Non-minimal, turn-model based NoC routing

In this study, it is shown that any deadlock-free, turn-model based minimal routing algorithm can be extended to a non-minimal routing algorithm. Specifically, three novel non-minimal NoC routing algorithms are proposed based on the Odd–Even, West-First, and Negative-First turn models, respectively. These algorithms are not only deadlock free and livelock free, but can also leverage non-minimal routing paths to avoid traffic congestion and improve fault tolerance. Moreover, these algorithms are backward compatible with existing minimal routing schemes. As a result, they represent an ideal routing solution to NoC-based interconnections designed for both existing and emerging embedded multicore systems.