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 条
  • [31] 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
  • [32] An Innovative Fault-Tolerant Method for 2-D Mesh-Based Network-on-Chip Routing
    Mohtashamzadeh, Mehdi
    Momeni, Ladan
    Rezazadeh, Arshin
    UKSIM FIFTH EUROPEAN MODELLING SYMPOSIUM ON COMPUTER MODELLING AND SIMULATION (EMS 2011), 2011, : 339 - 343
  • [33] 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
  • [34] A New Fault-tolerant Routing Scheme for N-dimesional Mesh
    Duan Xin-ming
    Wu Ji-Gang
    2012 13TH INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS, AND TECHNOLOGIES (PDCAT 2012), 2012, : 642 - 645
  • [35] 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
  • [36] An Enhanced Fault-Tolerant Routing Algorithm for Mesh Network-on-Chip
    Rezazadeh, Arshin
    Fathy, Mahmood
    Rahnavard, Gholamali
    2009 INTERNATIONAL CONFERENCE ON EMBEDDED SOFTWARE AND SYSTEMS, PROCEEDINGS, 2009, : 505 - +
  • [37] Efficient Routing Table Minimization for Fault-Tolerant Irregular Network-on-Chip
    Mota, Rafael Goncalves
    Silveira, Jarbas
    Silveira, Jardel
    Brahm, Lucas
    Zorzo, Avelino
    Mor, Filipo
    Marcon, Cesar
    23RD IEEE INTERNATIONAL CONFERENCE ON ELECTRONICS CIRCUITS AND SYSTEMS (ICECS 2016), 2016, : 632 - 635
  • [38] Fault-Tolerant Routing for Irregular-Topology-based Network-on-Chips
    Ajabshir, Vahid Babaei
    Tosun, Suleyman
    2014 SECOND INTERNATIONAL SYMPOSIUM ON COMPUTING AND NETWORKING (CANDAR), 2014, : 123 - 129
  • [39] An Implementation of a Distributed Fault-Tolerant Mechanism for 2D Mesh NoCs
    Marcon, Cesar
    Amory, Alexandre
    Webber, Thais
    Bortolon, Felipe T.
    Volpato, Thomas
    Munareto, Jader
    RAPID SYSTEM PROTOTYPING: SHORTENING THE PATH FROM SPECIFICATION TO PROTOTYPE (RSP 2013), 2013, : 24 - 29
  • [40] Routing Fault-Tolerant Sliding Scheduled Traffic in WDM Optical Mesh Networks
    Saradhi, Chava Vijaya
    Gurusamy, Mohan
    Piesiewicz, Radoslaw
    2008 5TH INTERNATIONAL CONFERENCE ON BROADBAND COMMUNICATIONS, NETWORKS AND SYSTEMS (BROADNETS 2008), 2008, : 197 - +
12345