Information Technology Reference
In-Depth Information
restriction is placed on the Exclusive Read/Exclusive Write (EREW) PRAM , with succes-
sively weaker restrictions placed on the Concurrent Read/Exclusive Write (CREW) PRAM ,
the Exclusive Read/Concurrent Write (ERCW) PRAM ,andthe Concurrent Read/Con-
current Write (CRCW) PRAM . When concurrent writing is allowed, conflicts are resolved
in one of the following ways: a) the COMMON model requires that all RAMs writing to a
common location write the same value, b) the ARBITRARY model allows an arbitrary value
to be written, and c) the PRIORITY model writes into the common location the value being
written by the lowest numbered RAM.
Observe that any algorithm written for the COMMON CRCW PRAM runs without
change on the ARBITRARY CRCW PRAM. Similarly, an ARBITRARY CRCW PRAM al-
gorithm runs without change on the PRIORITY CRCW PRAM. Thus, the latter is the most
powerful of the PRAM models.
In performing a computation on a PRAM it is typically assumed that the input is written
in the lowest numbered locations of the common memory. PRAM computations are charac-
terized by p ,the number of processors (RAMs) in use, and T ( time ), the number of PRAM
steps taken. Both measures are usually stated as a function of the size of a problem instance,
namely m , the number of input words, and n , their total length in bits.
After showing that tree, array, and hypercube algorithms translate directly to a PRAM
algorithm with no loss in efficiency, we explore the power of concurrency. This is followed by a
brief discussion of the simulation of a PRAM on a hypercube and a circuit on a CREW PRAM.
We close by referring the reader to connections established between PRAMs and circuits and
to the discussion of serial space and parallel time in Chapter 8 .
7.9.1 Simulating Trees, Arrays, and Hypercubes on the PRAM
We have shown that 1D arrays can be embedded into 2D meshes and that d -dimensional
meshes can be embedded into hypercubes while preserving the neighborhood structure of the
first graph in the second. Also, we have demonstrated that any balanced tree algorithm can be
simulated as a normal algorithm on a hypercube. As a consequence, in each case, an algorithm
designed for the first network carries over to the second without any increase in the number of
steps executed. We now show that normal hypercube algorithms are efficiently simulated on
an EREW PRAM.
With each d -dimensional hypercube processor, associate an EREW PRAM processor and
a reserved location in the common memory. In a normal algorithm each hypercube processor
communicates with its neighbor along a specified direction. To simulate this communication,
each associated PRAM processor writes the data to be communicated into its reserved location.
The processor for which the message is destined knows which hypercube neighbor is providing
the data and reads the value stored in its associated memory location.
When a hypercube algorithm is not normal, as many as d
1 neighbors can send messages
to one processor. Since EREW PRAM processors can access only one cell per unit time,
simulation of the hypercube can require a running time that is about d times that of the
hypercube.
THEOREM 7.9.1 Every T -step normal algorithm on the d -dimensional, n -vertex hypercube, n =
2 d ,canbesimulatedin O ( T ) steps on an n -processor EREW PRAM. Every T -step hypercube
algorithm, normal or not, can be simulated in O ( Td ) steps.
Search WWH ::




Custom Search