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 条

[41] Fault tolerant algorithms for network-on-chip interconnect
Pirretti, M
Link, GM
Brooks, RR
Vijaykrishnan, N
Kandemir, M
Irwin, MJ
VLSI 2004: IEEE COMPUTER SOCIETY ANNUAL SYMPOSIUM ON VLSI, PROCEEDINGS, 2004, : 46 - 51
[42] ACO-BASED FAULT-AWARE ROUTING ALGORITHM FOR NETWORK-ON-CHIP SYSTEMS
Lin, Chia-An
Hsin, Hsien-Kai
Chang, En-Jui
Wu, An-Yeu
2013 IEEE WORKSHOP ON SIGNAL PROCESSING SYSTEMS (SIPS), 2013, : 342 - 347
[43] A Fault-Tolerant and Congestion-Aware Routing Algorithm for Networks-on-Chip
Valinataj, Mojtaba
Mohammadi, Siamak
Plosila, Juha
Liljeberg, Pasi
PROCEEDINGS OF THE 13TH IEEE SYMPOSIUM ON DESIGN AND DIAGNOSTICS OF ELECTRONIC CIRCUITS AND SYSTEMS, 2010, : 139 - 144
[44] Router-shared-pair mesh: a reconfigurable fault-tolerant network-on-chip architecture
Chen, Yali
Ren, Kaixin
Gu, Naijie
INTERNATIONAL JOURNAL OF EMBEDDED SYSTEMS, 2018, 10 (06) : 526 - 536
[45] Fault-Tolerant Network-On-Chip Router Architecture Design for Heterogeneous Computing Systems in the Context of Internet of Things
Rashid, Muhammad
Baloch, Naveed Khan
Shafique, Muhammad Akmal
Hussain, Fawad
Saleem, Shahroon
Zikria, Yousaf Bin
Yu, Heejung
SENSORS, 2020, 20 (18) : 1 - 20
[46] A fault-tolerant deadlock-free routing algorithm in a meshed network
Lee, D
Moon, D
Yun, I
Kim, H
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2002, E85D (04): : 722 - 726
[47] Dynamic Reliability Analysis Model for Fault-tolerant Network Routing
Wang Bin
Wu Chunming
Yang Qiang
Qian Yaguan
Wang Xiaonan
CHINESE JOURNAL OF ELECTRONICS, 2012, 21 (03): : 500 - 504
[48] A survey of routing algorithm for mesh Network-on-Chip
Wu, Yue
Lu, Chao
Chen, Yunji
FRONTIERS OF COMPUTER SCIENCE, 2016, 10 (04) : 591 - 601
[49] A survey of routing algorithm for mesh Network-on-Chip
Yue Wu
Chao Lu
Yunji Chen
Frontiers of Computer Science, 2016, 10 : 591 - 601
[50] A Strategy for Fault Tolerant Reconfigurable Network-on-Chip Design
Chatterjee, Navonil
Mukherjee, Priyajit
Chattopadhyay, Santanu
2016 20TH INTERNATIONAL SYMPOSIUM ON VLSI DESIGN AND TEST (VDAT), 2016,

← 1 2 3 4 5 →