|
* [http://sourceforge.net/projects/xmtc/ XMTC: PRAM-like Programming - Software release]
Unbounded collection of numbered RAM processors P0, P1, P2,... (without tapes).
==References==
Unbounded collection of shared memory cells M[0], M[1], M[2],....
{{Reflist}}
Each Pi has its own (unbounded) local memory (registers) and knows its index i.
Each processor can access any shared memory cell (unless there is an access conflict, see further) in unit time.
Input af a PRAM algorithm consists of n items stored in (usually the first) n shared memory cells.
{{Citation
Output of a PRAM algorithm consists of n' items stored in n' shared memory cells.
| last1=Eppstein | first1=David
PRAM instructions execute in 3-phase cycles.
| last2=Galil | first2=Zvi
Read (if any) from a shared memory cell.
| title=Parallel algorithmic techniques for combinatorial computation
Local computation (if any).
| journal=Ann. Rev. Comput. Sci
Write (if any) to a shared memory cell.
| year=1988
Processors execute these 3-phase PRAM instructions synchronously.
| volume=3
Special assumptions have to be made about R-R and W-W shared memory access conflicts.
| pages=233–283
The only way processors can exchange data is by writing into and reading from memory cells.
| number=
P0 has a special activation register specifying the maximum index of an active processor. Initially, only P0 is active, it computes the number of required active processors and loads this register, and then the other corresponding processors start executing their programs.
| doi=10.1146/annurev.cs.03.060188.001313
Computation proceeds until P0 halts, at which time all other active processors are halted.
}}
Parallel time complexity = the time elapsed for P0's computation.
Space complexity = the number of shared memory cells accessed.
{{Citation
| first = Joseph
| last = JaJa
| coauthors =
| title = [[An Introduction to Parallel Algorithms]]
| edition =
| publisher = Addison-Wesley
| date = 1992
| isbn = 0-201-54856-9
}}
{{Citation
| last1=Karp | first1=Richard M.
| last2=Ramachandran | first2=Vijaya
| title=A Survey of Parallel Algorithms for Shared-Memory Machines
| journal=University of California, Berkeley, Department of EECS, Tech. Rep. UCB/CSD-88-408
| year=1988
| volume=
| pages=
| number=
| doi=
}}
{{cite book | first=Jörg | last=Keller | coauthors=Christoph Keßler, Jesper Träff | title=Practical PRAM Programming | publisher=John Wiley and Sons | year=2001 | isbn=0-471-35351-5}}
{{Citation
| authorlink = Uzi Vishkin
| first = Uzi
| last = Vishkin
| coauthors =
| title = Thinking in Parallel: Some Basic Data-Parallel Algorithms and Techniques, 104 pages
| edition =
| publisher = Class notes of courses on parallel algorithms taught since 1992 at the University of Maryland, College Park, Tel Aviv University and the Technion
| date = 2009
| isbn =
| url=http://www.umiacs.umd.edu/users/vishkin/PUBLICATIONS/classnotes.pdf
}}
{{Citation
| last1=Vishkin | first1=Uzi
| title=Communications of the ACM, Volume 54 Issue 1, January 2011
| contribution=Using simple abstraction to reinvent computing for parallelism
| pages=75–85
| year=2011
| doi=10.1145/1866739.1866757
| url=10.1145/1866739.1866757
| journal=Communications of the ACM
| volume=54
}}
{{Citation
| last1=Caragea | first1=George Constantin
| last2=Vishkin | first2=Uzi
| title=Better speedups for parallel max-flow
| journal=ACM SPAA
| year=2011
| doi=10.1145/1989493.1989511
}}
{{Parallel Computing}}
[[Category:Models of computation]]
[[de:Parallel Random Access Machine]]
[[fa:حافظه دسترسی تصادفی موازی]]
[[fr:Parallel random access machine]]
[[ja:並列ランダムアクセス機械]]
[[zh:PRAM模型]]
| 