Gradient — An adaptive fault-tolerant routing algorithm for 2D mesh Network-on-Chips

Adaptive routing algorithms have been proposed for deadlock avoidance and load balancing. Furthermore they can be used to avoid failures on physical links. The classical algorithms divide the NoCs into several zones, and hence route the packets using one routing criterion. In this paper we present Gradient, a novel adaptive fault-tolerant routing algorithm. It considers sequence of alternative paths for packets when the main path fails. The proposed algorithm tolerates faults in worst traffic condition in NoCs. To evaluate the performance of the proposed algorithm, scenarios with various link-faults and node failure schemes are created. Hence the number of hops to the destination nodes and the number of alternative paths in faulty network are determined and compared with other adaptive routing algorithms. The results show that Gradient has more alternative routes with minimum hops, less latency and higher throughput than other routing algorithms.