Technique for Deadlock-Free Adaptive Routing Algorithms

J. Duato. "A New Theory of Deadlock-Free Adaptive Routing in Wormhole Networks." IEEE Transactions on Parallel and Distributed Systems (TPDS), 4(12):1320–1331, December 1993.

This is a classic paper that describes a technique for creating deadlock-free adaptive routing algorithms. This approach has been used in several real machines and is worth understanding in detail. Students are encouraged to read Sections 1–3 of the related TPDS'95 paper since it also provides a nice overview of the technique. Students should definitely read the related TOC'87 paper by Dally and Seitz on creating deadlock-free deterministic routing algorithms, since Duato refers to this paper extensively. For the primary TPDS'93 paper, students should focus more on the high-level technique and not get too lost in the details of each proof. Duato includes "proof sketches" for each theorem that provide useful overviews of each proof. Students should spend time understanding the two design methodologies in Section 3. How do the deadlock-avoidance schemes used in GOAL relate to the Dally TOC'87 and Duato TPDS'93 papers? What exactly is Duato comparing his algorithm to in the simulation results? Notice that the traffic for the Adaptive(2VC) algorithm decreases past saturation in Figure 3. What does this indicate about the simulation methodology?