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 条
  • [31] A fault-tolerant routing scheme for meshes with nonconvex faults
    Chen, CL
    Chiu, GM
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2001, 12 (05) : 467 - 475
  • [32] A Deadlock-free Fault-tolerant Routing Algorithm for N-Dimesional Meshes
    Duan, Xinming
    Wu, Jigang
    2011 INTERNATIONAL CONFERENCE OF ELECTRON DEVICES AND SOLID-STATE CIRCUITS (EDSSC), 2011,
  • [33] Fault-Tolerant Broadcasting in 2-D Wormhole-Routed Meshes
    Zhen Jiang
    Jie Wu
    The Journal of Supercomputing, 2003, 25 : 255 - 275
  • [34] Fault-tolerant broadcasting in 2-D wormhole-routed meshes
    Jiang, Z
    Wu, J
    PDPTA'2001: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, 2001, : 2028 - 2034
  • [35] Fault-tolerant broadcasting in 2-D wormhole-routed meshes
    Jiang, Z
    Wu, J
    JOURNAL OF SUPERCOMPUTING, 2003, 25 (03): : 255 - 275
  • [36] A fault-tolerant wormhole routing scheme for torus networks with nonconvex faults
    Shih, JD
    INFORMATION PROCESSING LETTERS, 2003, 88 (06) : 271 - 278
  • [37] Fault-tolerant wormhole routing in torus networks with overlapped block faults
    Shih, JD
    IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES, 2003, 150 (01): : 29 - 37
  • [38] A fault-tolerant wormhole routing algorithms in two dimensional mesh networks
    Kim, J
    Kim, JY
    Yoon, H
    Maeng, SR
    Cho, JW
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1998, E81D (06) : 532 - 544
  • [39] Fault-tolerant adaptive wormhole routing in 2D mesh
    Kim, SP
    Han, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1998, E81D (10): : 1064 - 1071
  • [40] A New Fault-Tolerant Wormhole Routing Scheme in Tori with Convex Faults
    Xie, Lingfu
    Xu, Du
    Yao, Qing
    Song, Lei
    11TH IEEE HIGH ASSURANCE SYSTEMS ENGINEERING SYMPOSIUM, PROCEEDINGS, 2008, : 467 - 470
12345