Adaptive BFS Based Fault Tolerant Routing Algorithm for Network on Chip
Ashish Kumar Yadav, Kunwer Mrityunjay Singh, Santosh Biswas · 2020
In modern-day deep sub-micron technology various cores and components are integrated on a single chip called System on Chip (SOC). To assure performance of SOC, intra-core communication must be efficient and accurate. Network on Chip (NOC) plays a vital role in communication among cores, memory, input-output, and other components. Increased density of components on-chip enhances the probability of failure. Failure can be due to faulty components, link failure, deadlock, livelock, starvation, congestion, etc. To avoid failure in communication, we need an efficient algorithm that must have properties like deadlock-free, livelock free, highly adaptive, fault-tolerant, minimal etc. In this paper, we propose a novel fault-tolerant, deadlock-free, livelock free, fully adaptive, and minimal breadth-first search (BFS) based routing algorithm which routes a packet from source to destination efficiently. The simulation results depict that our algorithm can route packets in the presence of faulty links or faulty components. It also gives the alternate routes while facing faults.