Parallel Random Access Machine (PRAM)

Parallel Random Access Machine (PRAM) --- параллельная равнодоступная адресная машина (ПРАМ).

A Parallel Random Access Machine (or PRAM) is an abstract model of parallel computation which can be used by parallel algorithms designers to estimate the inherent parellelism of a given problem. PRAM neglects such issues as synchronization and communication, but provides any (problem size-dependent) number of processors.

An [math]\displaystyle{ (n,m) }[/math]PRAM consists of [math]\displaystyle{ n }[/math] processors running synchronously and [math]\displaystyle{ m }[/math] memory locations, where each processor is a random-access machine. All processors share the memory, and hence are commutative via it. During a given cycle each processor may read an element from the shared memory into its local memory, write an element from its local memory to the shared memory, or perform any RAM operation on the data which it already has in its local memory. It is a synchronous model, that is no processor will proceed with instruction [math]\displaystyle{ i+1 }[/math] until all have finished instruction [math]\displaystyle{ i }[/math].

The read/write conflicts in accessing the same shared memory location simultaneously can be resolved by different strategies. There is a family of PRAM models, each of which differs in its characteristics on this point. The members of the family are:

(1) the Exclusive Read Exclusive Write PRAM (or EREW PRAM), where every memory location can be read or written to by only one processor at a time,

(2) the Concurrent Read Exclusive Write PRAM (or CREW PRAM), where multiple processors may read a particular memory location, but at most one processor may write to a particular memory location at a time,

(3) the Concurrent Read Concurrent Write PRAM (or CRCW PRAM), where multiple processors may read or write to any memory location.

The Exclusive Read Concurrent Write PRAMs are not considered, since a machine with enough power to support concurrent writes should be able to support concurrent reads.

The read causes no discrepancies while the concurrent write is further defined as follows:

(1) the Common CRCW PRAM, where all values written concur\-rent\-ly must be identical,

(2) the Arbitrary CRCW PRAM, where the processor that suc\-ceeds in its concurrent write is chosen arbitrary from the writing processors,

(3)the Priority CRCW PRAM, where the processor that succeeds in its concurrent write is the processor with the highest priority, e.g., the smallest processor index,

(4) the Combining CRCW PRAM, where the value written is a linear combination of all values which where concurrently written, e.g. a sum of the values. The values may be combined with any associative and commutative operation which is computable in constant time on a RAM.