The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
De nombreux chercheurs ont utilisé les réseaux d’interconnexion hypercubes pour leurs bonnes propriétés afin de construire de nombreux systèmes de traitement parallèle. Cependant, à mesure que le nombre de processeurs augmente, la probabilité d’apparition de nœuds défectueux augmente également. Ainsi, pour les réseaux d'interconnexion hypercubes comportant des nœuds défectueux, plusieurs algorithmes de routage dynamique efficaces ont été proposés qui permettent à chaque nœud de détenir des informations sur l'état de ses nœuds voisins. Dans cet article, nous proposons une version améliorée de l'algorithme proposé par Chiu et Wu en introduisant la notion d'accessibilité totale. Un nœud entièrement accessible est un nœud qui peut atteindre tous les nœuds non défectueux ayant une distance de Hamming. l du nœud via des chemins de longueur l. De plus, nous améliorons encore l'algorithme en classant les possibilités de détours par rapport à chaque distance de Hamming entre les nœuds actuels et cibles. Nous proposons une procédure d'initialisation qui utilise une condition équivalente pour effectuer cette classification efficacement. De plus, nous effectuons une simulation pour mesurer le taux d’amélioration et comparer nos algorithmes avec d’autres. Les résultats de la simulation montrent que les algorithmes sont efficaces lorsqu’ils sont appliqués à des réseaux d’interconnexion hypercubes de faible dimension.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Keiichi KANEKO, Hideo ITO, "Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 1, pp. 121-128, January 2001, doi: .
Abstract: Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance l from the node via paths of length l. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_1_121/_p
Copier
@ARTICLE{e84-d_1_121,
author={Keiichi KANEKO, Hideo ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks},
year={2001},
volume={E84-D},
number={1},
pages={121-128},
abstract={Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance l from the node via paths of length l. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.},
keywords={},
doi={},
ISSN={},
month={January},}
Copier
TY - JOUR
TI - Fault-Tolerant Routing Algorithms for Hypercube Interconnection Networks
T2 - IEICE TRANSACTIONS on Information
SP - 121
EP - 128
AU - Keiichi KANEKO
AU - Hideo ITO
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2001
AB - Many researchers have used hypercube interconnection networks for their good properties to construct many parallel processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several efficient dynamic routing algorithms have been proposed which allow each node to hold status information of its neighbor nodes. In this paper, we propose an improved version of the algorithm proposed by Chiu and Wu by introducing the notion of full reachability. A fully reachable node is a node that can reach all nonfaulty nodes which have Hamming distance l from the node via paths of length l. In addition, we further improve the algorithm by classifying the possibilities of detours with respect to each Hamming distance between current and target nodes. We propose an initialization procedure which makes use of an equivalent condition to perform this classification efficiently. Moreover, we conduct a simulation to measure the improvement ratio and to compare our algorithms with others. The simulation results show that the algorithms are effective when they are applied to low-dimensional hypercube interconnection networks.
ER -