Fault-tolerant Routing for Irregular Faulty Patterns in 2D-Mesh without Virtual Channel

被引：2
作者：
Tse, Savio S. H. [1 ]
Zhou, Jipeng [2 ]
Lau, Francis C. M. [3 ]
机构：
[1] Istanbul Univ, Dept Comp Engn, Avcilar Campus, TR-34320 Istanbul, Turkey
[2] Jinan Univ, Dept Comp Sci, Guangzhou 510632, Peoples R China
[3] Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China
来源：
PROCEEDINGS OF THE 2012 12TH INTERNATIONAL SYMPOSIUM ON PERVASIVE SYSTEMS, ALGORITHMS, AND NETWORKS (I-SPAN 2012) | 2012年
关键词：
Wormhole Routing; virtual Channel; 2D-Mesh; fault-tolerance; COMMUNICATION; MODEL;
D O I：
10.1109/I-SPAN.2012.21
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In wormhole meshes, many fault-tolerant routing algorithms have been proposed. None of them, however, can tolerate general (irregular) fault model without virtual channels. In this paper, a 0-virtual channel fault-tolerant deadlock-free routing algorithm for general fault model is proposed for wormhole routing in two-dimensional meshes. Considering XY-routing as a precious property of two-dimensional meshes, we try to keep as many XY-routings as possible without incurring any deadlock. During the pre-processing, the mesh is divided into a number of fault-free (healthy) rectangular regions, and a minimum spanning tree connecting all these regions is built. Routing within a region uses XY-routing mainly; and routing across regions will use the spanning tree. An online solution is given for handling dynamic faults and recovery.
引用
收藏
页码：96 / 103
页数：8
相关论文
共 50 条
  • [1] A Hardware-Oriented Fault-Tolerant Routing Algorithm for Irregular 2D-Mesh Network-on-Chip without Virtual Channels
    Fukushima, Yusuke
    Fukushi, Masaru
    Yairi, Ikuko Eguchi
    Hattori, Takeshi
    2010 IEEE 25TH INTERNATIONAL SYMPOSIUM ON DEFECT AND FAULT TOLERANCE IN VLSI SYSTEMS (DFT 2010), 2010, : 52 - 59
  • [2] Fault-tolerant adaptive wormhole routing in 2D mesh
    Kim, SP
    Han, T
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 1998, E81D (10): : 1064 - 1071
  • [3] 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
  • [4] ZoneDefense: A Fault-Tolerant Routing for 2-D Meshes Without Virtual Channels
    Fu, Binzhang
    Han, Yinhe
    Li, Huawei
    Li, Xiaowei
    IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 2014, 22 (01) : 113 - 126
  • [5] Effect of Virtual Channels for a Fault-Tolerant XY Routing Method with the Passage of Faulty Nodes
    Kurokawa, Yota
    Fukushi, Masaru
    ICIET 2020: 2020 8TH INTERNATIONAL CONFERENCE ON INFORMATION AND EDUCATION TECHNOLOGY, 2020, : 267 - 272
  • [6] Generation and Performance Evaluation of Reconfigurable Fault Tolerant Routing Algorithm for 2D-Mesh NoC
    Singh, Sandeep Kr
    Mondal, Abir J.
    Majumder, Alak
    3RD INTERNATIONAL CONFERENCE ON RECENT TRENDS IN COMPUTING 2015 (ICRTC-2015), 2015, 57 : 232 - 240
  • [7] Fault-tolerant wormhole routing in meshes without virtual channels
    Glass, CJ
    Ni, LM
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1996, 7 (06) : 620 - 636
  • [8] Fault-Tolerant Adaptive Routing in n-D Mesh
    Chen, Meirun
    Yang, Yi
    WEB-AGE INFORMATION MANAGEMENT, 2016, 9998 : 77 - 87
  • [9] A fault-tolerant routing algorithm for NoC based on 2D Mesh
    Jiang, S. Y.
    Jiang, S. S.
    Luo, G.
    Lu, Z.
    Zhou, J.
    INFORMATION SCIENCE AND ELECTRONIC ENGINEERING, 2017, : 35 - 40
  • [10] ORIGIN-BASED FAULT-TOLERANT ROUTING IN THE MESH
    LIBESKINDHADAS, R
    BRANDT, E
    FUTURE GENERATION COMPUTER SYSTEMS, 1995, 11 (06) : 603 - 615
12345