An improved algorithm for fault-tolerant wormhole routing in meshes

被引：53
|
作者：
Sui, PH
Wang, SD
机构：
[1] Department of Electrical Engineering, National Taiwan University, Taipei
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1997年 / 46卷 / 09期
关键词：
fault-tolerant; deadlock; wormhole routing; virtual channel; channel dependency;
D O I：
10.1109/12.620485
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
Boppana and Chalasani [1] present simple methods to enhance wormhole routing algorithms for fault-tolerance in meshes. In this brief paper, we note that one of their algorithms, f-cube4, can further be improved. In particular, we show that only three virtual channels per physical channel are sufficient for tolerating multiple faulty regions. We also show that our scheme does not lead to deadlock with any combination of faults, while f-cube4 leads to deadlocks for some extreme combinations of fault regions.
引用
收藏
页码：1040 / 1042
页数：3
相关论文
共 50 条
  • [21] A theory of fault-tolerant routing in wormhole networks
    Duato, J
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1997, 8 (08) : 790 - 802
  • [22] Theory of fault-tolerant routing in wormhole networks
    Universidad Politecnica de Valencia, Valencia, Spain
    IEEE Trans Parallel Distrib Syst, 8 (790-802):
  • [23] Fault-tolerant routing algorithm for meshes without using virtual channels
    Chen, KH
    Chiu, GM
    JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 1998, 14 (04) : 765 - 783
  • [24] Adaptive fault-tolerant wormhole routing with two virtual channels in 2D meshes
    Zhou, JP
    Lau, FCM
    I-SPAN 2004: 7TH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND NETWORKS, PROCEEDINGS, 2004, : 142 - 148
  • [25] Performance analysis of fault-tolerant routing algorithm in wormhole-switched interconnections
    F. Safaei
    A. Khonsari
    M. Fathy
    M. Ould-Khaoua
    The Journal of Supercomputing, 2007, 41 : 215 - 245
  • [26] Performance analysis of fault-tolerant routing algorithm in wormhole-switched interconnections
    Safaei, F.
    Khonsari, A.
    Fathy, M.
    Ould-Khaoua, M.
    JOURNAL OF SUPERCOMPUTING, 2007, 41 (03): : 215 - 245
  • [27] FAULT-TOLERANT WORMHOLE ROUTING ALGORITHMS FOR MESH NETWORKS
    BOPPANA, RV
    CHALASANI, S
    IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (07) : 848 - 864
  • [28] Adaptive fault-tolerant wormhole routing for torus networks
    Shih, JD
    1998 INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, PROCEEDINGS, 1998, : 558 - 565
  • [29] Fault-tolerant routing in 2D torus with wormhole routing
    Acosta, JR
    Avresky, DR
    INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS I-V, PROCEEDINGS, 1999, : 2483 - 2487
  • [30] Fault-tolerant wormhole routing in mesh with overlapped solid fault regions
    Kim, SP
    Han, T
    PARALLEL COMPUTING, 1997, 23 (13) : 1937 - 1962
12345