IEICE TRANSACTIONS on Information
A Fault-Tolerant Wormhole Routing Algorithm in Two Dimensional Mesh Networks
Summary :
We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.
- Publication
- IEICE TRANSACTIONS on Information Vol.E81-D No.6 pp.532-544
- Publication Date
- 1998/06/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- Fault Tolerant Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Jinsoo KIM, Ji-Yun KIM, Hyunsoo YOON, Seung Ryoul MAENG, Jung Wan CHO, "A Fault-Tolerant Wormhole Routing Algorithm in Two Dimensional Mesh Networks" in IEICE TRANSACTIONS on Information,
vol. E81-D, no. 6, pp. 532-544, June 1998, doi: .
Abstract: We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_6_532/_p
Copy
@ARTICLE{e81-d_6_532,
author={Jinsoo KIM, Ji-Yun KIM, Hyunsoo YOON, Seung Ryoul MAENG, Jung Wan CHO, },
journal={IEICE TRANSACTIONS on Information},
title={A Fault-Tolerant Wormhole Routing Algorithm in Two Dimensional Mesh Networks},
year={1998},
volume={E81-D},
number={6},
pages={532-544},
abstract={We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - A Fault-Tolerant Wormhole Routing Algorithm in Two Dimensional Mesh Networks
T2 - IEICE TRANSACTIONS on Information
SP - 532
EP - 544
AU - Jinsoo KIM
AU - Ji-Yun KIM
AU - Hyunsoo YOON
AU - Seung Ryoul MAENG
AU - Jung Wan CHO
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1998
AB - We propose a fault-tolerant routing algorithm for 2D meshes. Our routing algorithm can tolerate any number of concave fault regions. It is based on xy-routing and uses the concept of the fault ring/chain composed of fault-free elements surrounding faults. Three virtual channels per physical link are used for deadlock-free routing on a fault ring. Four virtual channels are needed for a fault chain. For a concave fault ring, fault-free nodes in the concave region have been deactivated to avoid deadlock in the previous algorithms, which results in excessive loss of the computational power. Our algorithm ensures deadlock-freedom by restricting the virtual channel usage in the concave region, and it minimizes the loss of the computational power. We also extend the proposed routing scheme for adaptive fault-tolerant routing. The adaptive version requires the same number of virtual channels as the deterministic one.
ER -
English
