O1TURN Oblivious Routing Algorithm

D. Seo, A. Ali, W.-T. Lim, N. Rafique, and M. Thottethodi. "Near-Optimal Worst-case Throughput Routing for Two-Dimensional Mesh Networks." International Symposium on Computer Architecture (ISCA), July 2005.

This paper uses both analytical reasoning and simulation with synthetic traffic patterns to evaluate a simple oblivious non-deterministic routing algorithm called O1TURN for 2D mesh networks. O1TURN randomly chooses between X-Y and Y-X dimension-ordered routing, and can be considered a more restrictive version of the ROMM algorithm discussed in lecture. Section 2 provides a good summary of the same throughput analysis approach we used in lecture, and Section 3 uses this approach to determine the theoretical worst-case throughput for O1TURN. Students should make sure they understand Sections 1–3 in detail. Section 4 describes the required changes to the router for supporting O1TURN and uses virtual channels to avoid deadlock as described in lecture. What do students think of the evaluation in Sections 5–6? How important is optimal worst-case performance compared to average-case performance? How does implementing the O1TURN algorithm compare to implementing the more general ROMM algorithm? How can a more restrictive algorithm have better worst-case performance? Students should spend time reading the related short paper by Towles and Dally, which explains how to calculate the worse-cast traffic pattern for any oblivious routing algorithm, since the O1TURN paper relies on this approach. The Towles and Dally paper also provides another description of the throughput analysis approach we used in class.