Hot-potato routing on processor arrays

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Hot-potato routing on processor arrays

Full text

Pdf (1.20 MB)

Source

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

Velen, Germany

Pages: 273 - 282

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

Christos Kaklamanis	DIMACS Center Rutgers University Piscataway, NJ
Danny Krizanc	School of Computer Science Carleton University Ottawa, Ontario K1S 5B6
Satish Rao	NEC Research Institute, 4 Independence Way, Princeton, NJ

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 15, Citation Count: 12

Additional Information:

references cited by 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/165231.376321 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. Acampora and S. Shah. Multihop Iightwave networks: a comparison of store and forward and hotpotato routing. In IEEE INFOCOM, pages 10-19, 1991.
	2	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	3	U. Feige and P. Raghavan. Exact analysis of hotpotato routing, in Symposium on the Foundations of Computer Science, pages 553-562. IEEE, 1992.
	4	U. Felperin, P. Raghavan, and E. Upfal. A theory of wormhole routing in parMlel computers. In Symposium on the Foundations of Computer Science, pages 563-572. IEEE, 1992.
	5	A. Greenberg and J. Goodman. Sharp approximate models of deflection routing in mesh networks. IEEE Transactions on Computers, 1993. to appear.
	6	A. Greenberg and B. Hajek. Deflection routing in hypercube networks. IEEE Transactions on Computers, 1993. to appear.
	7	B. Hajek, Bounds on evacuation time for deflection routing, Distributed Computing, v.5 n.1, p.1-6, June 1991 [doi>10.1007/BF02311228]
	8	W D Hillis, The connection machine, MIT Press, Cambridge, MA, 1985
	9	Christos Kaklamanis , Danny Krizanc , Satish Rao, Simple path selection for optimal routing on processor arrays, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.23-30, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.140904]
	10	D. Lawrie and D. Padua. Analysis of message switching with shuffle-exchanges in multiprocessors. In Interconnection Networks. IEEE Computer Society Press, 1984.
	11	T. Leighton, B. Maggs, and S. Rao. Universal packet routing algorithms. In Symposium on the Foundations of Computer Science, pages 256-269, 1988.
	12	T. Leighton , F. Makedon , I. G. Tollis, A 2n-2 step algorithm for routing in an nxn array with constant size queues, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.328-335, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72970]
	13	N. Maxemchuk. Comparison of deflection and store and forward techniques in the manahattan street and shuffle-exchange networks. In IEEE INFO- COM, pages 800-809, 1989.
	14	i. Newman and A. Schuster. Hot-potato algorithms for permutation routing. Technical Report CS- LPCR 9201, Technion, 1992.
	15	R. Prager. An algorithm for routing in hypercube networks. M.S. thesis, U. of Toronto, 1986.
	16	D. Krizanc , S. Rajasekaran , T. Tsantilas, Optimal routing algorithms for mesh-connected processor arrays (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	17	B. Smith. Architecture and applications of the hep multiprocessor computer system. In Real Time Signal Processing, pages 241-248, 1981.
	18	L. Valiant. A scheme for fast parallel communication. SIAM Journal of Computing, 11:350-361, 1982.

CITED BY 12

	Stephen Alstrup , Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Direct routing on trees, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.342-349, January 25-27, 1998, San Francisco, California, United States
	Amir Ben-Dor , Shai Halevi , Assaf Schuster, Potential function analysis of greedy hot-potato routing, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.225-234, August 14-17, 1994, Los Angeles, California, United States
	Costas Busch , Maurice Herlihy , Roger Wattenhofer, Randomized greedy hot-potato routing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.458-466, January 09-11, 2000, San Francisco, California, United States
	Donald D. Chinn , Tom Leighton , Martin Tompa, Minimal adaptive routing on the mesh with bounded queue size, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.354-363, June 27-29, 1994, Cape May, New Jersey, United States
	Costas Busch , Maurice Herlihy , Roger Wattenhofer, Routing without flow control, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.11-20, July 2001, Crete Island, Greece
	Costas Busch , Maurice Herlihy , Roger Wattenhofer, Hard-Potato routing, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.278-285, May 21-23, 2000, Portland, Oregon, United States
	Ilan Newman , Assaf Schuster, Hot-Potato Algorithms for Permutation Routing, IEEE Transactions on Parallel and Distributed Systems, v.6 n.11, p.1168-1176, November 1995
	Micah Adler , Ramesh K. Sitaraman , Arnold L. Rosenberg , Walter Unger, Scheduling time-constrained communication in linear networks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.269-278, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Allan Borodin , Yuval Rabani , Baruch Schieber, Deterministic Many-to-Many Hot Potato Routing, IEEE Transactions on Parallel and Distributed Systems, v.8 n.6, p.587-596, June 1997
	Uriel Feige , Robert Krauthgamer, Networks on which hot-potato routing does not livelock, Distributed Computing, v.13 n.1, p.53-58, January 2000
	Costas Busch, Õ(congestion + dilation) hot-potato routing on leveled networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Costas Busch , Malik Magdon-Ismail , Marios Mavronicolas, Efficient bufferless packet switching on trees and leveled networks, Journal of Parallel and Distributed Computing, v.67 n.11, p.1168-1186, November, 2007

Collaborative Colleagues:

Christos Kaklamanis: colleagues

Danny Krizanc: colleagues

Satish Rao: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player