A General Theory for Deadlock Avoidance in Wormhole-Routed Networks
Identifieur interne : 00B134 ( Main/Exploration ); précédent : 00B133; suivant : 00B135A General Theory for Deadlock Avoidance in Wormhole-Routed Networks
Auteurs : Eric Fleury ; Pierre FraigniaudSource :
- IEEE Transactions on Parallel and Distributed Systems ; 1998.
English descriptors
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.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 002353
- to stream Crin, to step Curation: 002353
- to stream Crin, to step Checkpoint: 002382
- to stream Main, to step Merge: 00B855
- to stream Main, to step Curation: 00B134
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="211">A General Theory for Deadlock Avoidance in Wormhole-Routed Networks</title></titleStmt><publicationStmt><idno type="RBID">CRIN:fleury98a</idno><date when="1998" year="1998">1998</date><idno type="wicri:Area/Crin/Corpus">002353</idno><idno type="wicri:Area/Crin/Curation">002353</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">002353</idno><idno type="wicri:Area/Crin/Checkpoint">002382</idno><idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">002382</idno><idno type="wicri:Area/Main/Merge">00B855</idno><idno type="wicri:Area/Main/Curation">00B134</idno><idno type="wicri:Area/Main/Exploration">00B134</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">A General Theory for Deadlock Avoidance in Wormhole-Routed Networks</title><author><name sortKey="Fleury, Eric" sort="Fleury, Eric" uniqKey="Fleury E" first="Eric" last="Fleury">Eric Fleury</name></author><author><name sortKey="Fraigniaud, Pierre" sort="Fraigniaud, Pierre" uniqKey="Fraigniaud P" first="Pierre" last="Fraigniaud">Pierre Fraigniaud</name></author></analytic><series><title level="j">IEEE Transactions on Parallel and Distributed Systems</title><imprint><date when="1998" type="published">1998</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>deadlock</term><term>multicast</term><term>routing</term><term>wormhole</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en" wicri:score="5090">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.</div></front></TEI><affiliations><list></list><tree><noCountry><name sortKey="Fleury, Eric" sort="Fleury, Eric" uniqKey="Fleury E" first="Eric" last="Fleury">Eric Fleury</name><name sortKey="Fraigniaud, Pierre" sort="Fraigniaud, Pierre" uniqKey="Fraigniaud P" first="Pierre" last="Fraigniaud">Pierre Fraigniaud</name></noCountry></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00B134 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 00B134 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= CRIN:fleury98a
|texte= A General Theory for Deadlock Avoidance in Wormhole-Routed Networks
}}
| This area was generated with Dilib version V0.6.33. |  |