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 条
  • [41] Fault-Tolerant Routing Algorithm for Mesh based NoC using Reinforcement Learning
    Samala, Jagadheesh
    Takawale, Harshvardhan
    Chokhani, Yash
    Bhanu, P. Veda
    Soumya, J.
    [J]. 2020 24TH INTERNATIONAL SYMPOSIUM ON VLSI DESIGN AND TEST (VDAT), 2020,
  • [42] Fault-tolerant routing mechanism based on network coding in wireless mesh networks
    Peng, Yuhuai
    Song, Qingyang
    Yu, Yao
    Wang, Fei
    [J]. JOURNAL OF NETWORK AND COMPUTER APPLICATIONS, 2014, 37 : 259 - 272
  • [43] A rectilinear-monotone polygonal fault block model for fault-tolerant minimal routing in mesh
    Wang, DJ
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2003, 52 (03) : 310 - 320
  • [44] A new approach to fault-tolerant wormhole routing for mesh-connected parallel computers
    Ho, CT
    Stockmeyer, L
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 2004, 53 (04) : 427 - 438
  • [45] A heuristic fault-tolerant routing algorithm in mesh using rectilinear-monotone polygonal fault blocks
    Wang, Dajin
    [J]. JOURNAL OF SYSTEMS ARCHITECTURE, 2007, 53 (09) : 619 - 628
  • [46] Supremum of idle routers on 2d-mesh with dimension-order routing
    Chen, Juan
    Zhou, Wenhao
    Ben, Chi
    [J]. Journal of Computational Information Systems, 2014, 10 (22): : 9897 - 9906
  • [47] IDFT: An Intermediate Node Based Deterministic Fault Tolerant Routing in 2D Mesh
    Yang, C. X.
    Ding, X. T.
    Ren, X. W.
    Ren, P. J.
    [J]. PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMPUTER INFORMATION SYSTEMS AND INDUSTRIAL APPLICATIONS (CISIA 2015), 2015, 18 : 483 - 488
  • [48] AFRM: Adaptive and Fault-Tolerant Routing Method for 2D Network-on-Chip
    Xie, Ruilian
    Cai, Jueping
    Wang, Peng
    Zhang, Xin
    Wang, Juan
    [J]. JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2017, 26 (12)
  • [49] A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip
    Valinataj, Mojtaba
    Mohammadi, Siamak
    Plosila, Juha
    Liljeberg, Pasi
    Tenhunen, Hannu
    [J]. AEU-INTERNATIONAL JOURNAL OF ELECTRONICS AND COMMUNICATIONS, 2011, 65 (07) : 630 - 640
  • [50] Generation and Performance Evaluation of Reconfigurable Random Routing Algorithm for 2D-Mesh NoCs
    Singh, Sandeep Kumar
    Mondal, Abir J.
    Majumder, Alak
    [J]. 2015 16TH LATIN-AMERICAN TEST SYMPOSIUM (LATS), 2015,
12345