A New Approach to Deadlock-Free Fully Adaptive Routing for High-Performance Fault-Tolerant NoCs

NoCs (Networks-on-chips) are considered as the paradigm of choice for on-chip communication as they solve the scalability concerns of traditional buses. Many research efforts have been aimed toward the design of adaptive routing algorithms that are flexible enough to avoid congested and defective areas in a NoC. However, to avoid deadlocks, most of these solutions either prohibit some turns, which limits path diversity and reduces fault-tolerance, or restrict the use of some virtual channels, which can enable full adaptiveness at the cost of an underutilization of virtual channels. In this work, we eliminate the trade-off between path diversity and virtual channel utilization by introducing a novel, topology-agnostic, deadlock-free routing algorithm capable of taking full advantage of virtual channels for performance boosting while providing very high fault-tolerance at the same time. Both an intuitive and a formal description of our routing algorithm are presented, and simulation results show the merits of our solution compared to other techniques from the literature.