Parallel Random Access Machine

A Parallel Random Access Machine (PRAM) is a shared memory abstract machine which is used by parallel algorithms designers to estimate the algorithm performance (like its time complexity). PRAM neglects such issues as synchronization and communication, but provides any (problem size-dependent) number of processors. Algorithm cost, for instance, is estimated as O(time x processor_number).

The read/write conflicts in accessing the same shared memory location simultaneously are resolved by one of the following strategies:

1. Exclusive Read Exclusive Write (EREW) - every memory cell can be read or written to by only one processor at a time
2. Concurrent Read Exclusive Write (CREW) - multiple processors can read a memory cell but only one can write at a time
3. Exclusive Read Concurrent Write (ERCW) - never considered
4. Concurrent Read Concurrent Write (CRCW) - multiple processors can read and write.

Here, E and C stand for 'exclusive' and 'concurrent' correspondingly. The read causes no discrepancies while the concurrent write is further defined as:

Common - all processors write the same value; otherwise is illegal

Arbitrary - only one arbitrary attempt is successful, others retire

Priority - processor rank indicates who gets to write

Another kind of array Reduction operation like SUM, Logical AND or MAX.

Several simplifying assumptions are made while considering the development of algorithms for PRAM. They are :

1. There is no limit on the number of processors in the machine.
2. Any memory location is uniformly accessible from any processor.
3. There is no limit on the amount of shared memory in the system.
4. Resource contention is absent.
5. The programs written on these machines are, in general, of type MIMD. Certain special cases such as SIMD may also be handled in such a framework.

Algorithms are written in pseudo-code as there are only prototype implementations of a PRAM (see below). However, these kinds of algorithms are useful for understanding the exploitation of concurrency, dividing the original problem into similar sub-problems and solving them in parallel.

See also

• Flynn's taxonomy
• Lock-free and wait-free algorithms
• Random access machine
• XMTC

External links

• Saarland University's prototype PRAM
• University Of Maryland's prototype PRAM
• XMTC: PRAM-like Programming - Software release

References

Keller, Jörg; Christoph Keßler, Jesper Träff (2001). Practical PRAM Programming. John Wiley and Sons. ISBN 0471353515.