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 条
  • [11] Dynamic Fault-Tolerant Wormhole Routing in 2-D Meshes
    Mortazavi, A.
    Safaei, F.
    15TH CSI INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND DIGITAL SYSTEMS (CADS 2010), 2010, : 77 - 82
  • [12] Fault-tolerant routing for wormhole routed two-dimensional meshes
    Avresky, DR
    Cunningham, C
    Ravichanran, H
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 2000, 15 (06): : 385 - 397
  • [13] Multi-phase minimal fault-tolerant wormhole routing in meshes
    Zhou, JP
    Lau, FCM
    PARALLEL COMPUTING, 2004, 30 (03) : 423 - 442
  • [14] Fault-tolerant wormhole routing algorithm in 2D meshes without virtual channels
    Zhou, JP
    Lau, FCM
    PARALLEL AND DISTRIBUTED PROCESSING AND APPLICATIONS, PROCEEDINGS, 2004, 3358 : 688 - 697
  • [15] Fault-Tolerant Routing Algorithm in Meshes with Solid Faults
    Jong-Hoon Youn
    Bella Bose
    Seungjin Park
    The Journal of Supercomputing, 2006, 37 : 161 - 177
  • [16] Fault-tolerant routing algorithm in meshes with solid faults
    Youn, Jong-Hoon
    Bose, Bella
    Park, Seungjin
    JOURNAL OF SUPERCOMPUTING, 2006, 37 (02): : 161 - 177
  • [17] Multiphase minimal fault-tolerant wormhole routing in 2D meshes
    Zhou, JP
    Lau, FCM
    PROCEEDINGS OF THE EIGHTH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED SYSTEMS, 2001, : 323 - 330
  • [18] A simple and efficient fault-tolerant adaptive routing algorithm for meshes
    Shamaei, Arash
    Nayebi, Abbas
    Sarbazi-Azad, Hamid
    ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, PROCEEDINGS, 2008, 5022 : 54 - +
  • [19] Fault-Tolerant Routing Schemes for Wormhole Mesh
    Duan, Xinming
    Zhang, Dakun
    Sun, Xuemei
    2009 IEEE INTERNATIONAL SYMPOSIUM ON PARALLEL AND DISTRIBUTED PROCESSING WITH APPLICATIONS, PROCEEDINGS, 2009, : 298 - 301
  • [20] Fault-tolerant wormhole routing for hypercube networks
    Shih, JD
    INFORMATION PROCESSING LETTERS, 2003, 86 (02) : 93 - 100
12345