|
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
|
|
| |
6
|
|
| |
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
|
|
 |
9
|
|
| |
10
|
H. Kuhn. The Hungarian method for the assignment problem. Naval Res. Logist. Q., 2:83--97, 1955.
|
| |
11
|
|
 |
12
|
|
| |
13
|
|
CITED BY 7
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|