Modeling parallel bandwidth

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Modeling parallel bandwidth: local vs. global restrictions

Full text

Pdf (1.65 MB)

Source

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

Newport, Rhode Island, United States

Pages: 94 - 105

Year of Publication: 1997

ISBN:0-89791-890-8

Authors

Micah Adler	Heinz Nixdorf Institute, Room F1-119, Fürstenallee 11, D-33102, Paderborn, Germany
Phillip B. Gibbons	Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ
Vijaya Ramachandran	Dept. of Computer Sciences, University of Texas at Austin, Austin, TX
Yossi Matias	Bell Laboratories, Lucent Technologies, 600 Mountain Ave., Murray Hill, NJ

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): 2, Downloads (12 Months): 13, Citation Count: 4

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/258492.258502 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	M. Adler, New coding techniques for improved bandwidth utilization, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.173, October 14-16, 1996
	2	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]
	3	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]
	4	A. Fernandez, Universal stability results for greedy contention-resolution protocols, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.380, October 14-16, 1996
	5	Yossi Azar, Lower bounds for threshold and symmetric functions in parallel computation, SIAM Journal on Computing, v.21 n.2, p.329-338, April 1992 [doi>10.1137/0221024]
	6	David A. Bader , Joseph JáJá, Practical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selection, Proceedings of the 10th International Parallel Processing Symposium, p.292-301, April 15-19, 1996
	7	Vasanth Bala , Jehoshua Bruck , Robert Cypher , Pablo Elustando , Alex Ho , Ching-Tien Ho , Shlomo Kipnis , Marc Snir, CCL: A Portable and Tunable Collective Communication Library for Scalable Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.154-164, February 1995 [doi>10.1109/71.342126]
	8	Amotz Bar-Noy , Jehoshua Bruck , Ching-Tien Ho , Shlomo Kipnis , Baruch Schieber, Computing Global Combine Operations in the Multiport Postal Model, IEEE Transactions on Parallel and Distributed Systems, v.6 n.8, p.896-900, August 1995 [doi>10.1109/71.406965]
	9	Armin Baumker , Wolfgang Dittrich, Fully dynamic search trees for an extension of the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.233-242, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237562]
	10	Paul Beame , Johan Hastad, Optimal bounds for decision problems on the CRCW PRAM, Journal of the ACM (JACM), v.36 n.3, p.643-670, July 1989 [doi>10.1145/65950.65958]
	11	Sandeep N. Bhatt , Gianfranco Bilardi , Geppino Pucci , Abhiram Ranade , Arnold L. Rosenberg , Eric J. Schwabe, On Bufferless Routing of Variable Length Messages in Leveled Networks, IEEE Transactions on Computers, v.45 n.6, p.714-729, June 1996 [doi>10.1109/12.506427]
	12	R.H. Bisseling and W.F. McColl. Scientific computing on bulk synchronous parallel architectures. In Proc. 133th IFIP World Computer Congress, pages 509-514, 1994.
	13	Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queueing theory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.376-385, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237984]
	14	Jehoshua Bruck , Ching-Tien Ho , Shlomo Kipnis , Derrick Weathersby, Efficient algorithms for all-to-all communications in multi-port message-passing systems, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181756]
	15	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
	16	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	17	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
	18	D. E. Culler, A. Dusseau, R. Martin, and K. E. Schauser. Fast parallel sorting under LogP: from theory to practice. In Proc. Workshop on Portability and Performance for Parallel Processing, Southhampton, England, July 1993.
	19	Pilar de la Torre , Clyde P. Kruskal, Submachine Locality in the Bulk Synchronous Setting (Extended Abstract), Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.352-358, August 26-29, 1996
	20	S. Felperin, P. Raghavan, and E. Upfal. A theory of wormhole routing in parallel computers. In Proc. 33rd IEEE Symp. on Foundations of Computer Science, 1992.
	21	Alexandros V. Gerbessiotis , Constantinos J. Siniolakis, Deterministic sorting and randomized median finding on the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.223-232, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237561]
	22	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 [doi>10.1145/258492.258500]
	23	Leslie Ann Goldberg , Philip D. MacKenzie, Analysis of practical backoff protocols for contention resolution with multiple servers, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.554-563, January 28-30, 1996, Atlanta, Georgia, United States
	24	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	25	Mark Goudreau , Kevin Lang , Satish Rao , Torsten Suel , Thanasis Tsantilas, Towards efficiency and portability: programming with the BSP model, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.1-12, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237503]
	26	Himanshu Gupta , P. Sadayappan, Communication efficient matrix multiplication on hypercubes, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.320-329, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181434]
	27	David R. Helman , David A. Bader , Joseph JáJá, Parallel algorithms for personalized communication and sorting with an experimental study (extended abstract), Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.211-222, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237558]
	28	Susan Hinrichs , Corey Kosak , David R. O'Hallaron , Thomas M. Stricker , Riichiro Take, An architecture for optimal all-to-all personalized communication, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.310-319, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181427]
	29	Arun K. Jagota, A near-optimal algorithm for gossiping in a d-dimensional mesh bus interconnection network, Proceedings of the 9th International Symposium on Parallel Processing, p.331, April 25-28, 1995
	30	Joseph F. JáJá , Kwan Woo Ryu, The block distributed memory model, University of Maryland at College Park, College Park, MD, 1994
	31	S. Lennart Johnsson , Ching-Tien Ho, Optimum Broadcasting and Personalized Communication in Hypercubes, IEEE Transactions on Computers, v.38 n.9, p.1249-1268, September 1989 [doi>10.1109/12.29465]
	32	B H. H. Juurlink. Ph.D. Thesis, Leiden University, 1996.
	33	Ben H. H. Juurlink , Harry A. G. Wijshoff, The E-BSP Model: Incorporating General Locality and Unbalanced Communication into the BSP Model, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.339-347, August 26-29, 1996
	34	Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
	35	C. E. Leiserson and B. M. Maggs. Communicationefficient parallel algorithms for distributed random-access machines. Algorithmica, 3(1):53-77, 1988.
	36	Y.-D. Lyuu and E. Schenfeld. Total exchange on a reconfigurable parallel architecture. In Proc. 5th IEEE S Ymp. on Parallel and Distributed Processing, pages 2- 10, December 1993.
	37	Yishay Mansour , Noam Nisan , Uzi Vishkin, Trade-offs between communication throughput and parallel time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.372-381, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195199]
	38	Ft. Miller. A library for bulk-synchronous parallel programming. In Proc. oct the British Computer Society Parallel Processsing, Specialist Group Workshop on General Purpose Parallel Computing, December 1993.
	39	Prabhakar Raghavan , Eli Upfal, Stochastic contention resolution with short delays, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.229-237, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225129]
	40	Satish Rao , Torsten Suel , Thanasis Tsantilas , Mark Goudreau, Efficient communication using total-exchange, Proceedings of the 9th International Symposium on Parallel Processing, p.544-550, April 25-28, 1995
	41	Yu-Chee Tseng , Sandeep K. S. Gupta, All-to-All Personalized Communication in a Wormhole-Routed Torus, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.498-505, May 1996 [doi>10.1109/71.503775]
	42	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]
	43	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	44	U. Vishkin and A. Wigderson. Trade-offs between depth and width in parallel computation. In SlAM Journal of Computing, volume 14(2), pages 303 - 314, 1985.
	45	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 [doi>10.1145/237502.241604]

CITED BY 4

	Micah Adler , Tom Leighton, Compression using efficient multicasting, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.153-162, May 21-23, 2000, Portland, Oregon, United States
	Philip D. MacKenzie , Vijaya Ramachandran, Computational bounds for fundamental problems on general-purpose parallel models, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.152-163, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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