Skip to Main content Skip to Navigation
Journal articles

A General Theory for Deadlock Avoidance in Wormhole-Routed Networks

Eric Fleury 1 Pierre Fraigniaud 2
1 RESEDAS - Software Tools for Telecommunications and Distributed Systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Most of the machines from the last generation of distributed memory parallel computers possess specific routers that are used to communicate with non-neighboring nodes in the network. Among the several technologies, wormhole routing is usually prefered because it allows low channel-setup time and reduces the dependency between latency and inter-node distance. However, wormhole routing is very susceptible to deadlock because messages are allowed to hold many resources while requesting others. Therefore, designing deadlock-free routing algorithms using few hardware facilities is a major problem for wormhole-routed networks. Even though maximizing the degree of adaptiveness of a routing algorithm is not necessarily the best way to obtain the largest efficiency/complexity ratio, adding some adaptiveness improves the performance. It is therefore of great interest to answer the following question: given any network $G$ and any adaptive routing function R on G, is R deadlock-free or not? Characterizations of deadlock-free routing functions in terms of channel dependency graph have been known for a long time for deterministic routing, but only for a short time for adaptive routing, and only for some particular definitions of the routing functions. In this paper, we give a general framework to study deadlock-free routing functions. First we give a general definition that captures many specific definitions of the literature (namely vertex-dependent, input-dependent, source-dependent, path-dependent, etc.). With this general definition, we give a necessary and sufficient condition that characterizes deadlock-free routing functions for a large class of definitions. Using our results, we study several adaptive routing algorithms that have been proposed for meshes, and we derive a new algorithm that offers a higher degree of adaptiveness.
Document type :
Journal articles
Complete list of metadata
Contributor : Publications Loria <>
Submitted on : Monday, September 25, 2006 - 5:02:02 PM
Last modification on : Friday, February 26, 2021 - 3:28:07 PM


  • HAL Id : inria-00098494, version 1



Eric Fleury, Pierre Fraigniaud. A General Theory for Deadlock Avoidance in Wormhole-Routed Networks. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 1998, 9 (7), pp.626--638. ⟨inria-00098494⟩



Record views