General theory for deadlock avoidance in wormhole-routed networks
Identifieur interne : 000B51 ( PascalFrancis/Checkpoint ); précédent : 000B50; suivant : 000B52General theory for deadlock avoidance in wormhole-routed networks
Auteurs : E. Fleury [France] ; P. FraigniaudSource :
- IEEE Transactions on Parallel and Distributed Systems [ 1045-9219 ] ; 1998.
Descripteurs français
- Pascal (Inist)
- Wicri :
- topic : Bibliographie.
English descriptors
- KwdEn :
- Algorithms, Bibliographies, Communication channels (information theory), Computer system recovery, Congestion control (communication), Data communication systems, Data storage equipment, Deadlock avoidance, Interconnection networks, Parallel processing systems, Storage allocation (computer), Theory, Wormhole-routed networks.
Abstract
Most machines of the last generation of disturbed memory parallel computers possess specific routers which are used to exchange messages between nonneighboring nodes in the network. Among the several technologies, wormhole routing id usually preferred because it allows low channel-setup time and reduces the dependency between latency and internode 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. In this paper, we describe a general theoretical framework for the study of deadlock-free routing functions. We give a general definition of what can be a routing function. This definition captures many specific definitions of the literature (e.g., vertex-dependent, input-dependent, source-dependent, path-dependent, etc.). Using our definition, we give a necessary and sufficient condition which characterizes deadlock-free routing functions. Our theory embraces, at a high level, most of the theories related to deadlock avoidance in wormhole-routed networks previously derived in the literature. In particular, it applies not only to one-to-one routing, but also to one-to-many routing. The latter paradigm is used to solve the multicast problem with the path-based or tree-based facility.
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:98-0365760Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">General theory for deadlock avoidance in wormhole-routed networks</title><author><name sortKey="Fleury, E" sort="Fleury, E" uniqKey="Fleury E" first="E." last="Fleury">E. Fleury</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LORIA</s1><s2>Villers-Les-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>Villers-Les-Nancy</wicri:noRegion><wicri:noRegion>LORIA</wicri:noRegion><wicri:noRegion>LORIA</wicri:noRegion></affiliation></author><author><name sortKey="Fraigniaud, P" sort="Fraigniaud, P" uniqKey="Fraigniaud P" first="P." last="Fraigniaud">P. Fraigniaud</name></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">98-0365760</idno><date when="1998">1998</date><idno type="stanalyst">PASCAL 98-0365760 EI</idno><idno type="RBID">Pascal:98-0365760</idno><idno type="wicri:Area/PascalFrancis/Corpus">000B96</idno><idno type="wicri:Area/PascalFrancis/Curation">000C78</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000B51</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000B51</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">General theory for deadlock avoidance in wormhole-routed networks</title><author><name sortKey="Fleury, E" sort="Fleury, E" uniqKey="Fleury E" first="E." last="Fleury">E. Fleury</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>LORIA</s1><s2>Villers-Les-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></inist:fA14><country>France</country><wicri:noRegion>Villers-Les-Nancy</wicri:noRegion><wicri:noRegion>LORIA</wicri:noRegion><wicri:noRegion>LORIA</wicri:noRegion></affiliation></author><author><name sortKey="Fraigniaud, P" sort="Fraigniaud, P" uniqKey="Fraigniaud P" first="P." last="Fraigniaud">P. Fraigniaud</name></author></analytic><series><title level="j" type="main">IEEE Transactions on Parallel and Distributed Systems</title><title level="j" type="abbreviated">IEEE Trans Parallel Distrib Syst</title><idno type="ISSN">1045-9219</idno><imprint><date when="1998">1998</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">IEEE Transactions on Parallel and Distributed Systems</title><title level="j" type="abbreviated">IEEE Trans Parallel Distrib Syst</title><idno type="ISSN">1045-9219</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Bibliographies</term><term>Communication channels (information theory)</term><term>Computer system recovery</term><term>Congestion control (communication)</term><term>Data communication systems</term><term>Data storage equipment</term><term>Deadlock avoidance</term><term>Interconnection networks</term><term>Parallel processing systems</term><term>Storage allocation (computer)</term><term>Theory</term><term>Wormhole-routed networks</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Bibliographie</term><term>Système communication donnée</term><term>Gestion encombrement(communication)</term><term>Canal transmission</term><term>Rétablissement système informatique</term><term>Equipement stockage donnée</term><term>Allocation mémoire</term><term>Réseau interconnexion</term><term>Algorithme</term><term>Système traitement parallèle</term><term>Théorie</term></keywords><keywords scheme="Wicri" type="topic" xml:lang="fr"><term>Bibliographie</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Most machines of the last generation of disturbed memory parallel computers possess specific routers which are used to exchange messages between nonneighboring nodes in the network. Among the several technologies, wormhole routing id usually preferred because it allows low channel-setup time and reduces the dependency between latency and internode 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. In this paper, we describe a general theoretical framework for the study of deadlock-free routing functions. We give a general definition of what can be a routing function. This definition captures many specific definitions of the literature (e.g., vertex-dependent, input-dependent, source-dependent, path-dependent, etc.). Using our definition, we give a necessary and sufficient condition which characterizes deadlock-free routing functions. Our theory embraces, at a high level, most of the theories related to deadlock avoidance in wormhole-routed networks previously derived in the literature. In particular, it applies not only to one-to-one routing, but also to one-to-many routing. The latter paradigm is used to solve the multicast problem with the path-based or tree-based facility.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>1045-9219</s0></fA01><fA02 i1="01"><s0>ITDSEO</s0></fA02><fA03 i2="1"><s0>IEEE Trans Parallel Distrib Syst</s0></fA03><fA05><s2>9</s2></fA05><fA06><s2>7</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>General theory for deadlock avoidance in wormhole-routed networks</s1></fA08><fA11 i1="01" i2="1"><s1>FLEURY (E.)</s1></fA11><fA11 i1="02" i2="1"><s1>FRAIGNIAUD (P.)</s1></fA11><fA14 i1="01"><s1>LORIA</s1><s2>Villers-Les-Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ></fA14><fA20><s1>626-638</s1></fA20><fA21><s1>1998</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>22203</s2></fA43><fA44><s0>A100</s0></fA44><fA45><s0>76 Refs.</s0></fA45><fA47 i1="01" i2="1"><s0>98-0365760</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i2="1"><s0>IEEE Transactions on Parallel and Distributed Systems</s0></fA64><fA66 i1="01"><s0>USA</s0></fA66><fC01 i1="01" l="ENG"><s0>Most machines of the last generation of disturbed memory parallel computers possess specific routers which are used to exchange messages between nonneighboring nodes in the network. Among the several technologies, wormhole routing id usually preferred because it allows low channel-setup time and reduces the dependency between latency and internode 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. In this paper, we describe a general theoretical framework for the study of deadlock-free routing functions. We give a general definition of what can be a routing function. This definition captures many specific definitions of the literature (e.g., vertex-dependent, input-dependent, source-dependent, path-dependent, etc.). Using our definition, we give a necessary and sufficient condition which characterizes deadlock-free routing functions. Our theory embraces, at a high level, most of the theories related to deadlock avoidance in wormhole-routed networks previously derived in the literature. In particular, it applies not only to one-to-one routing, but also to one-to-many routing. The latter paradigm is used to solve the multicast problem with the path-based or tree-based facility.</s0></fC01><fC02 i1="01" i2="X"><s0>001D03J07</s0></fC02><fC02 i1="02" i2="X"><s0>001D02B</s0></fC02><fC02 i1="03" i2="X"><s0>001D04B</s0></fC02><fC02 i1="04" i2="X"><s0>001D04A</s0></fC02><fC02 i1="05" i2="X"><s0>001D03I02</s0></fC02><fC02 i1="06" i2="X"><s0>001D02A</s0></fC02><fC03 i1="01" i2="1" l="ENG"><s0>Wormhole-routed networks</s0><s4>INC</s4></fC03><fC03 i1="02" i2="1" l="ENG"><s0>Deadlock avoidance</s0><s4>INC</s4></fC03><fC03 i1="03" i2="1" l="FRE"><s0>Bibliographie</s0></fC03><fC03 i1="03" i2="1" l="ENG"><s0>Bibliographies</s0></fC03><fC03 i1="04" i2="1" l="FRE"><s0>Système communication donnée</s0></fC03><fC03 i1="04" i2="1" l="ENG"><s0>Data communication systems</s0></fC03><fC03 i1="05" i2="1" l="FRE"><s0>Gestion encombrement(communication)</s0></fC03><fC03 i1="05" i2="1" l="ENG"><s0>Congestion control (communication)</s0></fC03><fC03 i1="06" i2="1" l="FRE"><s0>Canal transmission</s0></fC03><fC03 i1="06" i2="1" l="ENG"><s0>Communication channels (information theory)</s0></fC03><fC03 i1="07" i2="1" l="FRE"><s0>Rétablissement système informatique</s0></fC03><fC03 i1="07" i2="1" l="ENG"><s0>Computer system recovery</s0></fC03><fC03 i1="08" i2="1" l="FRE"><s0>Equipement stockage donnée</s0></fC03><fC03 i1="08" i2="1" l="ENG"><s0>Data storage equipment</s0></fC03><fC03 i1="09" i2="1" l="FRE"><s0>Allocation mémoire</s0></fC03><fC03 i1="09" i2="1" l="ENG"><s0>Storage allocation (computer)</s0></fC03><fC03 i1="10" i2="1" l="FRE"><s0>Réseau interconnexion</s0></fC03><fC03 i1="10" i2="1" l="ENG"><s0>Interconnection networks</s0></fC03><fC03 i1="11" i2="1" l="FRE"><s0>Algorithme</s0></fC03><fC03 i1="11" i2="1" l="ENG"><s0>Algorithms</s0></fC03><fC03 i1="12" i2="1" l="FRE"><s0>Système traitement parallèle</s0><s3>P</s3></fC03><fC03 i1="12" i2="1" l="ENG"><s0>Parallel processing systems</s0><s3>P</s3></fC03><fC03 i1="13" i2="1" l="FRE"><s0>Théorie</s0></fC03><fC03 i1="13" i2="1" l="ENG"><s0>Theory</s0></fC03><fN21><s1>251</s1></fN21></pA></standard></inist><affiliations><list><country><li>France</li></country></list><tree><noCountry><name sortKey="Fraigniaud, P" sort="Fraigniaud, P" uniqKey="Fraigniaud P" first="P." last="Fraigniaud">P. Fraigniaud</name></noCountry><country name="France"><noRegion><name sortKey="Fleury, E" sort="Fleury, E" uniqKey="Fleury E" first="E." last="Fleury">E. Fleury</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000B51 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000B51 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:98-0365760
|texte= General theory for deadlock avoidance in wormhole-routed networks
}}
| This area was generated with Dilib version V0.6.33. |  |