Multiprocessors and Multicomputer

Even though all distributed systems consist of multiple CPUs, there are several different ways the hardware can be organized, especially in terms of how they are interconnected and how they communicate.
Various classification schemes for multiple CPU computer systems have been proposed over the years, but none of them have really caught on and been widely adopted.

Flynn picked two characteristics that he considered essential:
The number of instruction streams and
The number of data streams.

Flynn’s Classification for multiple CPU computer systems

● SISD
A computer with a single instruction stream and a single data stream is called SISD. All traditional uniprocessor computers (i.e., those having only one CPU) fall in this category, from personal computers to large mainframes.

● SIMD
Computer with a single instruction stream and multiple data stream is
called SIMD. For example, adding(Single Instruction) up all the
elements(multiple data) of 64 independent vectors.

● MISD
Computer with Multiple instruction streams and single data stream is called MISD. No known computers fit this model.

● MIMD
Finally, comes MIMD, which essentially means a group of independent computers, each with its own program counter, program, and data. All distributed systems are MIMD.

Multiprocessors:
Tthose have shared memory In a multiprocessor, there is a single virtual address space that is shared by
all CPUs. If any CPU writes, for example, the value 44 to address 1000, any other CPU subsequently reading from its address 1000 will get the value 44. All the machines share the same memory.

● Multicomputer:
Tthose do not have shared memory In a multicomputer, every machine has its own private memory. If one CPU writes the value 44 to address 1000, when another CPU reads address 1000 it will get whatever value was there before. The write of 44 does not affect its memory at all.
A common example of a multicomputer is a collection of personal computers connected by a network.

Another dimension to Taxonomy is that in some systems the machines are:-

• Tightly coupled systems

The delay experienced when a message is sent from one computer to another is short, and the data rate is high; that is, the number of bits per second that can be transferred is large. For example, two CPU chips on the same printed circuit board and connected by wires etched onto the board are likely to be tightly coupled.

•  Loosely-coupled system

In a loosely-coupled system, the opposite is true: the intermachine message delay is large and the data rate is low. For example, two computers connected by a 2400 bit/sec modem over the telephone system are certain to be loosely coupled. Each of these categories can be further divided based on the architecture of
the interconnection network. In Fig.1 we describe these two categories as

• Bus-based

There is a single network, backplane, bus, cable, or other medium that connects all the machines. Cable television uses a scheme like this: the cable company runs a wire down the street, and all the subscribers have taps running to it from their television sets.

• Bus-Based Multiprocessors

Bus-based multiprocessors consist of some number of CPUs all connected to a common bus, along with a memory module. A simple configuration is to have a high-speed backplane or motherboard into which CPU and memory cards can be inserted. A typical bus has 32 or 64 address lines, 32 or 64 data lines, and perhaps
32 or more control lines, all of which operate in parallel.

To read a word of memory, a CPU puts the address of the word it wants on the bus address lines, and then puts a signal on the appropriate control lines to indicate that it wants to read. The memory responds by putting the value of the word on the data lines to allow the requesting CPU to read it in. Writes work in a similar way.

Since there is only one memory, if CPU A writes a word to memory and then CPU B reads that word back a microsecond later, B will get the value just written. A memory that has this property is said to be coherent. Coherence plays an important role in distributed operating systems.

Issue:
With as few as 4 or 5 CPUs, the bus will usually be overloaded and
performance will drop drastically.

Solution:
Add a high-speed cache memory between the CPU and the bus, as shown in Fig.3. The cache holds the most recently accessed words. All memory requests go through the cache. If the word requested is in the cache, the cache itself responds to the CPU, and no bus request is made, and the amount of bus traffic per
CPU will drop dramatically, allowing many more CPUs in the system.

Issue: Suppose that two CPUs, A and B, each read the same word into their respective caches. Then A overwrites the word. When B next reads that word, it gets the old value from its cache, not the value A just wrote. The memory is now incoherent, and the system is difficult to program.

Solution

i) write-through cache
Whenever a word is written to the cache, it is written through to memory as well. In this design, cache hits for reads do not cause bus traffic, but cache misses for reads, and all writes, hits and misses, cause bus traffic.

ii) Snoopy or Snooping cache
All caches constantly monitor the bus. Whenever a cache sees a write occurring to a memory address present in its cache, it either removes that entry from its cache, or updates the cache entry with the new value.

A design consisting of snoopy write-through caches is coherent and is invisible to the programmer. Nearly all bus-based multiprocessors use either this architecture or one closely related to it. Using it, it is possible to put about 32 or possibly 64 CPUs on a single bus.