Fault Tolerant and Congestion-Aware Routing Algorithm in a Partially Connected ۳D Network on Chip

Abstract— Network-on-Chips (NoCs) have been accepted as a viable communication platform in many-core systems. However, they possess high network latency and consume large power. In this paper, we introduce a minimal routing algorithm in partially connected ۳D Network-on-Chip, in which a fixed place of TSVs is designed to reduce TSV implementation cost which can be provided as a standard in the automotive electronics industry. This routing algorithm employs network congestion and fault information to find the minimum path while avoiding traversing the faulty paths. The proposed algorithm consists of in-layer routing and interlayer routing. The intra-layer routing algorithm employs an information propagation network to propagate control information between nodes located in the same layer. It uses a parameter called index to select the optimum path between nodes in the same layer. The index value is updated periodically based on a faulty link or a faulty node and published across networks. The interlayer routing algorithm is performed based on the minimum path to the elevator routers. The proposed algorithm reduces the average packet latency and increases the network throughput. The simulation results indicate that our routing algorithm improves network latency by ۱۵.۳% compared to two other routing algorithms.

Keywords:

Keywords— Fault-tolerant , Congestion-aware , Index Mechanism , ۳D-NoC , routing