Name
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%. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1145/564870.564872 | IEEE Computer Architecture Letters |
Keywords | DocType | Volume |
oblivious routing function,bipartitemaximum-weight matching,obliviousrouting algorithm,interconnection networks,oblivious routing,worst-case traffic,channel loading,oblivious routing algorithm,practical routing function,exact worst-case performance,arbitrary interconnection network topology,worst-case throughput,overestimate thethroughput,bipartite maximum-weight matching,arbitrary interconnectionnetwork topology,exact worstcaseperformance,polynomial time,example case,worst-case traffic pattern,polynomial number,particular routing algorithm | Conference | 1 |
Issue | ISSN | ISBN |
1 | 1556-6056 | 1-58113-529-7 |
Citations | PageRank | References |
43 | 2.30 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Brian Towles | 1 | 2564 | 195.45 |
| William J. Dally | 2 | 11782 | 1460.14 |