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

Common Memory

RAM RAM RAM

P 1 P 2 P p

Figure 7.21 The PRAM consists of synchronous RAMs accessing a common memory.

random-access memory and the common memory. During each PRAM step, the RAMs exe-
cute the following steps in synchrony: they (a) read from the common memory, (b) perform
a local computation, and (c) write to the common memory. Each RAM has its own program
and program counter as well as a unique identifying number id j that it can access to make
processor-dependent decisions. The PRAM is primarily an abstract programming model, not
a machine designed to be built (unlike mesh-based computers, for example).
The power of the PRAM has been explored by considering a variety of assumptions about
the length of local computations and the type of instruction allowed. In designing parallel
algorithms it is generally assumed that each local computation consists of a small number of
instructions. However, when this restriction is dropped and the PRAM is allowed an unlim-
ited number of computations between successive accesses to the common memory (the ideal
PRAM ), the information transmitted between processors reflects the minimal amount of in-
formation that must be exchanged to solve a problem on a parallel computer.
Because the size of memory words is potentially unbounded, very large numbers can be
generated very quickly on a PRAM if a RAM can multiply and divide integers and perform
vector operations. This allows each RAM to emulate a parallel machine with an unbounded
number of processors. Since the goal is to understand the power of parallelism, however, this
form of hidden parallelism is usually disallowed, either by not permitting these instructions or
by assuming that in t steps a PRAM generates numbers whose size is bounded by a polynomial
in t . To simplify the discussion, we limit instructions in a RAM's repertoire to addition,
subtraction, vector comparison operations, conditional branching, and shifts by fixed amounts.
We also allow load and store instructions for moving words between registers, local memories,
and the common memory. These instructions are sufficiently rich to compute all computable
functions.
As yet we have not specified the conditions under which access to the common memory oc-
curs in the first and third substeps of each PRAM step. If access by more than one RAM to the
same location is disallowed, access is exclusive . If this restriction does not apply, access is con-
current . Four combinations of these classifications apply to reading and writing. The strongest