Developing Deadlock-Free Routing Algorithms in Torus NoC: A Formal Approach

Torus is a symmetric Network-on-Chip (NoC) topology with uniform node degree providing very high path diversity between a pair of source and destination. Moreover, the Wraparound Channels (WCs) in the torus can significantly reduce the hop count, thereby reducing overall communication latency. However, the WCs also create cyclic paths that may lead to a NoC deadlock. As a consequence, very few deadlock-free routing algorithms for torus-based NoC exist that do not have significant implementation overhead. Furthermore, the existing routing algorithms do not unlock the full potential of the torus-based NoC topology. In this work, we present a formal modeling-based technique for developing deadlock-free routing algorithms for torus-based NoC. This method systematically combines routing algorithms of mesh with WCs of torus to develop deadlock-free routing algorithms for torus. Using the proposed technique, we develop three novel routing algorithms and verify their deadlock-freedom using Directional Dependency Graph (DDG). We then evaluate the proposed routing algorithms using both synthetic and real traffic patterns. The primary objective of this work is to present a technique that can generate multiple routing algorithms and not the single best routing algorithm. Hence, we do not claim that the three proposed algorithms are the best-performing ones. Nevertheless, we show that they can save hop counts by more than 10% and latency by 8% compared to the competitive methods. The performance of our algorithms is comparable even with state-of-the-art Table-based rout- ing and deadlock recovery-based technique.