Parallel Random Access Machine (PRAM)

PRAM for Parallel Random Access Machine is an abstract model of machine for designing algorithms for parallel machines model MIMD, or for rarer model SIMD.

PRAM model a parallel machine with a memory RAM shared by all processors. These processors are synchronized with each statement. We define several variants of this model, depending on memory access restrictions:

CRCW: Concurrent Read, Concurrent Write: each processor can read and write anywhere in memory at any time.

CREW: Concurrent Read, Exclusive Write: each processor can read any memory location at any time, but no two processors write simultaneously in one place is possible.

EREW: Exclusive Read, Exclusive Write: each processor can not read or write to a location in memory if there are no other processor accesses that time.

We define such a machine on the time complexity compared to the size of the input in the same way as a sequential algorithm (see Computational Complexity), and also the complexity in the number of processors used, again depending on the size of the input.

PRAM does wish, however, no account of the costs of data exchange between different machines. Particularly, the representation of a PRAM computer cluster on the memory is actually shared by each computer, neglecting the access time of a processor to a portion of memory that he is not physically local.