Abstract
In order to alleviate the problem raised in Gomez's method, our method selects the qualified intermediate node among all the candidates by its residual bandwidth without over-stressing any particular node. In addition, deterministic routing is applied along both subpaths to guarantee deadlock-free and in-order message delivery. It thereby achieves traffic workload balance across the network and graceful performance degradation even in the presence of faults.
Introduction
As transistors shrink to the deep sub-micron level, On-Chip Networks (OCNs) become increasingly susceptible to hardware faults caused by manufacturing variations or environmental factors. When a link or a router fails, the network must find a way to route data around the "dead" zone. Existing solutions, such as Gomez’s method, often funnel multiple data flows through the same "shortest" path, creating massive traffic bottlenecks, high latency, and reduced throughput. Furthermore, many fault-tolerant algorithms rely on adaptive routing, which can lead to out-of-order packet delivery, complicating cache coherence in many-core systems.
IDFT (Intermediate node based Deterministic Fault Tolerant routing) addresses these issues by intelligently selecting intermediate nodes based on available link bandwidth and using deterministic routing for each leg of the journey.
Methodology
The IDFT algorithm operates in two primary phases to ensure efficient and reliable data transmission in faulty 2D mesh networks.
- Flow Categorization: The system first determines if a message can reach its destination using standard XY routing. Flows are categorized into Class 1 (no faults encountered) and Class 2 (faults encountered).
- Bandwidth-Aware Node Selection: For Class 2 flows, the algorithm identifies potential intermediate nodes ($I$). Unlike previous methods that prioritize the shortest path, IDFT calculates a weight for each link based on its residual bandwidth using the function $W = 1 / (1 - \sum d_i / C)$, where $d_i$ is demand and $C$ is capacity. This "penalizes" congested links and encourages the use of non-minimal paths with more available capacity.
- Deterministic Sub-paths: Once an intermediate node is selected, the message travels from Source $\rightarrow$ $I$ and then from $I \rightarrow$ Destination using deterministic XY routing. This ensures in-order delivery and deadlock-free transmission.
Experimental Setup
The researchers evaluated IDFT using the HORNET cycle-accurate multicore simulator on an $8 \times 8$ 2D mesh topology. The algorithm was tested under standard synthetic traffic patterns, including TRANSPOSE, SHUFFLE, and BIT-COMPLEMENT, with fault rates of 5%, 10%, and 15%.
Results and Discussion
IDFT significantly outperforms baseline methods by effectively balancing the network load. By relaxing the requirement for minimal paths, IDFT utilizes idle links across the chip, preventing hotspots near fault zones.
Key results include:
- Throughput Boost: At a 15% fault rate, IDFT achieved up to 49.9% higher saturation throughput compared to the baseline (Gomez’s method).
- Lower Latency: Average packet latency was reduced by 13.6% to 21.6% across various fault rates when using two virtual channels (VCs).
- Balanced Power: Power maps indicated that IDFT spreads traffic load evenly, avoiding the high power density and heat associated with localized congestion in baseline methods.
Conclusion
IDFT provides a robust solution for fault-tolerant routing in NoCs by combining bandwidth-aware intermediate node selection with deterministic sub-paths. While the method requires an increase in Virtual Channels (VCs) to manage deadlocks as the number of intermediate nodes grows, it offers a significant improvement in throughput and latency. Future work will explore more area-efficient VC management and performance under real-world application workloads.
Summary updated