Worst-case traffic for oblivious routing functions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Worst-case traffic for oblivious routing functions

Full text

Pdf (221 KB)

Source

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

Winnipeg, Manitoba, Canada

SESSION: Session 1 table of contents

Pages: 1 - 8

Year of Publication: 2002

ISBN:1-58113-529-7

Authors

Brian Towles	Stanford University
William J. Dally	Stanford University

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 33, Citation Count: 6

Additional Information:

abstract 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/564870.564872 What is a DOI?

ABSTRACT

This paper presents an algorithm to find a worst-case traffic pattern for any oblivious routing algorithm on an arbitrary interconnection network topology. The linearity of channel loading offered by oblivious routing algorithms enables the problem to be mapped to a bipartite maximum-weight matching, which can be solved in polynomial time for most practical routing functions. Finding exact worst-case performance was previously intractable, and we demonstrate an example case where traditional characterization techniques overestimate the throughput of a particular routing algorithm by 47%.

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. M. Maggs, and M. Newman. Fast algorithms for bit-serial routing on a hypercube. Mathematical Systems Theory, 24(4):253--271, 1991.
	2	Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001 [doi>10.1145/363647.363677]
	3	I. T. Association. InfiniBand architecture specification. http://www.infinibandta.org.
	4	G. Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumán Rev. Ser. A, 5:147--151, 1946.
	5	Kevin Bolding , Melanie Fulgham , Lawrence Snyder, The Case for Chaotic Adaptive Routing, IEEE Transactions on Computers, v.46 n.12, p.1281-1292, December 1997 [doi>10.1109/12.641929]
	6	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]
	7	W. J. Dally, P. P. Carvey, and L. R. Dennison. The Avici terabit switch/router. In Conference Record of Hot Interconnects 6, pages 41--50, August 1998.
	8	Jose Duato , Sudhakar Yalamanchili , Lionel Ni, Interconnection Networks: An Engineering Approach, IEEE Computer Society Press, Los Alamitos, CA, 1997
	9	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]
	10	H. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Q., 2:83--97, 1955.
	11	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]
	12	Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215455]
	13	Li-Shiuan Peh , William J. Dally, A Delay Model and Speculative Architecture for Pipelined Routers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.255, January 20-24, 2001

CITED BY 7

	Brian Towles , William J. Dally , Stephen Boyd, Throughput-centric routing algorithm design, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Arjun Singh , William J. Dally , Amit K. Gupta , Brian Towles, GOAL: a load-balanced adaptive routing algorithm for torus networks, ACM SIGARCH Computer Architecture News, v.31 n.2, May 2003
	J. Miguel-Alonso , C. Izu , J. A. Gregorio, Improving the performance of large interconnection networks using congestion-control mechanisms, Performance Evaluation, v.65 n.3-4, p.203-211, March, 2008
	Dennis Abts , Natalie D. Enright Jerger , John Kim , Dan Gibson , Mikko H. Lipasti, Achieving predictable performance through better memory controller placement in many-core CMPs, ACM SIGARCH Computer Architecture News, v.37 n.3, June 2009
	Srinivasan Murali , David Atienza , Paolo Meloni , Salvatore Carta , Luca Benini , Giovanni De Micheli , Luigi Raffo, Synthesis of predictable networks-on-chip-based interconnect architectures for chip multiprocessors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.15 n.8, p.869-880, August 2007
	Radu Marculescu , Umit Y. Ogras , Li-Shiuan Peh , Natalie Enright Jerger , Yatin Hoskote, Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, v.28 n.1, p.3-21, January 2009
	Itamar Cohen , Ori Rottenstreich , Isaac Keslassy, Statistical Approach to NoC Design, Proceedings of the Second ACM/IEEE International Symposium on Networks-on-Chip, p.171-180, April 07-10, 2008