A quantitative comparison of parallel computation models

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A quantitative comparison of parallel computation models

Full text

Pdf (1.13 MB)

Source

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

Padua, Italy

Pages: 13 - 24

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Ben H. H. Juurlink	High Performance Computing Division, Department of Computer Science, Leiden University, P,O. Box 9512, 2300 RA Leiden, The Netherlands
Harry A. G. Wijshoff	High Performance Computing Division, Department of Computer Science, Leiden University, P,O. Box 9512, 2300 RA Leiden, The Netherlands

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): 5, Downloads (12 Months): 29, Citation Count: 6

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/237502.241604 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	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]
	3	Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
	4	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 [doi>10.1145/215399.215427]
	5	K.E. Batcher. Sorting networks and their applications. In Proc. AFIPS Spring Joint Computer Conference, pages 307-314, 1968.
	6	R.H. Bissehng and W.F. McColl. Scientific Computing on Bulk Synchronous Parallel Architectures. Technical Report 836, University of Utrecht, December 1993.
	7	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
	8	T. Cheatham , A. Fahmy , D. C. Stefanescu , L. G. Valiant, Bulk synchronous parallel computing-a paradigm for transportable software, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.268, January 04-07, 1995
	9	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, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	10	A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
	11	D.E. Culler, A C Dusseau, R.P. Martin, and K.E. Schauser. Fast Parallel Sorting under LogP: from Theory to Practice. In T. Hey and J. Ferrante, editors, Portabihty and Performance for Parallel Processing. Wiley, 1994.
	12	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]
	13	Hong Jia-Wei , H. T. Kung, I/O complexity: The red-blue pebble game, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.326-333, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802486]
	14	Joseph F. JáJá , Kwan Woo Ryu, The block distributed memory model, University of Maryland at College Park, College Park, MD, 1994
	15	B. H. H. Juurlink , H. A. G. Wijshoff, Experiences with a model for parallel computation, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.87-96, August 15-18, 1993, Ithaca, New York, United States [doi>10.1145/164051.164064]
	16	Ben H. H. Juurlink , Harry A. G. Wijshoff, Communication primitive for BSP computers, Information Processing Letters, v.58 n.6, p.303-310, June 24, 1996 [doi>10.1016/0020-0190(96)00073-7]
	17	B.H.H. Juurlink and H.A.G. Wijshoff. The E-BSP Model: Incorporating Unbalanced Communication and General Locality into the BSP Model. Technical Report 95-44, Leiden University, 1995.
	18	B.H.H. Juurlink and H.A.G. Wijshoff. A Quantitative Comparison of Parallel Computation Models. Technical Report 96-01, Leiden University, 1996.
	19	W. F. McColl, Special purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
	20	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]

CITED BY 6

	Micah Adler , Phillip B. Gibbons , Vijaya Ramachandran , Yossi Matias, Modeling parallel bandwidth: local vs. global restrictions, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.94-105, June 23-25, 1997, Newport, Rhode Island, United States
	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
	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
	Ben Juurlink , Petr Kolman , Friedhelm Meyer auf der Heide , Ingo Rieping, Optimal broadcast on parallel locality models, Journal of Discrete Algorithms, v.1 n.2, p.151-166, April 2003
	Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas, Portable and Efficient Parallel Computing Using the BSP Model, IEEE Transactions on Computers, v.48 n.7, p.670-689, July 1999
	David A. Bader , Bernard M. E. Moret , Peter Sanders, Algorithm engineering for parallel computation, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002