Parallel RAM: Difference between revisions

Revision as of 17:44, 27 November 2012

Revision as of 17:46, 27 November 2012

Line 79:

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

==References==

Unbounded collection of numbered RAM processors P0, P1, P2,... (without tapes).

{{Reflist}}

Unbounded collection of shared memory cells M[0], M[1], M[2],....

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.

{{Citation

Input af a PRAM algorithm consists of n items stored in (usually the first) n shared memory cells.

| last1=Eppstein | first1=David

Output of a PRAM algorithm consists of n' items stored in n' shared memory cells.

| last2=Galil | first2=Zvi

PRAM instructions execute in 3-phase cycles.

| title=Parallel algorithmic techniques for combinatorial computation

Read (if any) from a shared memory cell.

| journal=Ann. Rev. Comput. Sci

Local computation (if any).

| year=1988

Write (if any) to a shared memory cell.

| volume=3

Processors execute these 3-phase PRAM instructions synchronously.

| pages=233–283

Special assumptions have to be made about R-R and W-W shared memory access conflicts.

| number=

The only way processors can exchange data is by writing into and reading from memory cells.

| doi=10.1146/annurev.cs.03.060188.001313

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.

}}

Computation proceeds until P0 halts, at which time all other active processors are halted.

Parallel time complexity = the time elapsed for P0's computation.

{{Citation

Space complexity = the number of shared memory cells accessed.

| 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模型]]