GOAL
Arjun Singh, W.J. Dally, Amit Kr. Gupta et al. · ACM SIGARCH Computer Architecture News · 2003
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.
Cited by 49 works. doi:10.1145/871656.859641
Authors
References
- A Scheme for Fast Parallel Communication
- Virtual-channel flow control
- Performance analysis of k-ary n-cube interconnection networks
- An adaptive and fault tolerant wormhole routing strategy for k-ary n-cubes
- The case for chaotic adaptive routing
- A Large Scale, Homogenous, Fully Distributed Parallel Machine, II
- A delay model for router microarchitectures
- An efficient, fully adaptive deadlock recovery scheme
- Adaptive deadlock- and livelock-free routing with all minimal paths in torus networks
- ROMM routing on mesh and torus networks