Parallel RAM: Difference between revisions

Revision as of 07:58, 10 March 2024

Revision as of 08:57, 12 August 2024

Line 1:

{{short description|Abstract computer for designing parallel algorithms}}

{{more footnotes|date=July 2016}}

In [[computer science]], a '''parallel random-access machine''' ('''parallel RAM''' or '''PRAM''') is a [[shared memory architecture|shared-memory]] [[abstract machine]]. As its name indicates, the PRAM is intended as the parallel-computing analogy to the [[random-access machine]] (RAM) (not to be confused with [[random-access memory]]).<ref>{{Cite journalbook |lastlast1=Fortune |firstfirst1=Steven |last2=Wyllie |first2=James |date=1978-05-01 |titlechapter=Parallelism in random access machines |urldate=https://dl.acm.org/doi/10.1145/800133.8043391978-05-01 |journaltitle=Proceedings of the tenth annual ACM symposium on Theory of computing |series=- STOC '78 |chapter-url=https://dl.acm.org/doi/10.1145/800133.804339 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=114–118 |doi=10.1145/800133.804339 |isbn=978-1-4503-7437-8|hdl=1813/7454 |hdl-access=free }}</ref> In the same way that the RAM is used by sequential-algorithm designers to model algorithmic performance (such as time complexity), the PRAM is used by parallel-algorithm designers to model parallel algorithmic performance (such as time complexity, where the number of processors assumed is typically also stated). Similar to the way in which the RAM model neglects practical issues, such as access time to cache memory versus main memory, the PRAM model neglects such issues as [[Synchronization (computer science)|synchronization]] and [[communication]], but provides any (problem-size-dependent) number of processors. Algorithm cost, for instance, is estimated using two parameters O(time) and O(time × processor_number).

==Read/write conflicts==

Line 8:

#Exclusive read exclusive write (EREW)—every memory cell can be read or written to by only one processor at a time

#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)—mostly never considered because it mostly doesn't add more power<ref>{{Cite journal |lastlast1=MacKenzie |firstfirst1=Philip D. |last2=Ramachandran |first2=Vijaya |date=1998-04-06 |title=ERCW PRAMs and optical communication |url=https://www.sciencedirect.com/science/article/pii/S0304397597001990 |journal=Theoretical Computer Science |volume=196 |issue=1 |pages=153–180 |doi=10.1016/S0304-3975(97)00199-0 |issn=0304-3975}}</ref>

#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>