A new fault-tolerant deadlock-free fully adaptive routing in NOC

Abstract

Future applications will require processors with many cores communicating through a regular interconnection network. As the semiconductor industry advances to the deep sub-micron and nano technology points, the on-chip components are more prone to the defects during manufacturing and faults during system life time. In order to ensure the reliability of network-on-chip (NoC) under the faulty circumstance, a fully adaptive fault tolerant and congestion aware routing algorithm is proposed. This algorithm is able to route a message in presence of any number of faulty links which not allows interconnect network partitioned. For the purpose of detection and elimination of deadlock, we use a time-out scheme and then a virtual source for packet reinjection. In addition, a novel Livelock-avoidance algorithm is presented based on exploring loop in the recorded path in header flit. The deadlock and livelock-freeness of our algorithm are fully analyzed for real traffic SPLASH-2 benchmarks. The experimental result shows that we can achieve less latency and higher throughput for different fault rates. In addition, the hardware overhead of the algorithm is shown to have a reasonably low cost which maintains scalability for large NoC implementations.