Application Specific Routing Algorithms for Networks on Chip

In this paper, we present a methodology to develop efficient and deadlock-free routing algorithms for Network-on-Chip (NoC) platforms that are specialized for an application or a set of concurrent applications. The proposed methodology, called the Application- Specific Routing Algorithm (APSRA), exploits the application-specific information regarding pairs of cores that communicate and other pairs that never communicate in the NoC platform to maximize communication adaptivity and performance. The methodology also exploits the known information regarding concurrency/nonconcurrency of communication transactions among cores for the same purpose. The methodology does not require virtual channels to guarantee deadlock freedom. We demonstrate, through analysis of adaptivity and simulation-based evaluation of latency and throughput, that algorithms produced by the proposed methodology give significantly higher performance as compared to other deadlock-free algorithms for both homogeneous and heterogeneous 2D mesh topology NoC systems. Since the APSRA methodology is topology agnostic, the most appropriate general implementation of the routing function within the router is using a table. A table-based implementation of the router is costlier as compared to an algorithm-based implementation. We also propose a technique to compress the routing table in a mesh topology NoC to very small sizes with very little negative effect on routing adaptivity.