Parallel random access machine

PRAM

A model for parallel computation that assumes the presence of a number of processors operating synchronously in parallel and having access to a single unbounded shared memory at unit cost [a1], [a2]. This model can be viewed as a natural extension of the classical sequential model, consisting of a central processing unit with a random access memory attached to it, which is equivalent to the universal Turing machine model. The PRAM model has been widely used, especially by the theoretical computer science community, for designing and analyzing parallel combinatorial and graph-theoretic algorithms. The model focuses on the inherent level of computational parallelism without worrying about communication delays between the processors or delays due to memory accesses. There are several variations of the PRAM, depending on how the simultaneous access to a single location of the shared memory is handled. The main variations are as follows.

Exclusive read exclusive write parallel random access machine (EREW PRAM): the most restrictive version, in that it does not allow any simultaneous access to a single memory location by different processors. Note however that simultaneous access to different memory locations in unit time is a fundamental feature of all the variations of the PRAM model.

Concurrent read exclusive write parallel random access machine (CREW PRAM): a version allowing simultaneous access for a read operation only. No concurrent write operation to a single location is legal.

Concurrent read concurrent write parallel random access machine (CRCW PRAM): a version allowing the simultaneous read and write operations to a single memory location. The simultaneous write operations to a single memory location can be resolved in different ways including allowing an arbitrary processor to succeed (arbitrary CRCW), or allowing the highest priority processor to succeed (priority CRCW), or insisting that all the processors write the same value into the single location (common CRCW).

The computational powers of the different PRAM versions are relatively minor, but it can be shown that the CRCW PRAM is strictly more powerful than the CREW PRAM, which is strictly more powerful than the EREW PRAM. However there is an $O(\log n)$-time simulation between the priority CRCW PRAM (strongest PRAM) and the EREW PRAM (weakest PRAM).

The PRAM model allows the development of very fast algorithms for many problems. In fact, most combinatorial and numeric problems can be solved on the PRAM model in $O(\log^kn)$ time using a polynomial number of processors. Such problems define a computational class called $\mathcal{NC}$, that is, $\mathcal{NC}$ is the class of all problems that can be solved on the PRAM in poly-logarithmic time with a polynomial number of processors, or, equivalently, $\mathcal{NC}$ is the class of languages recognizable in polynomial size and poly-log-depth circuits [a5]. In fact, many combinatorial and graph-theoretic problems can be solved in $O(\log n)$ time using an optimal number of processors, that is, the product of the execution time and the number of the processors matches the sequential complexity of the problem. Examples of such problems include parallel sorting algorithms running in $O(\log n)$ time using $O(n)$ processors, parallel matrix multiplication algorithms running in $O(\log n)$ time using $O(n^3/\log n)$ processors, and string matching in $O(\log n)$ time using $O(n/\log n)$ processors.

However, there are several simple combinatorial problems that have efficient polynomial-time sequential algorithms but which seem to be outside the class $\mathcal{NC}$, that is, they do not seem to be solvable in poly-logarithmic parallel time with a polynomial number of processors. The list of such problems includes: determining the ordered depth-first search numbering of the vertices of an arbitrary graph, determining the maximum flow in a network, and determining the feasibility of a set of linear inequalities. In fact, these particular problems are $\mathcal P$-complete, that is, they are the most likely candidates in the class $\mathcal P$ that are outside $\mathcal{NC}$, where $\mathcal P$ consists of all the problems that can be solved in polynomial sequential time (cf. also Complexity theory; $\mathcal{NP}$).

The PRAM model is closely related to the fine grain data parallel model, which was initially developed independently of the PRAM model. The data parallel programming model [a3] is specified in terms of a sequence of steps such that any number of concurrent operations whose inputs are available can take place at each step, independently of the number of processors available. The data parallel model was initially advocated for large-scale artificial intelligence and image processing problems, which exhibit a very high degree of data parallelism and local dependence.

For more details about PRAM algorithms or the relative computational power of the PRAM model, see [a4].

References

[a1]	S. Fortune, J. Wyllie, "Parallelism in random access machines" , Proc. Tenth Annual ACM Symp. Theory of Computing, San Diego, CA (1978) , ACM (1978) pp. 114–118
[a2]	L.M. Goldschlager, "A unified approach to models of synchronous parallel machines" , Proc. Tenth Annual ACM Symp. Theory of Computing, San Diego, CA (1978) , ACM (1978) pp. 89–94
[a3]	W.D. Hillis, G.L. Steele, "Data parallel algorithms" Commun. ACM , 29 : 12 (1986) pp. 1170–1183
[a4]	J. JaJa, "An introduction to parallel algorithms" , Addison-Wesley (1992)
[a5]	N. Pippenger, "On simultaneous resource bounds" , Proc. Twentieth Annual IEEE Symp. Foundations of Computer Sci., San Juan, Puerto Rico (1979) (1979) pp. 307–311