A universal proof technique for deadlock-free routing in interconnection networks
Loren Schwiebert, D.N. Jayasimha · 1995
An important open problem in interconnection network routing has been to characterize the conditions under which routing algorithms are deadlock-free.Although this problem has been resolved for restricted classes of routing algorithms, no general solution has been found.In this paper, we solve this problem by proving a necessary and sufficient condition that can be used for any interconnection network routing algorithm, as long as only local information is required for routing.Our proof technique is universal: it can be used with any switching technique that is not inherently deadlock-free.This includes switching techniques such as wormhole routing, store-and-forward routing, and virtual cut-through.The proof technique for the necessary and sufficient condition introduces a new type of dependency graph, the buffer waiting graph, which omits most dependencies that cannot be used to create a deadlock configuration.Our methodology is illustrated by proving deadlock freedom for a store-and-forward routing algorithm for meshes and a wormhole routing algorithm for hypercubes.The hypercube routing algorithm requires only two virtual channels per physical channel and is more adaptive than any previously proposed wormhole routing algorithm for hypercubes.