Systematic construction of deadlock-free routing for NoC using integer linear programming

Abstract

Network-on-Chip (NoC) presents a promising solution for on-chip communication in highly integrated System-on-Chips (SoCs). This work addresses critical challenges in NoC design, including routing construction, application mapping, and particularly the issue of deadlocks in the widely-used wormhole routing method. In this paper, an Integer Linear Programming (ILP) approach for deadlock-free routing is proposed, applicable to arbitrary network topologies. We systematically analyze deadlock-free routing construction for mesh and torus topologies under uniform random traffic and provide alternative solutions to turn models. In the context of application-specific NoCs, application mapping, and deadlock-free routing are integrated within a single ILP. Through evaluation with several benchmark applications, it is demonstrated that the ILP method consistently delivers optimal solutions and could obtain better results than various heuristic methods within an acceptable time. Fault tolerance is also explored and existing techniques are incorporated into the ILP approach. As an illustrative example, application mapping and a 1-link-fault-tolerant deadlock-free routing for the MP3 application on a mesh network is performed.