Globally Oblivious Adaptive Locally Routing Algorithm

A. Singh, W.J. Dally, A.K. Gupta, and B. Towles. "GOAL: A Load-Balanced Adaptive Routing Algorithm for Torus Networks." International Symposium on Computer Architecture (ISCA), June 2003.

The GOAL routing algorithm illustrates an interesting combination of the oblivious and adaptive approaches. Section 2 is a nice summary of some of the terms and concepts we have been discussing in class. Section 3 more formally examines the simple example we discussed in class, namely the worst-case throughput for a minimal routing algorithm on a 8-ary 1-cube. Students should carefully read Section 4, which describes the actual GOAL algorithm and also describes how to use virtual channels to avoid deadlock. The oblivious half of GOAL is essentially just the weighted randomized algorithm we discussed in class extended to higher dimensions. Students might be interested in skimming the related paper on the RLB algorithm, which is the oblivious half of GOAL plus something like ROMM. Section 5 of the GOAL paper includes a nice overview of a variety of routing algorithms. What are the key trade-offs of an oblivious versus adaptive approach that make the GOAL hybrid so interesting? Is it possible to apply the GOAL algorithm to a mesh topology? Why does GOAL perform worse than dimension-ordered routing on uniform random traffic? What do students think about using saturation throughput histograms for random traffic permutation matrices and latency histograms as evaluation metrics? Why does the CHAOS routing algorithm experience a decrease in observed throughput with higher offered bandwidths? Consider the discrepancy between the O1TURN paper, which seems to argue for oblivious over adaptive algorithms, versus the GOAL paper, which argues for adding adaptivity to their previous oblivious RLB algorithm?