Name
Abstract | ||
|---|---|---|
Application-aware routing exploits static knowledge of an application's traffic pattern to improve performance compared to generalpurpose routing algorithms. Unfortunately, traditional approaches to application-aware routing cannot efficiently handle dynamic changes in the traffic pattern limiting its usefulness in practice. In this paper, we study application-aware routing under traffic uncertainty. Our problem formulation allows an application to statically specify an uncertainty set of traffic patterns that each occur with a given probability, and our goal is to find a single set of combined routes that will enable high-performance across all of these traffic patterns. We show how efficient combined routes can be found for this problem using convex optimization. These combined routes are optimal when the performance for every traffic pattern using the combined routes is the same as the performance using routes that are specialized for just that traffic pattern. We derive necessary and sufficient conditions for when our optimization framework will find optimal combined routes. We use theoretical and numerical analysis for the important class of permutation traffic patterns to quantify how often optimal combined routes exist and to determine the performance loss when optimal combined routes are infeasible. Finally, we use a cycle-level simulator that includes realistic pipeline latencies, arbitration, and buffered flow-control to study the latency and throughput of combined routes compared to specialized routes and routes generated using general-purpose routing algorithms. The theoretical analysis, numerical analysis, and simulation results in this paper provide a first step towards more flexible application-aware routing. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1999946.1999949 | NOCS |
Keywords | Field | DocType |
general-purpose routing algorithm,combined route,optimal combined route,traffic pattern,permutation traffic pattern,flexible application-aware routing,numerical analysis,application-aware on-chip routing,traffic uncertainty,efficient combined route,application-aware routing,flow control,theory,convex optimization,network routing,network on chip,routing,chip,algorithms | Airfield traffic pattern,Computer science,Static routing,Permutation,Administrative distance,Network on a chip,Throughput,Routing table,Convex optimization,Distributed computing | Conference |
Citations | PageRank | References |
3 | 0.44 | 12 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nithin Michael | 1 | 107 | 8.14 |
| Milen Nikolov | 2 | 5 | 2.11 |
| Ao Tang | 3 | 254 | 18.74 |
| G. Edward Suh | 4 | 2721 | 208.03 |
| Christopher Batten | 5 | 478 | 34.23 |