TL;DR
This paper introduces a novel reconfigurable routing algorithm for 2D-Mesh Networks-on-Chip (NoCs) designed for fault tolerance in Massively Parallel Multi-Processor Systems-on-Chip (MP2-SoCs). The algorithm dynamically adapts to faulty routers by rerouting traffic around them, maintaining network connectivity and performance with minimal overhead.
What Problem Does This Paper Address?
As we move towards integrating billions of transistors onto a single chip (MP2-SoCs), the likelihood of manufacturing defects and early-life failures increases significantly. While deactivating faulty processing cores or memory is manageable, a faulty router within the Network-on-Chip (NoC) presents a more complex challenge. Traditional NoCs rely on regular topologies and deterministic routing algorithms for efficiency. When a router fails, this regularity is broken, potentially leading to network blockages and deadlocks if the routing algorithm cannot adapt. This paper addresses the critical need for a fault-tolerant routing solution that can dynamically reconfigure itself to circumvent faulty routers without compromising the network's overall performance or introducing excessive hardware complexity.
Methods
The core of this paper is a new reconfigurable routing algorithm designed to handle single faulty routers in a 2D-Mesh NoC. The approach is based on identifying "natural contours" around a faulty router and then defining "cycle-free contours" to ensure deadlock-free operation.
Here's a breakdown of the key techniques:
- Faulty Router Model: The paper assumes that a faulty router is detected by an external mechanism and that the entire cluster associated with the faulty router is deactivated.
- Neighbor and Contour Definitions: They define "neighbors" (direct and indirect) of a router and the concept of a "natural contour" formed by these neighbors around a faulty router.
- Cycle-Free Contour Identification: The paper analyzes the channel dependency graphs (CDGs) of these natural contours. They identify that one specific contour shape (C5) is not deadlock-free due to cycles. To resolve this, they propose a "turn-based fault-tolerant approach" by prohibiting specific turns (NE turns in the case of C5) to break these cycles. This results in 9 distinct cycle-free contours, each corresponding to a possible location of a single faulty router.
- Modified Routing Function: For routers that become part of a cycle-free contour around a faulty router, a modified routing function is defined. This function reroutes packets through the established cycle-free path, effectively restoring broken "unique paths" (the deterministic paths in the original X-First routing).
- Hardware Implementation: The algorithm is implemented by adding a small configuration register (4 bits) to each router. This register stores the router's configuration (e.g., NORMAL, N_OF_x, E_OF_x, etc.), and the existing X-First routing function is modified to incorporate this configuration information, dynamically altering its routing decisions.
Datasets
Not discussed in the paper. The evaluation is based on simulations of a 5x5 2D-Mesh network.
Key Insights and Ideas
- Dynamic Reconfiguration is Key: The most significant insight is that for fault tolerance in NoCs, static routing is insufficient. Dynamic reconfiguration of routing logic based on detected faults is essential to maintain connectivity and performance.
- Minimal Overhead for High Impact: The proposed solution achieves fault tolerance with a remarkably low hardware cost. The addition of a 4-bit configuration register and minor modifications to existing routing logic result in only an 8% increase in router area, which is a small fraction of the overall chip area. This makes it practical for large-scale MP2-SoCs.
- Cycle-Free Contours for Deadlock Prevention: The rigorous analysis of channel dependency graphs to identify and eliminate deadlock-prone configurations around faulty routers is a crucial step. By ensuring that all reconfigured paths remain deadlock-free, the algorithm guarantees reliable communication.
- Scalability of the Approach: The algorithm is designed to be scalable, meaning its complexity does not increase with the size of the mesh. This is vital for future MP2-SoCs that will feature thousands of processing cores.
Key Results
- Performance: The paper demonstrates that when the network load is not too high, the impact of the modified routing algorithm on average latency is negligible. However, the saturation threshold (the maximum load the network can handle before latency explodes) can be significantly improved, especially when the faulty router is located near the center of the mesh.
- Hardware Cost: The reconfigurable router incurs an area increase of only 8% compared to the original DSPIN router. This translates to approximately 0.2% of the total chip area, highlighting the cost-effectiveness of the solution.
- Deadlock Freedom: The proposed routing algorithm has been formally proven to be deadlock-free for any single faulty router topology in a 10x10 2D-Mesh using the ODI tool.
- Demonstrated Implementation: The algorithm was successfully implemented in a reconfigurable version of the DSPIN micro-network.
Limitations and Future Work
- Single Faulty Router: The current algorithm is designed to handle only single faulty routers. The paper mentions that the approach can be extended to one-faulty-region topology (a rectangle of faulty routers), as illustrated in Figure 12, but the detailed mechanism for this extension is not elaborated upon.
- Fault Detection Mechanism: The paper explicitly states that the fault detection mechanism (built-in self-test) is not addressed in this work.
- Configuration Bus: Similarly, the implementation of a robust configuration bus to distribute fault information to routers is also outside the scope of this paper.
- Future Work: The authors suggest that extending the algorithm to handle multiple faulty routers or faulty regions would be a valuable next step. Investigating the impact on performance and cost for these more complex scenarios would also be important.
Summary updated