A more practical PRAM model

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A more practical PRAM model

Full text

Pdf (1.43 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the first annual ACM symposium on Parallel algorithms and architectures table of contents

Santa Fe, New Mexico, United States

Pages: 158 - 168

Year of Publication: 1989

ISBN:0-89791-323-X

Author

P. B. Gibbons

Computer Science Division, University of California, Berkeley, CA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 94, Citation Count: 40

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/72935.72953 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Aggarwal , A. K. Chandra , M. Snir, On communication latency in PRAM computations, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.11-21, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72937]
	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	Richard J. Anderson , Gary L. Miller, Deterministic Parallel List Ranking, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.81-90, June 28-July 01, 1988
	4	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	5	[CV86a] Richard Cole and Uzi Vishkin. Approximate and exact parallel scheduling with applications to list, tree, and graph problems. In Proc. of the Symp. on Foundations of Computer Science (FOCS), pages 478-491, 1986.
	6	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	7	D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
	8	R. Cole , O. Zajicek, The APRAM: incorporating asynchrony into the PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.169-178, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72954]
	9	[Eck] Diane M. Eckstein. Simultaneous memory access. Technical Report TR-79-6, Computer Science Dept., Iowa State University, Ames, Iowa, 1979.
	10	[Kar88] Richard M. Karp. personal communication, 1988.
	11	[KR88] Richard M. Karp and Vijaya L. Ramachandran. A survey of parallel algorithms for shared-memory machines. Technical Report UCB-CSD-88-408, Computer Science Division, University of California, Berkeley, March 1988. To appear in Handbook of Theoretical Computer Science, North-Holland, Amsterdam, 1989.
	12	[KRS88] Clyde P. Kruskal, Larry Rudolph, and Marc Snir. A complexity theory of efficient parallel algorithms. Technical Report RC 13572, IBM T. J. Watson Research Center, Yorktown Heights, New York, March 1988.
	13	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]
	14	[LF81] N. A. Lynch and M. J. Fisher. On describing the behavior of an implementation of distributed systems. Theoretical Computer Science , 13:17-43, 1981.
	15	Gary L. Miller , Vijaya Ramachandran , Erich Kaltofen, Efficient parallel evaluation of straight-line code and arithmetic circuits, SIAM Journal on Computing, v.17 n.4, p.687-695, August 1988 [doi>10.1137/0217044]
	16	Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
	17	[Ran87] A. Ranade. How to emulate shared memory. In Proc. off the Symp. on Foundations of Computer Science (FOCS), pages 185-194, 1987.
	18	[Sni88] Marc Snir. personal communication, 1988.
	19	[TV85] Robert E. Tarjan and Uzi Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14:862-874, 1985.

CITED BY 40

	David E. Culler , Richard M. Karp , David Patterson , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser , Ramesh Subramonian , Thorsten von Eicken, LogP: a practical model of parallel computation, Communications of the ACM, v.39 n.11, p.78-85, Nov. 1996
	Uzi Vishkin , Shlomit Dascal , Efraim Berkovich , Joseph Nuzman, Explicit multi-threading (XMT) bridging models for instruction parallelism (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.140-151, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
	Greg Barnes, A method for implementing lock-free shared-data structures, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.261-270, June 30-July 02, 1993, Velen, Germany
	Z. M. Kedem , K. V. Palem , A. Raghunathan , P. G. Spirakis, Combining tentative and definite executions for very fast dependable parallel computing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.381-390, May 05-08, 1991, New Orleans, Louisiana, United States
	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, ACM SIGPLAN Notices, v.28 n.7, p.1-12, July 1993
	Michael T. Goodrich, Communication-efficient parallel sorting (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.247-256, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Paris C. Kanellakis , Dimitrios Michailidis , Alex Allister Shvartsman, Controlling memory access concurrency in efficient fault-tolerant parallel algorithms, Nordic Journal of Computing, v.2 n.2, p.146-180, Summer 1995
	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, California, United States
	Bogdan S. Chlebus , Stefan Dobrev , Dariusz R. Kowalski , Grzegorz Malewicz , Alex Shvartsman , Imrich Vrto, Towards practical deteministic write-all algorithms, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.271-280, July 2001, Crete Island, Greece
	R. Cole , O. Zajicek, The expected advantage of asynchrony, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.85-94, July 02-06, 1990, Island of Crete, Greece
	Hagit Attiya , Nancy Lynch , Nir Shavit, Are wait-free algorithms fast?, Journal of the ACM (JACM), v.41 n.4, p.725-763, July 1994
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Can shared-memory model serve as a bridging model for parallel computation?, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.72-83, June 23-25, 1997, Newport, Rhode Island, United States
	Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States
	Jaswinder Pal Singh , Edward Rothberg , Anoop Gupta, Modeling communication in parallel algorithms: a fruitful interaction between theory and systems?, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.189-199, June 27-29, 1994, Cape May, New Jersey, United States
	Divyakant Agrawal , Manhoi Choy , Hong Va Leong , Ambuj K. Singh, Maya: a simulation platform for distributed shared memories, ACM SIGSIM Simulation Digest, v.24 n.1, p.151-155, July 1994
	J. Aspnes , M. Herlihy, Wait-free data structures in the asynchronous PRAM model, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.340-349, July 02-06, 1990, Island of Crete, Greece
	Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States
	Yonatan Aumann , Michael A. Bender , Lisa Zhang, Efficient execution of nondeterministic parallel programs on asynchronous systems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.270-276, June 24-26, 1996, Padua, Italy
	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
	N. Nishimura, Asynchronous shared memory parallel computation, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.76-84, July 02-06, 1990, Island of Crete, Greece
	Richard J. Anderson , Heather Woll, Wait-free parallel algorithms for the union-find problem, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.370-380, May 05-08, 1991, New Orleans, Louisiana, United States
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms on restartable fail-stop processors, Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.23-36, August 19-21, 1991, Montreal, Quebec, Canada
	Grzegorz Malewicz, A work-optimal deterministic algorithm for the asynchronous certified write-all problem, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.255-264, July 13-16, 2003, Boston, Massachusetts
	Bogdan S. Chlebus , Leszek Gasieniec , Andrzej Pelc, Deterministic computations on a PRAM with static processor and memory faults, Fundamenta Informaticae, v.55 n.3-4, p.285-306, June 2003
	Eric Freudenthal , Allan Gottlieb, Process coordination with fetch-and-increment, ACM SIGPLAN Notices, v.26 n.4, p.260-268, Apr. 1991
	Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States
	Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996
	Dariusz R. Kowalski , Alexander A. Shvartsman, Writing-all deterministically and optimally using a non-trivial number of asynchronous processors, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Thomas Grün , Thomas Rauber , Jochen Röhrig, Support for Efficient Programming on the SB-PRAM, International Journal of Parallel Programming, v.26 n.3, p.209-240, June 1998
	Grzegorz Malewicz, A tight analysis and near-optimal instances of the algorithm of Anderson and Woll, Theoretical Computer Science, v.329 n.1-3, p.285-301, 13 December 2004
	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990
	Paris C. Kanellakis , Alex A. Shvartsman, Efficient parallel algorithms can be made robust, Distributed Computing, v.5 n.4, p.201-217, April 1992
	Naomi Nishimura, Asynchronous shared memory parallel computation (preliminary version), ACM SIGARCH Computer Architecture News, v.19 n.1, p.97-105, March 1991
	Michael A. Bender , Cynthia A. Phillips, Scheduling DAGs on asynchronous processors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	M. Rasit Eskicioglu, A comprehensive bibliography of distributed shared memory, ACM SIGOPS Operating Systems Review, v.30 n.1, p.71-96, Jan. 1996
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	Jose Luis Bosque , Luis Pastor, A Parallel Computational Model for Heterogeneous Clusters, IEEE Transactions on Parallel and Distributed Systems, v.17 n.12, p.1390-1400, December 2006
	Dariusz R. Kowalski , Alexander A. Shvartsman, Writing-all deterministically and optimally using a nontrivial number of asynchronous processors, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-22, June 2008
	Reza Dorrigiv , Alejandro López-Ortiz , Alejandro Salinger, Optimal speedup on a low-degree multi-core parallel architecture (LoPRAM), Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany