Towards an architecture-independent analysis of parallel algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards an architecture-independent analysis of parallel algorithms

Full text

Pdf (427 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twentieth annual ACM symposium on Theory of computing table of contents

Chicago, Illinois, United States

Pages: 510 - 513

Year of Publication: 1988

ISBN:0-89791-264-0

Authors

Christos Papadimitriou	Department of Computer Science and Engineering, University of California at San Diego
Mihalis Yannakakis	AT&T Bell Laboratories

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 90, Citation Count: 26

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/62212.62262 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.

	Be	C. Gordon Bell "Gordon Bell on the Future of Computers", interview in SIAM NEWS, February 1987.
	PU	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]

CITED BY 26

	Bonnie Berger , Lenore Cowen, Complexity results and algorithms for {<,≤,=}-constrained scheduling, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.137-147, January 28-30, 1991, San Francisco, California, United States
	Xiaotie Deng , Elias Koutsoupias, Competitive implementation of parallel programs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.455-461, January 25-27, 1993, Austin, Texas, United States
	Chandra Chekuri , Waqar Hasan , Rajeev Motwani, Scheduling problems in parallel query optimization, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.255-265, May 22-25, 1995, San Jose, California, United States
	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
	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
	Pauline Markenscoff , Yong Yuan Li, An optimal algorithm for scheduling a computational tree on a parallel system with communication delays, Proceedings of the 19th annual conference on Computer Science, p.289-298, April 1991, San Antonio, Texas, 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. Koch , T. Leighton , B. Maggs , S. Rao, Work-preserving emulations of fixed-connection networks, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.227-240, May 14-17, 1989, Seattle, Washington, United States
	Xiaotie Deng , Nian Gu , Tim Brecht , KaiCheng Lu, Preemptive scheduling of parallel jobs on multiprocessors, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.159-167, January 28-30, 1996, Atlanta, Georgia, United States
	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
	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
	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
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Journal of the ACM (JACM), v.46 n.2, p.281-321, March 1999
	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
	Eunice E. Santos, Optimal and efficient algorithms for summing and prefix summing on parallel machines, Journal of Parallel and Distributed Computing, v.62 n.4, p.517-543, April 2002
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias, Provably efficient scheduling for languages with fine-grained parallelism, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1995, Santa Barbara, California, United States
	Michael T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.767-776, January 05-07, 1997, New Orleans, Louisiana, 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
	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
	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990
	Richard R. Koch , F. T. Leighton , Bruce M. Maggs , Satish B. Rao , Arnold L. Rosenberg , Eric J. Schwabe, Work-preserving emulations of fixed-connection networks, Journal of the ACM (JACM), v.44 n.1, p.104-147, Jan. 1997
	Umakishore Ramachandran , Rajnish Kumar , Matthew Wolenetz , Brian Cooper , Bikash Agarwalla , Junsuk Shin , Phillip Hutto , Arnab Paul, Dynamic data fusion for future sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.3, p.404-443, August 2006
	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
	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
	H. Jung , L. Kirousis , P. Spirakis, Lower bounds and efficient algorithms for multiprocessor scheduling of dags with communication delays, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.254-264, June 18-21, 1989, Santa Fe, New Mexico, United States
	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