Towards efficiency and portability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Towards efficiency and portability: programming with the BSP model

Full text

Pdf (1.38 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: 1 - 12

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Mark Goudreau	Department of Computer Science, University of Central Florida, Orlando, FL
Kevin Lang	NEC Research Institute, 4 Independence Way, Princeton, NJ
Satish Rao	NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CA
Torsten Suel	NEC Research Institute, 4 Independence Way, Princeton, NJ and University of California at Berkeley, Berkeley, CA
Thanasis Tsantilas	Department of Computer Science, Columbia University, New York, NY

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): 3, Downloads (12 Months): 32, Citation Count: 17

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.237503 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	Micah Adler , John W. Byers , Richard M. Karp, Scheduling Parallel Communication: The h-relation Problem, Proceedings of the 20th International Symposium on Mathematical Foundations of Computer Science, p.1-20, August 28-September 01, 1995
	2	Amotz Bar-Noy , Shlomo Kipnis, Designing broadcasting algorithms in the postal model for message-passing systems, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.13-22, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140903]
	3	J. Barnes and P. Hut. A hierarchical O(NtogN) force-calculation algorithm. Nature, 324(4):446-449, 1986.
	4	Armin Bäumker , Wolfgang Dittrich , Friedhelm Meyer auf der Heide, Truly efficient parallel algorithms: 1-optimal multisearch for an extension of the BSP model, Selected papers from the third European symposium on Algorithms, p.175-203, August 1998, Courfu, Greece
	5	R. H. Bisseling. Sparse matrix computations on bulk synchronous parallel computers, in Proc. Int. Conf on Industrial and Applied Math., July 1995.
	6	R. H. Bisseling and W. F. McColl. Scientific computing on bulk synchronous parallel architectures. In B. Pehrson and I. Simon, editors, Proc. 13th IFIP World Computer Congress, volume 1, pages 509-514. Elsevier, 1994.
	7	J. Cartier, L. Greengard, and V. Rokhlin. A fast adaptive multipole algorithm for particle simulations. SlAM J. on Scientific and Statistical Computing, 9(4):669-686, July 1988.
	8	T. Cheatham, A. Fahmy, and D. Stefanescu. General purpose optimization technology. Tech. report, Center for Research in Computing Technology, Harvard University, Dec. 1994.
	9	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
	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	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
	12	Al Geist , Adam Beguelin , Jack Dongarra , Weicheng Jiang , Robert Manchek , Vaidy Sunderam, PVM: Parallel virtual machine: a users' guide and tutorial for networked parallel computing, MIT Press, Cambridge, MA, 1995
	13	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct bulk-synchronous parallel algorithms, Journal of Parallel and Distributed Computing, v.22 n.2, p.251-267, Aug. 1994 [doi>10.1006/jpdc.1994.1085]
	14	A.V. Goldberg, K. Lang, and S. Rap. Computing minimum spanning. tree with the Green BSP library. In preparation, April 1996.
	15	M. Goudreau, K. Lang, S. Rap, and T. Tsantilas. The Green BSP library. Tech. Report CR-TR-95-11, University of Central Florida, 1995.
	16	William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI: portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1994
	17	Pat Hanrahan , David Salzman , Larry Aupperle, A rapid hierarchical radiosity algorithm, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.197-206, July 1991
	18	S. Knee. Program development and performance prediction on BSP machines using Opal. Technical Report PRG-TR-18-94, Oxford University Computing Laboratory, Aug. 1994.
	19	Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
	20	D. Lecomber. An object-oriented programming model for BSP computations. Tech. Report, Oxford Unwersity Computing Laboratory, 1994.
	21	C. Leiserson and B. M. Maggs. Communieation-efficientparallel algorithms for distributed random-access machines. Algorithmics, 3:53-77, 1988.
	22	Pangfeng Liu , William Aiello , Sandeep Bhatt, An atomic model for message-passing, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.154-163, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165251]
	23	Pangfeng Liu , Sandeep N. Bhatt, Experiences with parallel N-body simulation, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.122-131, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181081]
	24	B. M. Maggs , L. R. Matheson , R. E. Tarjan, Models of parallel computation: a survey and synthesis, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.61, January 04-07, 1995
	25	W. F. McColl, General purpose parallel computing, Lectures on parallel computation, Cambridge University Press, New York, NY, 1993
	26	W. E McColl. BSP programming. In G.E. Blelloch, K.M. Chandy, and S. Jagannathan, editors, Proc. DIMACS Workshop on Specification of Parallel Algorithms, pages 21-35 American Math. Soc. May 1994.
	27	Richard Miller. A library for bulk-synchronous parallel programming. In Proc. of the Brttish Computer Society Parallel Processing Specialist Group Workshop on General Purpose Parallel Computing, Dec. 1993.
	28	M. Nibhanupudi, C. Norton, and B. Szymanski. Plasma simulation on networks of workstations using the bulk synchronous parallel model. In Proc. Int. Cony on Parallel and Distributed Processing Techniques and Applications, Nov. 1995.
	29	J. P. Singh. Data locality and memory system performance in the parallel simulation of ocean eddy currents. In Proc. 2nd Int. Symp. on High Performance Computmg, Oct. 1991.
	30	Jaswinder Pal Singh , Anoop Gupta , Marc Levoy, Parallel Visualization Algorithms: Performance and Architectural Implications, Computer, v.27 n.7, p.45-55, July 1994 [doi>10.1109/2.299410]
	31	Jaswinder P Singh , Wolf Weber , Anoop Gupta, SPLASH: Stanford parallel applications for shared-memory*, Stanford University, Stanford, CA, 1992
	32	T. Suel. Programming Parallel N-Body Simulations with the Bulk- Synchronous Parallel Model. In preparation, April 1996.
	33	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	34	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]
	35	L. G. Valiant. Why BSP computers? In Proc. 7th Int. Parallel Processmg Syrup., pages 2-5. IEEE Press, April 1993.
	36	Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia
	37	M. S. Warren , J. K. Salmon, Astrophysical N-body simulations using hierarchical tree data structures, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.570-576, November 16-20, 1992, Minneapolis, Minnesota, United States

CITED BY 17

	Mark W. Goudreau , Kevin Lang , Girija Narlikar , Satish B. Rao, BOS is boss: a case for bulk-synchronous object systems, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.115-125, June 27-30, 1999, Saint Malo, France
	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
	Bruce M. Maggs , Berthold Vöcking, Improved routing and sorting on multibutterflies, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.517-530, May 04-06, 1997, El Paso, Texas, 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
	Steven Phillips , Anne Rogers, Parallel Speech Recognition, International Journal of Parallel Programming, v.27 n.4, p.257-288, Aug. 1999
	David Skillicorn , Susanna Pelagatti, Building programs in the network of tasks model, Proceedings of the 2000 ACM symposium on Applied computing, p.248-254, March 2000, Como, Italy
	Sergei Gorlatch, SAT: a programming methodology with skeletons and collective operations, Patterns and skeletons for parallel and distributed computing, Springer-Verlag, London, 2003
	Curtis Lisle , Rebecca Parsons, Recursive, object-oriented structures for molecular modeling, Proceedings of the 1998 ACM symposium on Applied Computing, p.50-54, February 27-March 01, 1998, Atlanta, Georgia, United States
	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
	Frank Dehne , Todd Eavis , Susanne Hambrusch , Andrew Rau-Chaplin, Parallelizing the Data Cube, Distributed and Parallel Databases, v.11 n.2, p.181-201, March 2002
	David Blackston , Torsten Suel, Highly portable and efficient implementations of parallel adaptive N-body methods, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 15-21, 1997, San Jose, CA
	Sergei Gorlatch, Message passing without send-receive, Future Generation Computer Systems, v.18 n.6, p.797-805, May 2002
	Thierry Garcia , David Semé, A Coarse-Grained multicomputer algorithm for the detection of repetitions, Information Processing Letters, v.93 n.6, p.307-313, 31 March 2005
	Assefaw Hadish Gebremedhin , Isabelle Guérin Lassous , Jens Gustedt , Jan Arne Telle, Graph coloring on coarse grained multicomputers, Discrete Applied Mathematics, v.131 n.1, p.179-198, 6 September 2003
	Guy E. Blelloch , Phillip B. Gibbons , Yossi Matias , Marco Zagha, Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.8 n.9, p.943-958, September 1997
	David Skillicorn, Strategies for Parallel Data Mining, IEEE Concurrency, v.7 n.4, p.26-35, October 1999
	Curtis Lisle , Rebecca Parsons, Recursive, object-oriented structures for molecular modeling, ACM SIGBIO Newsletter, v.18 n.1, p.2-8, April 1, 1998