On the benefit of supporting virtual channels in wormhole routers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the benefit of supporting virtual channels in wormhole routers

Full text

Pdf (1.32 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: 131 - 141

Year of Publication: 1996

ISBN:0-89791-809-6

Authors

Richard J. Cole	Courant Institute, New York University, New York, NY
Bruce M. Maggs	School of Computer Science, Carnegie Mellon University, Pittsburgh, PA
Ramesh K. Sitaraman	Dept. of Computer Science, University of Massachusetts, Amherst, MA

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: 5

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.237517 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	W. A Aiello, F. T Leighton, B. I#I. Maggs, and M. Newman. Fast algorithms for bit-serial routing on a hypercube. Mathematical ,5'gstems Theorg, 24(4):253- 271. 1991.
	2	N. Alon. A parallel algorithmic version of the Local Lemma. Random ,5"truc't#ree and Atgorzthms, 2(4):367- 378, 1991.
	3	S. Arora , T. Leighton , B. Maggs, On-line algorithms for path selection in a nonblocking network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.149-158, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100232]
	4	ButterflyTM Parallel Processor Overview. BBN Report No. 6148, Version 1. BBN Advanced ('omputers, Inc., Cambridge, 5IA, March 1986.
	5	.J Beck. An algorithmic approach to the Lov#isz Local Lemma I. Random 5'tructures and Algorithms, 2(4)'343-36,5, 1991.
	6	B. Beizer. The analysis and synthesis of signal switching networks. In Proceedings of the Stlrnpos#um on Mathematical Theory of Automata, pages 563-576, Brooklyn, NY, 1962. Brooklyn Polytechnic Instimt, e,
	7	V. E. Bene#. Optimal rearrangeable multistage connecting networks. Bell S'#ystem Yechn, zcal Journal, 43.t641- 16,56, July 1964.
	8	S. Borkar , R. Cohn , G. Cox , S. Gleason , T. Gross, Warp: an integrated solution of high-speed parallel computing, Proceedings of the 1988 ACM/IEEE conference on Supercomputing, p.330-339, November 12-17, 1988, Orlando, Florida, United States
	9	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]
	10	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 [doi>10.1145/167088.167237]
	11	R. Cypher, Minimal, deadlock-free routing in hypercubic and arbitrary networks, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.122, October 25-28, 1995
	12	Robert Cypher , Luis Gravano, Storage-Efficient, Deadlock-Free Packet Routing Algorithms for Torus Networks, IEEE Transactions on Computers, v.43 n.12, p.1376-1385, December 1994 [doi>10.1109/12.338097]
	13	Robert Cypher , Friedhelm Meyer auf der Heide , Christian Scheideler , Berthold Vöcking, Universal algorithms for store-and-forward and wormhole routing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.356-365, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237982]
	14	W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
	15	William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
	16	W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
	17	W. J. Dally" and C. L. Seitz. The Torus Routing Chip. Dzstr#buted Comput,ng, 1(4)'187-196, 1986.
	18	S. Felperin, P. Raghavan, and E. Upfal. A theory of wormhole routing in parallel computers. In Proceed- #nys of the 33rd Annual Symposzum on Foundatzons of Computer Science, pages 563-572, October 1992.
	19	R. Greenberg and H.-C. Oh. Universal wormhole routing. In Procee&ngs of the 5th {EEE Symposium on Parallel and D,stmbuted Processzn9, pages 56-63, December 1993.
	20	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 [doi>10.1145/97444.97453]
	21	P. Kermani and L. Kleinrock. Virtual cut-through a new computer communications switching technique. Computer Networks, 3(4):267-286, 1979.
	22	R. R. Koch. Increasing the size of a network by a constant factor can increase performance by more than a constant factor. In Procee&ngs of the 29th Annual Symposium on Foundations of Computer Science, pages '2'21-230. IEEE Computer Society Press, October 1988.
	23	R. K. Koeninger, M. Furtney, and M. Walker. A shared MPP from Cray research. Dt9#tal Technical Journal, 6(2):8-21, Spring 1994.
	24	C. P. I(ruskal and M. Snir. The performance of multistage intzerconnection networks for mukiprocessors. IEEE Transactions on Computers, C-32(12)'1091- 1098, December 1983.
	25	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	26	F. T. Leighton , Bruce M. Maggs , Abhiram G. Ranade , Satish B. Rao, Randomized routing and sorting on fixed-connection networks, Journal of Algorithms, v.17 n.1, p.157-205, July 1994 [doi>10.1006/jagm.1994.1030]
	27	F. T. Leighton, B. M. Maggs, and S. B. Rao. Packet routing and job-shop scheduling m O(congestion + dilation) steps. Cornbinatorica, 14('2):167-180, 1994.
	28	Tom Leighton, Methods for message routing in parallel machines, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.77-96, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129721]
	29	T. Leighton , B. Maggs, Fast algorithms for finding O(congestion+dilation) packet routing schedules, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.555, January 04-07, 1995
	30	Charles E. Leiserson , Zahi S. Abuhamdeh , David C. Douglas , Carl R. Feynman , Mahesh N. Ganmukhi , Jeffrey V. Hill , Daniel Hillis , Bradley C. Kuszmaul , Margaret A. St. Pierre , David S. Wells , Monica C. Wong , Shaw-Wen Yang , Robert Zak, The network architecture of the Connection Machine CM-5 (extended abstract), Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.272-285, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141883]
	31	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 [doi>10.1145/129712.129728]
	32	Yishay Mansour , Boaz Patt-Shamir, Greedy packet scheduling on shortest paths, Journal of Algorithms, v.14 n.3, p.449-465, May 1993 [doi>10.1006/jagm.1993.1024]
	33	P. M. Merlin and P. J. Schweitzer. Deadlock avoidance in store-and-forward networks. 1 Store-and-forward deadlock. IEEE Transactions on Communications, 28-345-354, 1980.
	34	F. Meyer auf der Heide and B. Vgcking. A packet routing protocol for arbitrary networks In Procee&ngs of the 12th Symposium on Theoretical Aspects of Computer Science, pages 291-302, #Iarch 1995.
	35	Michael D. Noakes , Deborah A. Wallach , William J. Dally, The J-machine multicomputer: an architectural evaluation, Proceedings of the 20th annual international symposium on Computer architecture, p.224-235, May 16-19, 1993, San Diego, California, United States
	36	Gustavo D. Pifarré , Luis Gravano , Sergio A. Felperin , Jorge L. C. Sanz, Fully-adaptive minimal deadlock-free packet routing in hypercubes, meshes, and other networks, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.278-290, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113405]
	37	A. Ranade, S. Schleimer, and D. S. Wilkerson. Nearly" tight bounds for wormhole routing. In Proceedings of the 35th Annual Symposzum on Foundations of Computer Science, 1994.
	38	Christian Scheideler , Berthold Vöcking, Universal continuous routing strategies, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.142-151, June 24-26, 1996, Padua, Italy [doi>10.1145/237502.237519]
	39	C. L. Seitz , W. C. Athas , C. M. Flaig , A. J. Martin , J. Seizovic , C. S. Steele , W-K. Su, The architecture and programming of the Ametek series 2010 multicomputer, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.33-37, January 19-20, 1988, Pasadena, California, United States [doi>10.1145/62297.62302]
	40	J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Philadelphia, PA, 1987.
	41	L. G. Valiant. A scheme for fast parallel communication. SIAM Journal on Computing, 11(2)350-361, May 1982.
	42	Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]

CITED BY 5

	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
	Matthias Westermann, Distributed caching independent of the network size, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Christof Krick , Friedhelm Meyer auf der Heide , Harald Räcke , Berthold Vöcking , Matthias Westermann, Data management in networks: experimental evaluation of a provably good strategy, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.165-174, June 27-30, 1999, Saint Malo, France
	Richard R. Koch , F. T. Leighton , Bruce M. Maggs , Satish B. Rao , Arnold L. Rosenberg , Eric J. Schwabe, Work-preserving emulations of fixed-connection networks, Journal of the ACM (JACM), v.44 n.1, p.104-147, Jan. 1997
	F. Meyer auf der Heide , H. Räcke , M. Westermann, Data management in hierarchical bus networks, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.109-118, July 09-13, 2000, Bar Harbor, Maine, United States