Efficient Schemes for Parallel Communication

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient Schemes for Parallel Communication

Full text

Pdf (636 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 3 (July 1984) table of contents

Pages: 507 - 517

Year of Publication: 1984

ISSN:0004-5411

Author

Eli Upfal

Instttute of Mathematics and Computer Science, The Hebrew Umversity, Jerusalem, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 47, Citation Count: 37

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/828.1892 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	R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
	2	ANGLUIN~ D., AND VALIANT, L. G.Fast probabilistic algorithm for Hamiltonian ciremts and matchlngs. J Comp S);st Sct 12, 6 (1979), 155-193.
	3	C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
	4	A. Borodin , J. E. Hopcroft, Routing, merging and sorting on parallel models of computation, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.338-344, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802209]
	5	CHERNOFF, H A measure of asymptotic efficiency for tests of hypothesis based on the sum of observattons. Ann Math Star 23 (1952), 493-507.
	6	HOEFFDING, W.On the d~stnbution of the number of successes in independent trials. Ann Math. Star 27 (1956), 713-721.
	7	MASSON, G. M., GINGHER, G. C., AND NAKAMURA, S.A sample of circuit switching networks. Computer 18 (June 1979), 32-48.
	8	Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
	9	RABIN, M. O.Probabihstic algorithms. In Algorithm and Complemty, J. F. Taub, ed. Academic Press, New York, 1976.
	10	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.10-16, December 1983 [doi>10.1145/800061.808727]
	11	Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
	12	SIEGEL, H. J.lnterconnection networks for SIMD machines. Computer 18 (June 1979), 57-65.
	13	SOLOVAY~ R, AND STRASSEN, V.Fast Monte-Carlo test for primality. SIAM J. Cornput. 6 (1977), 84-85.
	14	VALIANT. L. G.A scheme for fast parallel communication. SIAM J Comput. 11 (t982), 350-- 361.
	15	L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
	16	VALIANT, U G. Optimahty of two-phase strategy for routing in mterconnection networks. Res. Rep. TR- 15-82, AJken Computation Lab., Harvard Umv., Cambridge, Mass., 1982.

CITED BY 37

	S. A. Felperin , L. Gravano , G. D. Pifarré , J. L. C. Sanz, Fully-adaptive routing: packet switching performance and wormhole algorithms, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.654-663, November 18-22, 1991, Albuquerque, New Mexico, United States
	M. Dietzfelbinger , F. Meyer auf der Heide, An optimal parallel dictionary, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.360-368, June 18-21, 1989, Santa Fe, New Mexico, United States
	Allan Borodin , Prabhakar Raghavan , Baruch Scheiber , Eli Upfal, How much can hardware help routing?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.573-582, May 16-18, 1993, San Diego, California, United States
	Eli Upfal, A probabilistic relation between desirable and feasible, models of parallel computation, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.258-265, December 1984
	A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States
	M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States
	Danny Krizanc , David Peleg , Eli Upfal, A time-randomness tradeoff for oblivious routing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.93-102, May 02-04, 1988, Chicago, Illinois, United States
	Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada
	C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece
	Yukon Chang , Janos Simon, Continuous routing and batch routing on the hypercube, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.272-281, August 11-13, 1986, Calgary, Alberta, Canada
	Eli Upfal , Sergio Feleprin , Marc Snir, Randomized routing with shorter paths, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.283-292, June 30-July 02, 1993, Velen, Germany
	Allan Borodin , Prabhakar Raghavan , Baruch Schieber , Eli Upfal, How much can hardware help routing?, Journal of the ACM (JACM), v.44 n.5, p.726-741, Sept. 1997
	Andrei Z. Broder , Alan M. Frieze , Eli Upfal, A general approach to dynamic packet routing with bounded buffers, Journal of the ACM (JACM), v.48 n.2, p.324-349, March 2001
	Anna R. Karlin , Eli Upfal, Parallel hashing: an efficient implementation of shared memory, Journal of the ACM (JACM), v.35 n.4, p.876-892, Oct. 1988
	G. Mohan , G. Venkatesan , C. Siva Ram Murthy, Randomized routing and wavelength requirements in wavelength-routed WDM multistage, hypercube, and de Bruijn networks, Journal of Parallel and Distributed Computing, v.64 n.3, p.385-399, March 2004
	Eli Upfal , Sergio Felperin , Marc Snir, Randomized Routing with Shorter Paths, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.356-362, April 1996
	D. Peleg , E. Upfal, Constructing disjoint paths on expander graphs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.264-273, January 1987, New York, New York, United States
	Berthold Vöcking, Almost optimal permutation routing on hypercubes, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.530-539, July 2001, Hersonissos, Greece
	Qian-Ping Gu , Jun Gu, Two Packet Routing Algorithms on a Mesh-Connected Computer, IEEE Transactions on Parallel and Distributed Systems, v.6 n.4, p.436-440, April 1995
	George D. Stamoulis , John N. Tsitsiklis, The efficiency of greedy routing in hypercubes and butterflies, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.248-259, July 21-24, 1991, Hilton Head, South Carolina, United States
	Mor Harchol-Balter , David Wolfe, Bounding delays in packet-routing networks, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.248-257, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, Simple, efficient shared memory simulations, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.110-119, June 30-July 02, 1993, Velen, Germany
	Hussein M. Alnuweiri , V. K. Prasanna Kumar, Optimal VLSI Sorting with Reduced Number of Processors, IEEE Transactions on Computers, v.40 n.1, p.105-110, January 1991
	Emmanouel A. Varvarigos , Dimitri P. Bertsekas, Performance of hypercube routing schemes with or without buffering, IEEE/ACM Transactions on Networking (TON), v.2 n.3, p.299-311, June 1994
	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990
	Sergio Felperin , Prabhakar Raghavan , Eli Upfal, A Theory of Wormhole Routing in Parallel Computers, IEEE Transactions on Computers, v.45 n.6, p.704-713, June 1996
	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, ACM Computing Surveys (CSUR), v.28 n.1, p.33-37, March 1996
	Bruce M. Maggs , Ramesh K. Sitaraman, Simple algorithms for routing on butterfly networks with bounded queues, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.150-161, May 04-06, 1992, Victoria, British Columbia, Canada
	Nir Shavit , Eli Upfal , Asaph Zemach, A wait-free sorting algorithm, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.121-128, August 21-24, 1997, Santa Barbara, California, United States
	P. J. Bernhard , D. J. Rosenkrantz, Partitioning Message Patterns for Bundled Omega Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.353-363, April 1994
	Suprakash Datta , Ramesh Sitaraman, The performance of simple routing algorithms that drop packets, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.159-169, June 23-25, 1997, Newport, Rhode Island, United States
	Leslie Ann Goldberg , Yossi Matias , Satish Rao, An optical simulation of shared memory, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.257-267, June 27-29, 1994, Cape May, New Jersey, United States
	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
	Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking, Randomized protocols for low-congestion circuit routing in multistage interconnection networks, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.378-388, May 24-26, 1998, Dallas, Texas, United States
	G. D. Pifarré , L. Gravano , S. A. Felperin , J. L. C. Sanz, Fully Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes, and other Networks: Algorithms and Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.247-263, March 1994
	Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994
	Michael G. Norman , Peter Thanisch, Models of machines and computation for mapping in multicomputers, ACM Computing Surveys (CSUR), v.25 n.3, p.263-302, Sept. 1993