InforLorV4, Main, Merge, bibRecord, 00BB73

General theory for deadlock avoidance in wormhole-routed networks

Identifieur interne : 00BB73 ( Main/Merge ); précédent : 00BB72; suivant : 00BB74

General theory for deadlock avoidance in wormhole-routed networks

Auteurs : E. Fleury [France] ; P. Fraigniaud

Source :

IEEE Transactions on Parallel and Distributed Systems [ 1045-9219 ] ; 1998.

RBID : Pascal:98-0365760

Descripteurs français

Pascal (Inist)
- Bibliographie, Système communication donnée, Gestion encombrement(communication), Canal transmission, Rétablissement système informatique, Equipement stockage donnée, Allocation mémoire, Réseau interconnexion, Algorithme, Système traitement parallèle, Théorie.
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.

Links toward previous steps (curation, corpus...)

to stream PascalFrancis, to step Corpus: 000B96
to stream PascalFrancis, to step Curation: 000C78
to stream PascalFrancis, to step Checkpoint: 000B51

Links to Exploration step

Pascal:98-0365760

Le 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>
<idno type="wicri:doubleKey">1045-9219:1998:Fleury E:general:theory:for</idno>
<idno type="wicri:Area/Main/Merge">00BB73</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>
<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/Main/Merge

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 00BB73 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 00BB73 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Merge
   |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.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

General theory for deadlock avoidance in wormhole-routed networks

General theory for deadlock avoidance in wormhole-routed networks

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri