CFPA: Congestion aware, fault tolerant and process variation aware adaptive routing algorithm for asynchronous Networks-on-Chip

摘要

Delays caused by congestion, faults and process variation (PV) degrade networks-on-chip (NoC) performance. A congestion aware, fault tolerant and process variation aware adaptive routing algorithm (CFPA) is introduced for congested and faulty asynchronous NoCs. The proposed routing algorithm maintains two routing tables to determine the packet path: one for routing directions based on propagation delay (including PV delay), and the other to keep track of the queuing delays at each router port. The queuing delay is used as an indication for congestion. The proposed routing tables store multiple paths to every destination via all polar directions, which makes CFPA a fault tolerant algorithm in case of path failures. The proposed algorithm is verified against other popular routing algorithms for NoCs with different topologies and network dimensions. On average, CFPA enhances the NoC throughput by 60% compared to the recently proposed routing algorithms. With CFPA, the impact of faults on NoC throughput is alleviated by 48%. In addition, the average delay of messages routed using CFPA is shorter than that of other algorithms by (26 similar to 75)% under process variation conditions. Furthermore, the proposed algorithm minimizes the impact of PV on NoC throughput to less than 5% of the nominal throughput for mesh topology. (C) 2019 Elsevier Inc. All rights reserved.