An optical simulation of shared memory

ABSTRACT

We present a work-optimal randomized algorithm for simulating a shared memory machine (PRAM) on an optical communication parallel computer (OCPC). The OCPC model is motivated by the potential of optical communication for parallel computation. The memory of an OCPC is divided into modules, one module per processor. Each memory module only services a request on a timestep if it receives exactly one memory request. Our algorithm simulates each step of an n lg lg n-processor EREW PRAM on an n-processor OCPC in O(lg lg n) expected delay. (The probability that the delay is longer than this is at most n-&agr; for any constant &agr;.) The best previous simulation, due to Valiant, required &THgr;(lg n) expected delay.

REFERENCES

• 1: 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]
• 2: N.J. Anderson and G.L. Miller, Optical Communication for Pointer Based Algorithms, Technical Report CRI 88-14, Computer Science Department, University of Southern California, Los Angeles, CA 90089-0782 USA, 1988.
• 3: B. Bollob#s, Martingales, Isoperimetric Inequalities and Random Graphs, in Combinatorics (eds A. Hajnal, L. LovKsz, and V. T. S6s), Colloq. Math. Soc. Jdnos Bolyai 52 (North Holland 1988) 113-139.
• 4: J.L. Carter and M.N. Wegman, Universal Classes of Hash Functions, Journal of Computer and Systems Sciences 18 (1979) 143-154.
• 5: Bogdan S. Chlebus , Krzysztof Diks , Torben Hagerup , Tomasz Radzik, New Simulations between CRCW PRAMs, Proceedings of the International Conference on Fundamentals of Computation Theory, p.95-104, August 21-25, 1989
• 6: 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]
• 7: Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165246]
• 8: Mary Mehrnoosh Eshaghian, Parallel Algorithms for Image Processing on OMC, IEEE Transactions on Computers, v.40 n.7, p.827-833, July 1991 [doi>10.1109/12.83620]
• 9: Mihály Geréb-Graus , Thanasis Tsantilas, Efficient optical communication in parallel computers, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.41-48, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140906]
• 10: Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct Bulk-Synchronous Parallel Algorithms, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.1-18, July 08-10, 1992
• 11: Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, The QRQW PRAM: accounting for contention in parallel algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.638-648, January 23-25, 1994, Arlington, Virginia, United States
• 12: Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Efficient low-contention parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.236-247, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181382]
• 13: J. Gil and Y. Matias, Fast Hashing on a PRAM, Progorithms 2 (1991) 271-280.
• 14: Leslie Ann Goldberg, Mark Jerrum, Tom Leighton and Satish Rao, Doubly Logarithmic Communication Algorithms for Optical Communication Parallel Computers, Pre-print, 1994. (A preliminary version of this paper appeared in Proceedings o} the A CM Symposium On Parallel Algorithms and Architectures 5 (1993).)
• 15: Leslie Ann Goldberg, Mark Jerrum and Philip D. MacKenzie, An Ft(#) Lower Bound for Routing in Optical Networks, These proceedings.
• 16: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• 17: 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]
• 18: 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]
• 19: 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
• 20: 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]
• 21: Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
• 22: 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]
• 23: F. Meyer auf der Heide, C. Scheiderler, and V. Stemann, Fast simple dictionaries and shared memory simulation on distributed memory machines; upper and lower bounds, Pre-print 1994.
• 24: P. D. MacKenzie , C. G. Plaxton , R. Rajaraman, On contention resolution protocols and associated probabilistic phenomena, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.153-162, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195122]
• 25: C. McDiarmid, On the Method of Bounded Differences, Surveys in Combinatorics, London Math. Soc. Lecture Notes Series 141 (Cambridge Univ. Press, 1989) 148- 188.
• 26: W. F. McColl, General purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
• 27: David E. Muller , Franco P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching, Journal of the ACM (JACM), v.22 n.2, p.195-201, April 1975 [doi>10.1145/321879.321882]
• 28: 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
• 29: 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]
• 30: John H. Reif, Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 31: A. Siegel, On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications, Proceedings of the IEEE Symposium on Foundations of Computer Science 30 (1989) 20-25.
• 32: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
• 33: 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]
• 34: 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]
• 35: 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]
• 36: L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory, Verification