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

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.

Introduction

As transistor scaling approaches physical limits, hardware defects in Network-on-Chip (NoC) architectures are becoming inevitable. Furthermore, dynamic power-gating and reconfigurable wireless links result in shifting network topologies. Traditional routing protocols often struggle with these dynamic environments, either failing when links break or requiring resource-intensive routing tables. This paper proposes a topology-agnostic, greedy routing protocol that ensures connectivity as long as a physical path exists, without the overhead of large tables or virtual channels.

Problem Statement

Traditional NoC routing typically relies on rigid logic (e.g., XY routing) or extensive routing tables. Rigid logic is fragile; a single link failure can disconnect nodes. Routing tables, while flexible, consume significant silicon area and require costly recomputations upon topology changes. Moreover, many fault-tolerant schemes unnecessarily deactivate healthy nodes within "fault regions." The objective is a protocol that is topology-agnostic, table-less, deadlock-free, and robust enough to provide 100% fault coverage.

Proposed Methodology

The core of the proposed solution is tree-based greedy routing. The process involves:

  1. Spanning Tree Embedding: The network constructs one or more Breadth-First Search (BFS) spanning trees. Nodes are assigned virtual coordinates based on their path from the root.
  2. Tree Distance Calculation: Routing decisions are based on "tree distance"—the number of hops between nodes along the tree structure—rather than physical distance.
  3. Greedy Forwarding: Routers evaluate all neighbors and select the one that minimizes the tree distance to the destination.
  4. Deadlock Prevention: To ensure a cycle-free environment, packets can move "up" or "sideways" in the tree freely, but once a "down" step toward a leaf is taken, subsequent moves must only be "down."
  5. Multi-Tree Optimization: To mitigate the "long path" issue inherent in single-tree structures, multiple trees rooted at the same node are used, each favoring different directional growth.
Tree-based coordinate system and greedy routing logic in a 4x4 mesh.

Experimental Setup

The protocol was evaluated using graph-based simulations on 2D mesh networks (4x4 and 8x8). The researchers simulated random link failures with probabilities ranging from 0% to 25%. To ensure statistical significance, each data point represents results from at least 250,000 source-destination pairs.

Results and Discussion

The simulations demonstrated that greedy routing on tree distances effectively avoids local minima, providing a mathematical guarantee of reaching the destination. The multi-tree approach significantly reduces "stretch"—the ratio of the actual path length to the optimal shortest path.

Mean stretch vs. link failure probability for different mesh sizes and tree counts.

Key findings include:

  • Efficiency: In an 8x8 mesh without failures, the multi-tree variant consistently finds the minimal route. With 25% link failures, the mean stretch remains remarkably low (under 1.14).
  • Optimality: Over 75% of routes found were the absolute shortest paths.
  • Resource Savings: By eliminating routing tables and virtual channels, the protocol reduces hardware overhead.
  • Adaptivity: The degree of adaptiveness improves relative to available minimal paths as the number of faults increases.

Conclusion and Future Work

While the protocol is highly effective, some challenges remain. Virtual coordinates can become long in complex topologies, potentially requiring compression techniques like run-length encoding. Additionally, while routing is distributed, the reliance on a shared root for tree construction creates a central point for configuration. Future work will focus on optimizing address sizes and exploring decentralized root management. This protocol represents a major step toward resilient, "plug-and-play" NoC architectures.

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},
}
Figure