ILP Formulation for Designing Rings in Routerless Network-on-Chip
Jie Xiao, Kwan Lawrence Yeung, Sugih Jamin · 2019
In routerless network-on-chip (NoC), any pair of cores are directly connected via at least one isolated ring, such that high-cost routers can be entirely abandoned. In this paper, we focus on the problem of designing a set of rings that guarantee the connectivity and minimize the average hop count for all core pairs. We propose the first optimal integer linear programing (ILP) to design rings for any n×m chips under any given wiring constraint, i.e., the maximum number of wires allowed between any adjacent cores. Numerical results show that our ILP performs much better and is more flexible than the existing algorithms. But our ILP is time-consuming to solve and future work should focus on reducing its complexity.