A General, Fault tolerant, Adaptive, Deadlock-free Routing Protocol for Network-on-chip

Pieter Stroobant, Sergi Abadal, Wouter Tavernier, Eduard Alarcón, Didier Colle, Mario Pickavet

As we push transistor scaling to its limits, the "perfect" silicon chip is becoming a myth. Modern Network-on-Chip (NoC) architectures are increasingly plagued by hardware defects, and the rise of dynamic power-gating and reconfigurable wireless links makes the network topology a moving target.

In their paper, "A General, Fault tolerant, Adaptive, Deadlock-free Routing Protocol for Network-on-chip," Pieter Stroobant and his colleagues propose a routing solution that doesn't just survive these challenges—it thrives on them.

TL;DR

The authors introduce a topology-agnostic, greedy routing protocol that guarantees a path will be found as long as one exists, all without using bulky routing tables or virtual channels. By using a tree-based coordinate system, the algorithm remains deadlock-free and highly adaptive to permanent hardware faults.

What Problem Does This Paper Address?

Traditional NoC routing often relies on rigid logic (like XY routing) or massive routing tables. Rigid logic breaks when a single link fails, and routing tables consume precious silicon area and require expensive recomputations when the topology changes.

Furthermore, many "fault-tolerant" methods are forced to deactivate perfectly healthy nodes if they fall into a "fault region" (like a rectangular block of failures). The researchers set out to create a protocol that is:

  1. Topology-agnostic: It works on any network shape.
  2. Table-less: It saves area by calculating routes on the fly.
  3. Deadlock-free: It prevents "traffic jams" where packets wait on each other in a circle.
  4. Robust: It achieves 100% fault coverage—if a physical path exists, the packet gets through.

Methods

The core innovation is the use of tree-based greedy routing.

  1. Spanning Tree Embedding: The network builds one or more Breadth-First Search (BFS) spanning trees. Each node is assigned a "virtual coordinate" based on its position in the tree (the path from the root to that node).
  2. Tree Distance: Instead of physical distance, the router calculates "tree distance"—how many hops it takes to get from node A to node B along the tree.
  3. Greedy Forwarding: When a packet arrives, the router looks at all its neighbors (even those not in the tree) and picks the one that minimizes the tree distance to the destination.
  4. Deadlock Prevention: To prevent cycles, the authors enforce a strict rule: a packet can move "up" or "sideways" in the tree as much as it wants, but once it takes a "down" step toward a leaf, it can only move down. This ensures no circular dependencies can form.
  5. Multi-Tree Optimization: To avoid the "long path" problem (where two nodes are physically close but far apart on a specific tree), the authors use multiple trees rooted at the same node but grown with different directional preferences (e.g., one favoring North-South, another East-West).

Datasets

The authors evaluated their protocol using graph-based simulations of 2D mesh networks.

  • Topologies: 4x4 and 8x8 mesh networks.
  • Fault Models: They simulated random link failures with probabilities ranging from 0% to 25%.
  • Scale: Every data point was calculated over at least 250,000 source-destination pairs to ensure statistical significance.

Key Insights and Ideas

  • Greedy is Good (with a Tree): Greedy routing on physical coordinates often gets stuck in "local minima" (dead ends). By using tree distance, the authors provide a mathematical guarantee that there are no local minima—the gradient always leads to the destination.
  • Table-less Adaptivity: Because the routing is based on local neighbor checks and virtual coordinates, the system doesn't need a global map. If a link fails, the router simply picks the next best neighbor.
  • The Multi-Tree "Aha": A single tree can be inefficient. By rooting multiple trees at the same central node, the system can choose the tree that offers the shortest path for a specific destination, significantly reducing "stretch" (the ratio of the chosen path to the absolute shortest path).

Key Results

  • High Efficiency: In an 8x8 mesh with no failures, the multi-tree algorithm always finds the minimal route. Even with 25% link failures, the "mean stretch" remains below 1.14, meaning paths are only 14% longer than the theoretical optimum on average.
  • Optimal Paths: For over 75% of source-destination pairs, the algorithm found the absolute shortest path possible.
  • Area Savings: By eliminating routing tables and the need for virtual channels (which require extra buffers), the protocol significantly reduces the hardware overhead of the NoC routers.
  • Adaptivity: As the number of faults increases, the "degree of adaptiveness" (the number of legal paths the algorithm can choose from) actually improves relative to the number of available minimal paths.

Limitations and Future Work

  • Address Size: In very complex or irregular topologies, the "virtual coordinate" (the path from the root) can become long. The authors suggest run-length encoding to compress these addresses, but this adds a layer of complexity to the header flit.
  • Root Bottleneck: While the routing is distributed, all trees must share a root to maintain the deadlock-free proof. While the root isn't a single point of failure for routing, it is a central point for tree construction.
  • Minimal Path Guarantee: While the results are close to optimal, the algorithm is still greedy and does not guarantee the absolute shortest path in every single fault scenario.

This work represents a significant step toward "plug-and-play" NoCs that can handle the messy reality of modern silicon manufacturing and dynamic power management.

Summary updated

Abstract

The paper presents a topology-agnostic greedy protocol for network-on-chip routing. The proposed routing algorithm can tolerate any number of permanent faults, and is proven to be deadlock-free. We introduce a specialized variant of the algorithm, which is optimized for 2D mesh networks, both flat and wireless. The adaptiveness and minimality of several variants this algorithm are analyzed through graph-based simulations.
BibTeX
@inproceedings{stroobant2018general,
  author = {Pieter Stroobant and Sergi Abadal and Wouter Tavernier and Eduard Alarcón and Didier Colle and Mario Pickavet},
  title = {{A General, Fault tolerant, Adaptive, Deadlock-free Routing Protocol for Network-on-chip}},
  booktitle = {NoCArc@MICRO},
  year = {2018},
  url = {https://openreview.net/forum?id=6rN040bSIz},
}

Loading related content...

Figure