Lagrangian relaxation-based routing path allocation for application-specific network-on-chips

The application-specific network-on-chip (ASNoC) has been proposed as a promising solution to address the global communication challenges in terms of nanoscale system-on-chips. However, as the number of cores increases on chips, the power consumption and communication latency present major challenges for routing path allocation in ASNoCs. In this study, given the floorplan results and clustering of cores, we propose an efficient routing path allocation algorithm based on the Lagrangian relaxation for routing the traffic flows while minimizing the power consumption under constraints, such as latency constraints, physical link capacity constraints, and switch port constraints. In addition, we propose a modified shortest path algorithm based on the backtracking method to prevent deadlocks, which is critical for the correct operation of NoCs. Our experimental results demonstrate the effectiveness of the proposed method; the method has power overheads of less than 1% compared with designs that do not support a deadlock removal method.