explain classification of PRAM model

explain classification of PRAM model

The PRAM model is an extension of the familiar

RAM model of sequential computation that is used in algorithm analysis. We will use the synchronous PRAM which

is defined as follows.

1. There are p processors connected to a single shared memory.

2. Each processor has a unique index 1 <= i <= p called the processor id.

3. A single program is executed in single-instruction stream, multiple-data stream (SIMD) fashion. Each instruction

in the instruction stream is carried out by all processors simultaneously and requires unit time, regardless

of the number of processors.

4. Each processor has a flag that controls whether it is active in the execution of an instruction. Inactive processors

do not participate in the execution of instructions, except for instructions that reset the flag.

The processor id can be used to distinguish processor behavior while executing the common program. For example,

each processor can use its processor id to form a distinct address in the shared memory from which to read a value.

A sequence of instructions can be conditionally executed by a subset of processors. The condition is evaluated by all

processors and is used to set the processor active flags. Only active processors carry out the instructions that follow.

At the end of the sequence the flags are reset so that execution is resumed by all processors.

The operation of a synchronous PRAM can result in simultaneous access by multiple processors to the same

location in shared memory. There are several variants of our PRAM model, depending on whether such simultaneous

access is permitted (concurrent access) or prohibited (exclusive access). As accesses can be reads or writes, we have

the following four possibilities:

1. Exclusive Read Exclusive Write (EREW): This PRAM variant does not allow any kind of simultaneous access

to a single memory location. All correct programs for such a PRAM must insure that no two processors access

a common memory location in the same time unit.

2. Concurrent Read Exclusive Write (CREW): This PRAM variant allows concurrent reads but not concurrent

writes to shared memory locations. All processors concurrently reading a common memory location obtain the

same value.

3. Exclusive Read Concurrent Write (ERCW): This PRAM variant allows concurrent writes but not concurrent

reads to shared memory locations. This variant is generally not considered independently, but is subsumed

within the next variant.

4. Concurrent Read Concurrent Write (CRCW): This PRAM variant allows both concurrent reads and concurrent

writes to shared memory locations. There are several sub-variants within this variant, depending on how

concurrent writes are resolved.

(a) Common CRCW: This model allows concurrent writes if and only if all the processors are attempting to

write the same value (which becomes the value stored).

(b) Arbitrary CRCW: In this model, a value arbitrarily chosen from the values written to the common memory

location is stored.

(c) Priority CRCW: In this model, the value written by the processor with the minimum processor id writing

to the common memory location is stored.

(d) Combining CRCW: In this model, the value stored is a combination (usually by an associative and commutative

operator such as + or max) of the values written.

The different models represent different constraints in algorithm design. They differ not in expressive power but

in complexity-theoretic terms. We will consider this issue further in Section 5.

We study PRAM algorithms for several reasons.

1. There is a well-developed body of literature on the design of PRAM algorithms and the complexity of such

algorithms.

2. The PRAM model focuses exclusively on concurrency issues and explicitly ignores issues of synchronization

and communication. It thus serves as a baseline model of concurrency. In other words, if you can’t get a good

parallel algorithm on the PRAM model, you’re not going to get a good parallel algorithm in the real world.

3. The model is explicit: we have to specify the operations performed at each step, and the scheduling of operations

on processors.

2

4. It is a robust design paradigm. Many algorithms for other models (such as the network model) can be derived

directly from PRAM algorithms.