Twist-Routing Algorithm for Faulty Network-on-Chips

Kunwei Zhang, Thomas MoscibrodaJournal of Computer and Communications 2016 · DOI

Abstract

This paper introduces Twist-routing, a new routing algorithm for faulty on-chip networks, which improves Maze-routing, a face-routing based algorithm which uses deflections in routing, and archives full fault coverage and fast packet delivery. To build Twist-routing algorithm, we use bounding circles, which borrows the idea from GOAFR+ routing algorithm for ad-hoc wireless networks. Unlike Maze-routing, whose path length is unbounded even when the optimal path length is fixed, in Twist-routing, the path length is bounded by the cube of the optimal path length. Our evaluations show that Twist-routing algorithm delivers packets up to 35% faster than Maze-routing with a uniform traffic and Erdos-Rényi failure model, when the failure rate and the injection rate vary.

Introduction

As semiconductor technology scales into the deep sub-micron regime, the reliability of on-chip components has become a primary concern. Factors such as oxide breakdown, electromigration, and thermal cycling increase the likelihood of permanent failures within the Network-on-Chip (NoC). Consequently, modern multi-core processors must employ robust routing strategies to maintain communication even when portions of the interconnect fail.

One popular approach is "deflection" routing, exemplified by Maze-routing. These algorithms are favored for their low hardware overhead, as they avoid large buffers and complex global routing tables. However, Maze-routing possesses a significant theoretical drawback: its path length is unbounded. A packet may traverse an excessively large "face" of the network graph, leading to high latency even when a much shorter path exists. Twist-routing is proposed as a solution that provides guaranteed performance bounds and superior efficiency.

The Twist-Routing Algorithm

Twist-routing enhances the foundations of Maze-routing by incorporating the concept of "bounding circles," a technique adapted from the GOAFR+ algorithm used in wireless ad-hoc networking. The algorithm operates primarily in two modes:

  1. Greedy Mode: The router attempts to forward the packet toward the destination using the shortest available path.
  2. Face-routing Mode: Upon encountering a fault or obstacle, the algorithm enters face-routing mode to navigate the boundary (or "face") of the failure.

The core innovation lies in the use of an imaginary bounding circle centered at the destination. When entering face-routing mode, a circle of radius $c$ is defined. If the packet reaches the boundary of this circle without finding a path back to greedy mode, it "twists"—reversing its traversal direction—and expands the circle's radius. This mechanism ensures the search area remains localized and grows only as required.

Flowchart of the Twist-routing algorithm logic.

By implementing this "twist" and expansion logic, the algorithm transforms the routing process from an unbounded search into one with a predictable $O(m^3)$ upper bound on path length, where $m$ is the optimal path length. This predictability is a critical requirement for real-time and high-performance hardware systems.

Experimental Evaluation

The performance of Twist-routing was evaluated using a custom simulator modeling a 32x32 mesh network. To simulate realistic failure scenarios, the researchers employed the Erdös-Rényi model, generating random link failures at rates of 10% and 30%. The experiments utilized a uniform traffic pattern, where every node communicates with every other node with equal probability.

The results demonstrate that Twist-routing significantly outperforms the state-of-the-art Maze-routing (combined with the minBD deflection mechanism). In high-failure environments (30% failure rate), Twist-routing achieved a 35% reduction in delivery time. Furthermore, these performance gains remained consistent across varying injection rates, proving the algorithm's robustness under heavy traffic loads. Crucially, Twist-routing maintains full fault coverage, guaranteeing packet delivery as long as a physical path exists.

Conclusion and Future Work

Twist-routing represents a significant advancement in fault-tolerant NoC design by providing a mathematical bound on path lengths and substantial latency improvements. By bridging the gap between wireless geometry and silicon architecture, it offers a scalable solution for future unreliable hardware.

Future research should address the algorithm's performance under non-uniform, "bursty" traffic patterns typical of real-world applications. Additionally, while the logic is designed for low cost, a detailed analysis of the hardware area and power overhead associated with storing the bounding circle radius ($c$) in flit headers is necessary. Finally, exploring localized alternatives to global age-based priority systems could further enhance the scalability of Twist-routing in massive NoC architectures.

Summary updated

Abstract

This paper introduces Twist-routing, a new routing algorithm for faulty on-chip networks, which improves Maze-routing, a face-routing based algorithm which uses deflections in routing, and archives full fault coverage and fast packet delivery. To build Twist-routing algorithm, we use bounding circles, which borrows the idea from GOAFR+ routing algorithm for ad-hoc wireless networks. Unlike Maze-routing, whose path length is unbounded even when the optimal path length is fixed, in Twist-routing, the path length is bounded by the cube of the optimal path length. Our evaluations show that Twist-routing algorithm delivers packets up to 35% faster than Maze-routing with a uniform traffic and Erdos-Rényi failure model, when the failure rate and the injection rate vary.
BibTeX
@article{zhang2016twist,
  author = {Kunwei Zhang and Thomas Moscibroda},
  title = {{Twist-Routing Algorithm for Faulty Network-on-Chips}},
  journal = {Journal of Computer and Communications},
  year = {2016},
  doi = {10.4236/jcc.2016.414001},
}
Figure