A greedy approach for latency-bounded deadlock-free routing path allocation for application-specific NoCs

Custom network-on-chip (NoC) structures have improved power and area metrics compared to regular NoC topologies for application-specific systems-on-a-chip (SoCs). The synthesis of an application-specific NoC is a combinatorial problem. This paper presents a novel heuristic for solving the routing path allocation step. Its main advantages are the support of realistic nonlinear cost estimation and the ability to handle latency constraints, which guarantee high performance of processing elements sensitive to communication delays. Additionally, the method generates deadlock-free routing by avoiding cycles in the channel dependency graph. The NoC is constructed sequentially in a greedy manner by selecting the routing path for each communication flow in such a way that the additional NoC HW resources are kept minimal. The routing path is found using a binary search cheapest bounded path (BSCBP) algorithm. The method is highly efficient and provides a NoC routing path allocation for a smart phone SoC with 25 processing elements and 96 flows in less than a minute.