An improved fault-tolerant routing algorithm for a Network-on-Chip derived with formal analysis

被引：9
作者：
Zhang, Zhen [1 ]
Serwe, Wendelin [2 ,3 ,4 ]
Wu, Jian [5 ]
Yoneda, Tomohiro [6 ]
Zheng, Hao [7 ]
Myers, Chris [1 ]
机构：
[1] Univ Utah, Dept Elect & Comp Engn, Salt Lake City, UT 84112 USA
[2] Inria, Rocquencourt, France
[3] Univ Grenoble Alpes, LIG, F-38000 Grenoble, France
[4] CNRS, LIG, F-38000 Grenoble, France
[5] Toshiba Amer Elect Components Inc, San Jose, CA USA
[6] Natl Inst Informat, Tokyo, Japan
[7] Univ S Florida, Dept Comp Sci & Engn, Tampa, FL USA
来源：
SCIENCE OF COMPUTER PROGRAMMING | 2016年 / 118卷
基金：
美国国家科学基金会;
关键词：
Fault-tolerant routing; Formal methods; Model checking; Network-on-chip; Process calculus; VERIFICATION; SPECIFICATIONS; ARCHITECTURE; PROTOCOL; MESHES; MODEL;
D O I：
10.1016/j.scico.2016.01.002
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
A fault-tolerant routing algorithm in Network-on-Chip (NoC) architectures provides adaptivity for on-chip communications. Adding fault-tolerance adaptivity to a routing algorithm increases its design complexity and makes it prone to deadlock and other problems if improperly implemented. Formal verification techniques are needed to check the correctness of the design. This paper describes the discovery of a potential livelock problem through formal analysis on an extension of the link-fault tolerant NoC architecture introduced by Wu et al. In the process of eliminating this problem, an improved routing architecture is derived. The improvement simplifies the routing architecture, enabling successful verification using the CADP verification toolbox. The routing algorithm is proven to have several desirable properties including deadlock and livelock freedom, and tolerance to a single-link-fault. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码：24 / 39
页数：16
相关论文
共 50 条
  • [31] A General, Fault tolerant, Adaptive, Deadlock-free Routing Protocol for Network-on-chip
    Stroobant, Pieter
    Abadal, Sergi
    Tavernier, Wouter
    Alarcon, Eduard
    Colle, Didier
    Pickavet, Mario
    2018 11TH INTERNATIONAL WORKSHOP ON NETWORK ON CHIP ARCHITECTURES (NOCARC), 2018, : 35 - 40
  • [32] 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
  • [33] Double Stairs: A Fault-Tolerant Routing Algorithm for Networks-on-Chip
    Fakhrali, Saleh
    Zarandi, Hamid R.
    JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS, 2016, 25 (06)
  • [34] Fault Tolerant Mesh based Network-on-Chip Architecture
    Chatterjee, Navonil
    Chattopadhyay, Santanu
    2015 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS (ISCAS), 2015, : 417 - 420
  • [35] An Unified Online Fault-tolerant Mechanism for FIFO Faults in Network-on-Chip Router
    Xu, Linfu
    Hang, Yanxi
    Guo, Pengfei
    Dai, Qiang
    2016 13TH IEEE INTERNATIONAL CONFERENCE ON SOLID-STATE AND INTEGRATED CIRCUIT TECHNOLOGY (ICSICT), 2016, : 1419 - 1421
  • [36] Fault-Tolerant Application Mapping on Mesh-of-Tree based Network-on-Chip
    Bhanu, P. Veda
    Soumya, J.
    JOURNAL OF SYSTEMS ARCHITECTURE, 2021, 116
  • [37] Fault-Tolerant Unicast-Based Multicast for Reliable Network-on-Chip Testing
    Xiang, Dong
    Chakrabarty, Krishnendu
    Fujiwara, Hideo
    ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2018, 23 (06)
  • [38] Network on Chip: A Review of Fault Tolerant Adaptive Routing Algorithm
    Vindhya, N. S.
    Vidyavathi, B. M.
    2018 3RD INTERNATIONAL CONFERENCE ON ELECTRICAL, ELECTRONICS, COMMUNICATION, COMPUTER, AND OPTIMIZATION TECHNIQUES (ICEECCOT - 2018), 2018, : 1107 - 1110
  • [39] Fault-Tolerant Application Mapping on to ZMesh topology based Network-on-Chip Design
    Bhanu, P. Veda
    Mandapati, Nikita
    Soumya, J.
    Cenkeramaddi, Linga Reddy
    PROCEEDINGS OF THE 15TH IEEE CONFERENCE ON INDUSTRIAL ELECTRONICS AND APPLICATIONS (ICIEA 2020), 2020, : 142 - 147
  • [40] A Novel Approach to Optimize Fault-Tolerant Hybrid Wireless Network-on-Chip Architectures
    Dehghani, Abbas
    Jamshidi, Kamal
    ACM JOURNAL ON EMERGING TECHNOLOGIES IN COMPUTING SYSTEMS, 2016, 12 (04)
12345