GOAL
- 1 May 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGARCH Computer Architecture News
- Vol. 31 (2) , 194-205
- https://doi.org/10.1145/871656.859641
Abstract
We introduce a load-balanced adaptive routing algorithm for torus networks, GOAL - Globally Oblivious Adaptive Locally - that provides high throughput on adversarial traffic patterns, matching or exceeding fully randomized routing and exceeding the worst-case performance of Chaos [2], RLB [14], and minimal routing [8] by more than 40%. GOAL also preserves locality to provide up to 4.6× the throughput of fully randomized routing [19] on local traffic. GOAL achieves global load balance by randomly choosing the direction to route in each dimension. Local load balance is then achieved by routing in the selected directions adaptively. We compare the throughput, latency, stability and hot-spot performance of GOAL to six previously published routing algorithms on six specific traffic patterns and 1,000 randomly generated permutations.Keywords
This publication has 12 references indexed in Scilit:
- Locality-preserving randomized oblivious routing on torus networksPublished by Association for Computing Machinery (ACM) ,2002
- Worst-case traffic for oblivious routing functionsPublished by Association for Computing Machinery (ACM) ,2002
- A delay model for router microarchitecturesIEEE Micro, 2001
- The case for chaotic adaptive routingIEEE Transactions on Computers, 1997
- ROMM routing on mesh and torus networksPublished by Association for Computing Machinery (ACM) ,1995
- Adaptive deadlock- and livelock-free routing with all minimal paths in torus networksIEEE Transactions on Parallel and Distributed Systems, 1994
- Virtual-channel flow controlIEEE Transactions on Parallel and Distributed Systems, 1992
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubesIEEE Transactions on Computers, 1991
- Performance analysis of k-ary n-cube interconnection networksIEEE Transactions on Computers, 1990
- A Large Scale, Homogenous, Fully Distributed Parallel Machine, IIPublished by Association for Computing Machinery (ACM) ,1977