On communication latency in PRAM computations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On communication latency in PRAM computations

Full text

Pdf (1.45 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: 11 - 21

Year of Publication: 1989

ISBN:0-89791-323-X

Authors

A. Aggarwal	IBM Research Division, T. J. Watson Research Center, P. O. Box 218, Yorktown, Heights, New York
A. K. Chandra	IBM Research Division, T. J. Watson Research Center, P. O. Box 218, Yorktown, Heights, New York
M. Snir	IBM Research Division, T. J. Watson Research Center, P. O. Box 218, Yorktown, Heights, New York

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): 8, Downloads (12 Months): 42, Citation Count: 22

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.72937 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	Alok Aggarwal , Ashok K. Chandra, Communication Complexity of PRAMs (Preliminary Version), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.1-17, July 11-15, 1988
	2	[ACS87] A. Aggarwal, A. Chandra and M. Snir, "Hierarchical memory with Block Transfer," Proc. 28th IEEE Symp, on Foundations of Computer Science, 1987, pp. 204-216.
	3	M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
	4	William C. Athas , Charles L. Seitz, Multicomputers: Message-Passing Concurrent Computers, Computer, v.21 n.8, p.9-24, August 1988 [doi>10.1109/2.73]
	5	[Ba88] K.E. Batcher, "Sorting networks and their Applications," Proceedings, AFIPS 32, 1968. pp. 307-314.
	6	[BS78] G. Baudet and D. Stevenson, "Optimal Sorting Algorithms for Parallel Computers," IEEE Trans. on Computers, Vol. C-27, No. 1, 1978, pp. 84-87.
	7	D. A. Calahan, Performance evaluation of static and dynamic memory systems on the Cray-2, Proceedings of the 2nd international conference on Supercomputing, p.519-524, June 1988, St. Malo, France [doi>10.1145/55364.55414]
	8	[Ch76] A.K. Chandra, "Maximal Parallelism in Matrix Multiplication," IBM Technical Report RC 6193, Sept. 1976.
	9	D. R. Cheriton , A. Gupta , P. D. Boyle , H. A. Goosen, The VMP multiprocessor: initial experience, refinements, and performance evaluation, Proceedings of the 15th Annual International Symposium on Computer architecture, p.410-421, May 30-June 02, 1988, Honolulu, Hawaii, United States
	10	[Fl72] R.W. Floyd, "Permuting Information in Idealized Two-Level Storage," In R.E. Miller and J. W. Thatcher (editors), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 105-109.
	11	[GKLS83] D. Gajski, D. Kuck, D. Lawrie, and A. Sameh, "Cedar - a Large Scale Multiprocessor," Proc. of the 1983 Int. Conference on Parallel Processing, 1983, pp. 524-529.
	12	H. J. Hoover , M. M. Klawe , N. J. Pippenger, Bounding Fan-out in Logical Networks, Journal of the ACM (JACM), v.31 n.1, p.13-18, Jan. 1984 [doi>10.1145/2422.322412]
	13	Alan H. Karp, Programming for Parallelism, Computer, v.20 n.5, p.43-57, May 1987 [doi>10.1109/MC.1987.1663563]
	14	Clyde P. Kruskal , Larry Rudolph , Marc Snir, A Complexity Theory of Efficient Parallel Algorithms (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.333-346, July 11-15, 1988
	15	[KS88] C.P. Kruskal and C.H. Smith, "Definitions of Granularity," Proc. of Int. Symp. on High Performance Computer Systems, Ed. E. Gelenbe, North Holland, Amsterdam, 1988, pp. 257-268.
	16	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]
	17	[Pf85] G. Pfister et al. "The IBM Research Parallel Prototype (RP3): Introduction and Architecture," Proc. 1985 Int. Conf. on Parallel Processing, Aug. 1985, pp. 764-771.
	18	Christos H. Papadimitriou , Jeffrey D. Ullman, A communication-time tradeoff, SIAM Journal on Computing, v.16 n.4, p.639-646, Aug. 1987 [doi>10.1137/0216044]
	19	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]
	20	Anne M. Rogers , Keshav Pingali, Process Decomposition Through Locality of Reference, Cornell University, Ithaca, NY, 1988
	21	Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]
	22	[Vi83] U. Vishkin, "Implementation of Simultaneous Memory Address Access in Models That Forbid It," J. of Algorithms, Vol. 4, 1983, pp. 45-50.
	23	Uzi Vishkin , Avi Wigderson, Cynamic parallel memories, Information and Control, v.56 n.3, p.174-182, March 1983 [doi>10.1016/S0019-9958(83)80003-5]

CITED BY 22

	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
	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
	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.13-24, June 24-26, 1996, Padua, Italy
	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
	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
	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
	Micah Adler , John W. Byers , Richard M. Karp, Parallel sorting with limited bandwidth, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.129-136, June 24-26, 1995, Santa Barbara, California, 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
	Marc Snir, Issues and directions in scalable parallel computing, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.21-28, August 15-18, 1993, Ithaca, New York, United States
	Richard M. Karp , Abhijit Sahay , Eunice E. Santos , Klaus Erik Schauser, Optimal broadcast and summation in the LogP model, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.142-153, June 30-July 02, 1993, Velen, Germany
	Martin Reiman , Paul E. Wright, Performance analysis of concurrent-read exclusive-write, ACM SIGMETRICS Performance Evaluation Review, v.19 n.1, p.168-177, May 1991
	Ben H. H. Juurlink , Harry A. G. Wijshoff, A quantitative comparison of parallel computation models, ACM Transactions on Computer Systems (TOCS), v.16 n.3, p.271-318, Aug. 1998
	Yosi Ben-Asher , Gadi Haber, Parallel Solutions of Simple Indexed Recurrence Equations, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.22-37, January 2001
	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
	Marc Snir , David A. Bader, A Framework for Measuring Supercomputer Productivity, International Journal of High Performance Computing Applications, v.18 n.4, p.417-432, November 2004
	Joseph F. JáJá , Kwan Woo Ryu, The Block Distributed Memory Model, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.830-840, August 1996
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	Michael T. Goodrich, Parallel algorithms column 1: models of computation, ACM SIGACT News, v.24 n.4, p.16-21, Dec. 1993
	S. J. Bellantoni, Parallel RAMs with bounded memory wordsize, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.83-91, June 18-21, 1989, Santa Fe, New Mexico, United States
	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States
	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
	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