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

There are many ways to characterize parallel computers. A fine-grained parallel computer
is one in which the focus is on its constituent components, which themselves consist of low-
level entities such as logic gates and binary memory cells. A coarse-grained parallel computer
is one in which we ignore the low-level components of the computer and focus instead on its
functioning at a high level. A complex circuit, such as a carry-lookahead adder, whose details
are ignored is a single coarse-grained unit, whereas one whose details are studied explicitly is
fine-grained. CPUs and large memory units are generally viewed as coarse-grained.
A parallel computer is a collection of interconnected processors (CPUs or memories). The
processors and the media used to connect them constitute a network . If the processors are
in close physical proximity and can communicate quickly, we often say that they are tightly
coupled and call the machine a parallel computer rather than a computer network. How-
ever, when the processors are not in close proximity or when their operating systems require a
large amount of time to exchange messages, we say that they are loosely coupled and call the
machine a computer network .
Unless a problem is trivially parallel, it must be possible to exchange messages between
processors. A variety of low-level mechanisms are generally available for this purpose. The use
of software for the exchange of potentially long messages is called message passing . In a tightly
coupled parallel computer, messages are prepared, sent, and received quickly relative to the
clock speed of its processors, but in a loosely coupled parallel computer, the time required for
these steps is much larger. The time T m to transmit a message from one processor to another
is generally assumed to be of the form T m = α + lβ ,where l is the length of the message in
words, α ( latency ) is the time to set up a communication channel, and β ( bandwidth )isthe
time to send and receive one word. Both α and β are constant multiples of the duration of
the CPU clock cycle of the processors. Thus, α + β is the time to prepare, send, and receive
a single-word message. In a tightly coupled machine α and β are small, whereas in a loosely
coupled machine α is large.
An important classification of parallel computers with memory is based on the degree to
which they share access to memory. A shared-memory computer is characterized by a model
in which each processor can address locations in a common memory. (See Fig. 7.2 (a).) In
this model it is generally assumed that the time to make one access to the common mem-

...

M p P p M 3 P 3

Common Memory

Network

...

P 1 P 2 P p M 1 P 1 M 2 P 2

(b)
Figure 7.2 (a) A shared-memory computer; (b) a distributed-memory computer.

(a)