BSP vs LogP

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

BSP vs LogP

Full text

Pdf (1.00 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: 25 - 32

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Gianfranco Bilardi	Dip. di Elettronica e Informatica, Università di Padova, Italy and Dept. of Electrical Engineering and Computer Science, University of Illinois at Chicago, IL
Kieran T. Herley	Dept. of Computer Science, University College Cork, Cork, Ireland
Andrea Pietracaprina	Dip. di Matematica Pura e Applicata, Università di Padova, Italy
Geppino Pucci	Dip. di Elettronica e Informatica, Università di Padova, Italy
Paul Spirakis	Computer Technology Institute, Patras, Greece

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): 37, Citation Count: 10

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.237504 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.

	ABK95a	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 [doi>10.1145/215399.215431]
	ABK95b	M. Adler, J.W. Byers, and R.M. Karp. Scheduling parallel communication: The h-relation problem. Technical Report TR-95-032, International Computer Science Institute, Berkeley, CA, USA, 1995.
	AISS95	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]
	AKS83	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]
	BB95	Paul Bay , Gianfranco Bilardi, Deterministic on-line routing on area-universal networks, Journal of the ACM (JACM), v.42 n.3, p.614-640, May 1995 [doi>10.1145/210346.210417]
	BGMZ95	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for memory bank contention and delay in high-bandwidth multiprocessors, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.84-94, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215425]
	Bol79	B. Bollobks. Graph theory : an introductory course. Springer-Verlag, New York, NY, 1979.
	BPP96	G. Bilardi, A. Pietracaprina, and G. Pucci. A critical perspective of latency-bandwidth based models. In preparation, 1996.
	BS78	G. Baudet and D. Stevenson. Optimal sorting algorithms for parallel computers. IEEE Trans. on Computers, C-27(1):84-87, January 1978.
	CDMS93	D.E. Culler, A. Dusseau, R. Martin, and K.E. Shauser. Fast parallel sorting under LogP: from theory to practice. In Proc. of the Workshop on Portabd#ty and Performance for Parallel Processors, Southampton, UK, July 1993.
	CFSV95	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
	CKP+93	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
	CS92	Robert Cypher , Jorge L. C. Sanz, Cubesort: A parallel algorithm for sorting N data items with S-sorters, Journal of Algorithms, v.13 n.2, p.211-234, June, 1992 [doi>10.1016/0196-6774(92)90016-6]
	GV92	A.V. Gerbessiotis and L.G. Valiant. Direct bulksynchronous parallel algorithms. Technical Report TR-10-92, Harward University, Cambridge, MA 02138, USA, 1992. Also appeared in 3rd SWAT, 1992.
	HR90	Torben Hagerup , C. Rüb, A guided tour of Chernoff bounds, Information Processing Letters, v.33 n.6, p.305-308, February 1990 [doi>10.1016/0020-0190(90)90214-I]
	KSSS93	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 [doi>10.1145/165231.165250]
	Lei92	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	McC94a	W.F. McColl. BSP programming. In DIMACS Series in D#screte Mathematics. American Mathematical Society, 1994.
	McC94b	W. F. McColl, General purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
	McC94c	W.F. McColl. Scalable parallel computing: A grand unified theory and its practical development. In Proc. 13th IFIP World Computer Congress, 1994.
	SK94	Jop F. Sibeyn , Michael Kaufmann, Deterministic 1-k Routing on Meshes, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.237-248, February 24-26, 1994
	Tho80	Clark David Thompson, A complexity theory for vlsi, 1980
	Val90a	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]
	Val90b	L.G. Valiant General purpose parallel computing. In J Van Leeuwen, editor, Handbook of Theoretzcal Computer Science, volume A, chapter 18, pages 944-996. Elsevier, NL, 1990.
	Val92	Leslie G. Valiant, A Combining Mechanism for Parallel Computers, Proceedings of the First Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, p.1-10, November 11-13, 1992

CITED BY 10

	David B. Skillicorn , Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys (CSUR), v.30 n.2, p.123-169, June 1998
	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP, and LogP: a framework for general-purpose parallel algorithm design, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.957-958, January 17-19, 1999, Baltimore, Maryland, United States
	Sergei Gorlatch, SAT: a programming methodology with skeletons and collective operations, Patterns and skeletons for parallel and distributed computing, Springer-Verlag, London, 2003
	Sergei Gorlatch, Send-receive considered harmful: Myths and realities of message passing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.26 n.1, p.47-56, January 2004
	Sergei Gorlatch, Message passing without send-receive, Future Generation Computer Systems, v.18 n.6, p.797-805, May 2002
	Lixin Gao , Arnold L. Rosenberg , Ramesh K. Sitaraman, Optimal Clustering of Tree-Sweep Computations for High-Latency Parallel Environments, IEEE Transactions on Parallel and Distributed Systems, v.10 n.8, p.813-824, August 1999
	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
	Gianfranco Bilardi , Kieran Herley , Andrea Pietracaprina , Geppino Pucci, On stalling in LogP, Journal of Parallel and Distributed Computing, v.65 n.3, p.307-312, March 2005
	Vijaya Ramachandran , Brian Grayson , Michael Dahlin, Emulations between QSM, BSP and LogP: a framework for general-purpose parallel algorithm design, Journal of Parallel and Distributed Computing, v.63 n.12, p.1175-1192, December 2003
	Alexandros V. Gerbessiotis , Seung-Yeop Lee, Remote memory access: A case for portable, efficient and library independent parallel programming, Scientific Programming, v.12 n.3, p.169-183, August 2004