A survey of PRAM simulation techniques

ABSTRACT

The Parallel Random Access Machine (PRAM) is an abstract model of parallel computation which allows researchers to focus on the essential characteristics of a parallel architecture and ignore other details. The PRAM has long been acknowledged to be a useful tool for the study of parallel computing, but unfortunately it is not physically implementable in hardware. In order to take advantage of the broad base of algorithms and results regarding this high-level abstraction one needs general methods for allowing the execution of PRAM algorithms on more realistic machines. In the following we survey these methods, which we refer to as PRAM simulation techniques. The general issues of memory management and routing are discussed, and both randomized and deterministic solutions are considered. We show that good theoretical solutions to many of the subproblems in PRAM simulation have been developed, though questions still exist as to their practical utility. This article should allow those performing research in this field to become well acquainted with the current state of the art, while allowing the novice to get an intuitive feeling for the fundamental questions being considered. The introduction should provide a concise tutorial for those unfamiliar with the problem of PRAM simulation.

REFERENCES

• 1: Alok Aggarwal , Ashok K. Chandra , Marc Snir, Communication complexity of PRAMs, Theoretical Computer Science, v.71 n.1, p.3-28, 13 March 1990 [doi>10.1016/0304-3975(90)90188-N]
• 2: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 3: AKL, S. G. 1989a. On the power of concurrent memory access. In Computing and In/ormatzon, R. Janickyi and W. W. Koczkodaj, Eds. Elsewer Science Publishers, New York, 49 55.
• 4: Selim G. Akl, The design and analysis of parallel algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 5: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• 6: Helmut Alt , Torben Hagerup , Kurt Mehlhorn , Franco P. Perparata, Deterministic simulation of idealized parallel computers on more realistic ones, SIAM Journal on Computing, v.16 n.5, p.808-835, Oct. 1987 [doi>10.1137/0216053]
• 7: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 8: S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
• 9: Yonatan Aumann , Assaf Schuster, Improved memory utilization in deterministic PRAM simulation, Journal of Parallel and Distributed Computing, v.12 n.2, p.146-151, June 1991 [doi>10.1016/0743-7315(91)90018-5]
• 10: BATCHER, K E 1968. Sorting networks and their applications. In Proceeding of the AFIPS Spring Joint Computer Conference AFIPS, Washington, D. C., 307-314.
• 11: A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
• 12: C^RTE}~, J. L., )d'~D WEOMAN, M.N. 1979. Umversal classes of hash functions. J. Comput. Svst Scl 18, 2, 143-154.
• 13: Stephen A. Cook, The Classifikation of Problems which have Fast Parallel Algorithms, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.78-93, August 21-27, 1983
• 14: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 15: M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100229]
• 16: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 17: Alan Gibbons , Wojciech Rytter, Efficient parallel algorithms, Cambridge University Press, New York, NY, 1988
• 18: Leslie M. Goldschlager, A universal interconnection pattern for parallel computers, Journal of the ACM (JACM), v.29 n.4, p.1073-1086, Oct. 1982 [doi>10.1145/322344.322353]
• 19: HERLEY, K. T. 1989. Efficient simulations of small shared memories on bounded degree networks. In Proceedings of the 30th Symposium on Foundatwns of Computer Science. 390-395.
• 20: HERLEY, K. T. AND BmARDI, G. 1988. Deterministic simulations of PRAMs on bounded degree networks In Proceedings of the 26th Allerton Conference on Communication, Control and Computation. IEEE, New York
• 21: Scot W. Hornick , Franco P. Preparata, Deterministic P-RAM simulation with constant redundancy, Information and Computation, v.92 n.1, p.81-96, May 1991 [doi>10.1016/0890-5401(91)90021-S]
• 22: C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97453]
• 23: A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12146]
• 24: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 25: Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129743]
• 26: Danny Krizanc, Oblivious routing with limited buffer capacity, Journal of Computer and System Sciences, v.43 n.2, p.317-327, Oct. 1991 [doi>10.1016/0022-0000(91)90017-Y]
• 27: Clyde P. Kruskal , Larry Rudolph , Marc Snir, A complexity theory of efficient parallel algorithms, Theoretical Computer Science, v.71 n.1, p.95-132, 13 March 1990 [doi>10.1016/0304-3975(90)90192-K]
• 28: KUCERA, L. 1982. Parallel computation and conflicts in memory access. Inf. Process. Lett. 14, 2, 93-96.
• 29: LEIGHTON, F.T. 1989. Expanders might be practical: Fast algorithms for routing around faults on multibutterfiies. In Proceedings of the 30th Symposium on Foundations o)~ Computer Science. 384 389.
• 30: Tom Leighton, Tight bounds on the complexity of parallel sorting, IEEE Transactions on Computers, v.34 n.4, p.344-354, April 1985 [doi>10.1109/TC.1985.5009385]
• 31: Fabrizio Luccio , Andrea Pietracaprina , Geppino Pucci, Analysis of parallel uniform hashing, Information Processing Letters, v.37 n.2, p.67-69, Jan. 31, 1991 [doi>10.1016/0020-0190(91)90135-5]
• 32: Luccio, F., PEITRACAPRINA, A., AND PUCCI, G. 1990. A new scheme for the deterministic simulation of PRAMs in VLSI. Algortthmlca 5, 529 536.
• 33: Fabrizio Luccio , G. Pucci , I. Pietracaprina, A probabilistic simulation of PRAMs on a bounded degree network, Information Processing Letters, v.28 n.3, p.141-147, July 4, 1988 [doi>10.1016/0020-0190(88)90160-3]
• 34: Y. Mansour , N. Nisan , P. Tiwari, The computational complexity of universal hashing, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.235-243, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100246]
• 35: Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
• 36: MCCOLL, W. F. 1992. General purpose parallel computing. In Proceedzngs of the 1991 ALCOM Spring School on Parallel Computatwn, Gibbons and Spirakis, Eds. Cambridge University Press, Cambridge, England.
• 37: Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
• 38: M. S. Paterson, Improved Sorting Networks with O(log n) Depth, University of Warwick, Coventry, UK, 1987
• 39: PF~STER, G. F. AND NORTON, V. A. 1985. "Hot Spot" contention and combining in multistage interconnection networks. IEEE Trans. Cornput. C-34, 10.
• 40: PIPPENGER, N. 1984. Parallel communication with limited buffers. In the 25th Symposium on Foundations of Computer Science. 127-136.
• 41: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 42: Abhiram G. Ranade, How to emulate shared memory, Journal of Computer and System Sciences, v.42 n.3, p.307-326, June 1991 [doi>10.1016/0022-0000(91)90005-P]
• 43: Abhiram G. Ranade , Sandeep N. Bhatt , Lennart S. Johnsson, The fluent abstract machine, Proceedings of the fifth MIT conference on Advanced research in VLSI, p.71-93, January 1988, Cambridge, Massachusetts, United States
• 44: SANZ, J. L. C., ED. 1988. Opportumties and constraints of parallel computing. IBM Workshop, Almaden Research Center, San Jose, Calif.
• 45: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 46: SmLOACH, Y. AND VISHKIN, U. 1981. Finding the maximum, merging, and sorting in a parallel computation model. J. ACM 2, 1, 88-102.
• 47: SIEGEL, h. 1989. On universal classes of fast high performance hash functions, their time-space tradeoff, and their application. In Proceedings of the 30th Symposium on Foundations of Computer Science. 20-24.
• 48: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]
• 49: E. Upfal, An O(logN) deterministic packet routing scheme, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.241-249, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73030]
• 50: Eli Upfal, A probabilistic relation between desirable and feasible, models of parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.258-265, December 1984 [doi>10.1145/800057.808689]
• 51: Eli Upfal, Efficient Schemes for Parallel Communication, Journal of the ACM (JACM), v.31 n.3, p.507-517, July 1984 [doi>10.1145/828.1892]
• 52: Eli Upfal , Avi Wigderson, How to share memory in a distributed system, Journal of the ACM (JACM), v.34 n.1, p.116-127, Jan. 1987 [doi>10.1145/7531.7926]
• 53: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 54: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 55: VALrANT, L. G. 1983. Optimality of a two-phase strategy for routing in mterconnectmn networks. IEEE Trans Corr~put. C-32, 8,861-863,
• 56: VALIANT, L. G. 1982. A scheme for fast parallel communication. SIAM J. Cornput. 11, 2, 350 361
• 57: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 58: Uzi Vishkin, A parallel-design distributed-implementation (PDDI) general-purpose computer, Theoretical Computer Science, v.32 n.1-2, p.157-172, July 1984 [doi>10.1016/0304-3975(84)90028-8]
• 59: V~SHKIN, U. 1982 Implementation of simultaneous memory address access in models that forbid it J. Alg. 4, 1, 45-50.
• 60: W.-D. Weber , A. Gupta, Exploring the benefits of multiple hardware contexts in a multiprocessor architecture: preliminary results, Proceedings of the 16th annual international symposium on Computer architecture, p.273-280, April 1989, Jerusalem, Israel

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Relations between models
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Sorting and searching

General Terms:
Algorithms

Keywords:
bounded-degree networks, models of parallel computation, parallel complexity theory