Fault-Tolerant Routing for Irregular-Topology-Based Network-on-Chips

The designers favor irregular topologies for Network-on-Chip (NoC) architectures due to their lower energy consumptions, lower latencies, and higher throughputs than their regular counterparts. However irregular topologies generally allow only a single path between two communicating nodes. A permanent link failure in the fabrication process may make the entire chip useless because there is no alternative routing option for the transmitted data. In this study, we present a fault-tolerant routing generation algorithm that determines several alternative routing options for irregular-topology-based NoC, which has at least two alternative paths between all of its router pairs. The routing alternatives apply the shortest path routing to minimize the latency and energy consumption and they are stored in routing tables. While the designed NoC with no link failure uses the default optimized routing, we power up the corresponding routing table by external pins of the chip in case of a link failure. The objective of our algorithm is to minimize the number of routing options and to minimize the energy consumption of the alternative routings. Experiments on MP3 Encoder benchmark application show that our method determines routing options covering all single link failure with tolerable area, latency, and energy increase.