Integer Linear Programming Based Design of Deadlock-Free Routing for Chiplet-Based Systems

Chiplet-based systems have become prominent in large Systems-on-Chips (SoCs) as a means to mitigate increasing design costs. However, the integration of multiple chiplets introduces new challenges in the interconnection network, potentially leading to deadlocks. In this paper, we propose an Integer Linear Programming (ILP) based design approach to address this issue. Our method considers various design factors for deadlock-free routing, such as topology, latency, load balancing, path diversity, and fault tolerance, applicable to both general-purpose chiplets and application-specific chiplets. It facilitates the determination of optimal turn restrictions for general-purpose chiplets or constructs optimal deadlock-free routing paths for application-specific chiplets if the communication patterns are known. The results demonstrate the capability of the method to find optimal solutions under various design considerations.