Parallel RAM: Difference between revisions

Revision as of 03:53, 31 October 2019

Latest revision as of 02:40, 11 August 2025

(21 intermediate revisions by 15 users not shown)

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 wasis intended as the parallel-computing analogy to the [[random-access machine]] (RAM) (not to be confused with [[random-access memory]]).<ref>{{Cite book |last1=Fortune |first1=Steven |last2=Wyllie |first2=James |chapter=Parallelism in random access machines |date=1978-05-01 |title=Proceedings of the tenth annual ACM symposium on Theory of computing - 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 7 ⟶ 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 |last1=MacKenzie |first1=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|url-access=subscription }}</ref>

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

Line 26 ⟶ 27:

==Implementation==

PRAM algorithms cannot be parallelized with the combination of [[Central processing unit|CPU]] and [[dynamic random-access memory]] (DRAM) because DRAM does not allow concurrent access to a single bank (not even different addresses in the bank); but they can be implemented in hardware or read/write to the internal [[static random-access memory]] (SRAM) blocks of a [[field-programmable gate array]] (FPGA), it can be done using a CRCW algorithm.

However, the test for practical relevance of PRAM (or RAM) algorithms depends on whether their cost model provides an effective abstraction of some computer; the structure of that computer can be quite different than the abstract model. The knowledge of the layers of software and hardware that need to be inserted is beyond the scope of this article. But, articles such as {{harvtxt|Vishkin|2011}} demonstrate how a PRAM-like abstraction can be supported by the [[explicit multi-threading]] (XMT) paradigm and articles such as {{harvtxt|Caragea|Vishkin|2011}} demonstrate that a PRAM algorithm for the [[maximum flow problem]] can provide strong speedups relative to the fastest serial program for the same problem. The article {{harvtxt|Ghanim|Vishkin|Barua|2018}} demonstrated that PRAM algorithms as-is can achieve competitive performance even without any additional effort to cast them as mutlimulti-threaded programs on XMT.

==Example code==

This is an example of [[SystemVerilog]] code which finds the maximum value in the array in only 2 clock cycles. It compares all the combinations of the elements in the array at the first clock, and merges the result at the second clock. It uses CRCW memory; <code>m[i] <= 1</code> and <code>maxNo <= data[i]</code> are written concurrently. The concurrency causes no conflicts because the algorithm guarantees that the same value is written to the same memory. This code can be run on [[Field-programmable gate array|FPGA]] hardware.

<sourcesyntaxhighlight lang="SystemVerilog">

module FindMax #(parameter int len = 8)

(input bit clock, resetN, input bit[7:0] data[len], output bit[7:0] maxNo);

Line 67 ⟶ 68:

end

endmodule

</syntaxhighlight>

</source>

== See also ==

Line 104 ⟶ 105:

| last2=Ramachandran | first2=Vijaya

| title=A Survey of Parallel Algorithms for Shared-Memory Machines

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

| year=1988

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

Line 135 ⟶ 137:

| journal=Communications of the ACM

| volume=54

| doi-access=free

}}

* {{Citation

| last1=Caragea | first1=George Constantin

| last2=Vishkin | first2=Uzi

| titlechapter=Brief announcement: Better speedups for parallel max-flow

| title=Proceedings of the 23rd ACM symposium on Parallelism in algorithms and architectures - SPAA '11

| journal=

| pages=131

| year=2011

| doi=10.1145/1989493.1989511

| isbn=9781450307437

| s2cid=5511743

}}

* {{Citation

Line 152 ⟶ 157:

| title=Easy PRAM-based High-performance Parallel Programming with ICE

| journal=IEEE Transactions on Parallel and Distributed Systems

| volume=29,2

| issue=2

| pages=377–390

Line 158 ⟶ 163:

| doi=10.1109/TPDS.2017.2754376

| hdl=1903/18521

| doi-access=free

| hdl-access=free

}}

==External links==

* [http://www-wjp.cs.uni-sb.de/forschung/projekte/SB-PRAM/index.php Saarland University's prototype PRAM] {{Webarchive|url=https://web.archive.org/web/20160303202357/http://www-wjp.cs.uni-sb.de/forschung/projekte/SB-PRAM/index.php |date=2016-03-03 }}

* [http://www.umiacs.umd.edu/users/vishkin/XMT/spaa07paper.pdf University Of Maryland's PRAM-On-Chip prototype]. This prototype seeks to put many parallel processors and the fabric for inter-connecting them on a single chip

* [httphttps://sourceforge.net/projects/xmtc/ XMTC: PRAM-like Programming - Software release]

{{Parallel Computing}}