Parallel RAM: Difference between revisions

Revision as of 14:24, 24 May 2019

Revision as of 23:52, 12 June 2019

Line 8:

#Concurrent read exclusive write (CREW)—multiple processors can read a memory cell but only one can write at a time

#Exclusive read concurrent write (ERCW)—never considered

#Concurrent read concurrent write (CRCW)—multiple processors can read and write. A CRCW PRAM is sometimes called a '''concurrent random-access machine'''.<ref>Neil Immerman, ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.1834&rep=rep1&type=pdf Expressibility and parallel complexity]''. SIAM Journal on Computing, vol. 18, no. 3, pp. 625-638, 1989.</ref>

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

Line 23:

# The programs written on these machines are, in general, of type [[SIMD]].

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. The introduction of the formal 'P-RAM' model in Wyllie's 1979 thesis<ref>Wyllie, James C. [https://ecommons.cornell.edu/bitstream/handle/1813/7502/79-387.ps?sequence=2 The Complexity of Parallel Computations], PhD Thesis, Dept. of Computer Science, Cornell University</ref> had the aim of quantifying analysis of parallel algorithms in a way analogous to the [[Turing Machine]]. The analysis focused on a MIMD model of programming using a CREW model but showed that many variants, including implementing a CRCW model and implementing on an SIMD machine, were possible with only constant overhead.

==Implementation==

Line 106:

| journal=University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408

| year=1988

| url = https://dl.acm.org/citation.cfm?id=894803

}}

* {{cite book