Fault-Tolerant Networks-on-Chip Routing with Coarse and Fine-Grained Look-ahead

Research output: Contribution to journalArticle

27 Citations (Scopus)

Abstract

Fault tolerance and adaptive capabilities are challenges for modern Networks-on-Chip (NoC) due to the increase in physical defects in advanced manufacturing processes. Two novel adaptive routing algorithms, namely coarse and fine-grained look-ahead algorithms, are proposed in this paper to enhance 2D mesh/torus NoC system fault-tolerant capabilities. These strategies use fault-flag codes from neighbouring nodes to obtain the status or conditions of real-time traffic in a NoC region; then calculate the path weights and choose the route to forward packets. This approach enables the router to minimise congestion for the adjacent connected channels and also to bypass a path with faulty channels by looking ahead at distant neighbouring router paths. The novelty of the proposed routing algorithms is the weighted path selection strategies, which make near-optimal routing decisions to maintain the NoC system performance under high fault rates. Results show that the proposed routing algorithms can achieve performance improvement compared to other state of the art works under various traffic loads and high fault rates. The routing algorithm with fine-grained look-ahead capability achieves a higher throughput compared with the coarse-grained approach under complex fault patterns. The hardware area/power overheads of both routing approaches are relatively low which does not prohibit scalability for large scale NoC implementations.
LanguageEnglish
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume2015
DOIs
Publication statusPublished - 22 Jul 2015

Fingerprint

Routing algorithms
Routers
Adaptive algorithms
Fault tolerance
Scalability
Throughput
Network-on-chip
Hardware
Defects

Keywords

  • Networks-on-Chip
  • adaptive routing
  • fault tolerance
  • hardware reliability

Cite this

@article{76cd2d2315ba484f8ed8e04d476f2ace,
title = "Fault-Tolerant Networks-on-Chip Routing with Coarse and Fine-Grained Look-ahead",
abstract = "Fault tolerance and adaptive capabilities are challenges for modern Networks-on-Chip (NoC) due to the increase in physical defects in advanced manufacturing processes. Two novel adaptive routing algorithms, namely coarse and fine-grained look-ahead algorithms, are proposed in this paper to enhance 2D mesh/torus NoC system fault-tolerant capabilities. These strategies use fault-flag codes from neighbouring nodes to obtain the status or conditions of real-time traffic in a NoC region; then calculate the path weights and choose the route to forward packets. This approach enables the router to minimise congestion for the adjacent connected channels and also to bypass a path with faulty channels by looking ahead at distant neighbouring router paths. The novelty of the proposed routing algorithms is the weighted path selection strategies, which make near-optimal routing decisions to maintain the NoC system performance under high fault rates. Results show that the proposed routing algorithms can achieve performance improvement compared to other state of the art works under various traffic loads and high fault rates. The routing algorithm with fine-grained look-ahead capability achieves a higher throughput compared with the coarse-grained approach under complex fault patterns. The hardware area/power overheads of both routing approaches are relatively low which does not prohibit scalability for large scale NoC implementations.",
keywords = "Networks-on-Chip, adaptive routing, fault tolerance, hardware reliability",
author = "Junxiu Liu and Jim Harkin and Yuhua Li and Liam Maguire",
year = "2015",
month = "7",
day = "22",
doi = "10.1109/TCAD.2015.2459050",
language = "English",
volume = "2015",
journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",
issn = "0278-0070",

}

TY - JOUR

T1 - Fault-Tolerant Networks-on-Chip Routing with Coarse and Fine-Grained Look-ahead

AU - Liu, Junxiu

AU - Harkin, Jim

AU - Li, Yuhua

AU - Maguire, Liam

PY - 2015/7/22

Y1 - 2015/7/22

N2 - Fault tolerance and adaptive capabilities are challenges for modern Networks-on-Chip (NoC) due to the increase in physical defects in advanced manufacturing processes. Two novel adaptive routing algorithms, namely coarse and fine-grained look-ahead algorithms, are proposed in this paper to enhance 2D mesh/torus NoC system fault-tolerant capabilities. These strategies use fault-flag codes from neighbouring nodes to obtain the status or conditions of real-time traffic in a NoC region; then calculate the path weights and choose the route to forward packets. This approach enables the router to minimise congestion for the adjacent connected channels and also to bypass a path with faulty channels by looking ahead at distant neighbouring router paths. The novelty of the proposed routing algorithms is the weighted path selection strategies, which make near-optimal routing decisions to maintain the NoC system performance under high fault rates. Results show that the proposed routing algorithms can achieve performance improvement compared to other state of the art works under various traffic loads and high fault rates. The routing algorithm with fine-grained look-ahead capability achieves a higher throughput compared with the coarse-grained approach under complex fault patterns. The hardware area/power overheads of both routing approaches are relatively low which does not prohibit scalability for large scale NoC implementations.

AB - Fault tolerance and adaptive capabilities are challenges for modern Networks-on-Chip (NoC) due to the increase in physical defects in advanced manufacturing processes. Two novel adaptive routing algorithms, namely coarse and fine-grained look-ahead algorithms, are proposed in this paper to enhance 2D mesh/torus NoC system fault-tolerant capabilities. These strategies use fault-flag codes from neighbouring nodes to obtain the status or conditions of real-time traffic in a NoC region; then calculate the path weights and choose the route to forward packets. This approach enables the router to minimise congestion for the adjacent connected channels and also to bypass a path with faulty channels by looking ahead at distant neighbouring router paths. The novelty of the proposed routing algorithms is the weighted path selection strategies, which make near-optimal routing decisions to maintain the NoC system performance under high fault rates. Results show that the proposed routing algorithms can achieve performance improvement compared to other state of the art works under various traffic loads and high fault rates. The routing algorithm with fine-grained look-ahead capability achieves a higher throughput compared with the coarse-grained approach under complex fault patterns. The hardware area/power overheads of both routing approaches are relatively low which does not prohibit scalability for large scale NoC implementations.

KW - Networks-on-Chip

KW - adaptive routing

KW - fault tolerance

KW - hardware reliability

U2 - 10.1109/TCAD.2015.2459050

DO - 10.1109/TCAD.2015.2459050

M3 - Article

VL - 2015

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

T2 - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

SN - 0278-0070

ER -