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 条
  • [21] FAULT-TOLERANT WORMHOLE ROUTING ALGORITHMS FOR MESH NETWORKS
    BOPPANA, RV
    CHALASANI, S
    IEEE TRANSACTIONS ON COMPUTERS, 1995, 44 (07) : 848 - 864
  • [22] A General Fault-Tolerant Minimal Routing for Mesh Architectures
    Zhao, Hongzhi
    Bagherzadeh, Nader
    Wu, Jie
    IEEE TRANSACTIONS ON COMPUTERS, 2017, 66 (07) : 1240 - 1246
  • [23] Fault-tolerant Routing for On-chip Network Without Using Virtual Channels
    Ren, Pengju
    Meng, Qingxin
    Ren, Xiaowei
    Zheng, Nanning
    2014 51ST ACM/EDAC/IEEE DESIGN AUTOMATION CONFERENCE (DAC), 2014,
  • [24] Passage of Faulty Nodes: A Novel Approach for Fault-Tolerant Routing on NoCs
    Kurokawa, Yota
    Fukushi, Masaru
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2019, E102A (12) : 1702 - 1710
  • [25] Fault-tolerant wormhole routing in mesh networks with non-rectangular fault regions
    Ho, WH
    Cheung, YS
    INTERNATIONAL SOCIETY FOR COMPUTERS AND THEIR APPLICATIONS 10TH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING SYSTEMS, 1997, : 551 - 557
  • [26] Fault-tolerant routing in two-dimensional mesh networks with less-restricted fault patterns
    Wang, SD
    Sui, PH
    2001 PACIFIC RIM INTERNATIONAL SYMPOSIUM ON DEPENDABLE COMPUTING, PROCEEDINGS, 2001, : 111 - 118
  • [27] TRACK: An algorithm for fault-tolerant, dynamic and scalable 2D mesh network-on-chip routing reconfiguration
    Jain, Anugrah
    Laxmi, Vijay
    Tripathi, Meenakshi
    Gaur, Manoj Singh
    Bishnoi, Rimpy
    INTEGRATION-THE VLSI JOURNAL, 2020, 72 (72) : 92 - 110
  • [28] A Path-Counter Method for Fault-Tolerant Minimal Routing Algorithms in 2D Mesh
    Zhao, Hongzhi
    Wang, Qiang
    Xiong, Ke
    Pei, Songwen
    JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2018, 27 (04)
  • [29] A new fault-tolerant routing scheme for 2-dimesnsioal mesh networks
    Wang, GC
    Chen, JN
    PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PDCAT'2003, PROCEEDINGS, 2003, : 95 - 98
  • [30] NEW FAULT-TOLERANT BROADCAST ROUTING ALGORITHM ON MESH NETWORKS
    Wang, Gaocai
    Chen, Jianer
    Lin, Chuang
    JOURNAL OF INTERCONNECTION NETWORKS, 2010, 11 (3-4) : 175 - 187
12345