Parallel Computation - Models of Computation: Exploring the Power of Computing - page 285

ory is relatively close to the time for a processor to access one of its registers. Processors in a
shared-memory computer can communicate with one another via the common memory. The
distributed-memory computer is characterized by a model in which processors can commu-
nicate with other processors only by sending messages. (See Fig. 7.2 (b).) In this model it is
generally assumed that processors also have local memories and that the time to send a message
from one processor to another can be large relative to the time to access a local memory. A third
type of computer, a cross between the first two, is the distributed shared-memory computer .
It is realized on a distributed-memory computer on which the time to process messages is large
relative to the time to access a local memory, but a layer of software gives the programmer the
illusion of a shared-memory computer. Such a model is useful when programs can be executed
primarily from local memories and only occasionally must access remote memories.
Parallel computers are synchronous if all processors perform operations in lockstep and
asynchronous otherwise. A synchronous parallel machine may alternate between executing
instructions and reading from local or common memory. (See the PRAM model of Sec-
tion 7.9 , which is a synchronous, shared-memory model.) Although a synchronous parallel
computational model is useful in conveying concepts, in many situations, as with loosely cou-
pled distributed computers, it is not a realistic one. In other situations, such as in the design
of VLSI chips, it is realistic. (See, for example, the discussion of systolic arrays in Section 7.5 .)

7.3.1 Flynn's Taxonomy
Flynn's taxonomy of parallel computers distinguishes between four extreme types of paral-
lel machine on the basis of the degree of simultaneity in their handling of instructions and
data. The single-instruction, single-data (SISD) model is a serial machine that executes one
instruction per unit time on one data item. An SISD machine is the simplest form of serial
computer. The single-instruction, multiple-data (SIMD) model is a synchronous parallel
machine in which all processors that are not idle execute the same instruction on potentially
different data. (See Fig. 7.3 .) The multiple-instruction,single-data(MISD) model de-
scribes a synchronous parallel machine that performs different computations on the same data.
While not yet practical, the MISD machine could be used to test the primality of an inte-
ger (the single datum) by having processors divide it by independent sets of integers. The

Common Memory

...

P 1 P 2 P p

Control Unit

Figure 7.3 In the SIMD model the same instruction is executed on every processor that is
not idle.