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.
Type de document :
Article dans une revue
IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 1998, 9 (7), pp.626--638
Liste complète des métadonnées

https://hal.inria.fr/inria-00098494
Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:02:02
Dernière modification le : jeudi 5 avril 2018 - 12:30:08

Identifiants

  • HAL Id : inria-00098494, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

356