An Abstraction to Support Design of Deadlock-free Routing Algorithms for Large and Hierarchical NoCs

New techniques and tools will be required to handle the complexity of on-chip networks required for building multi-core platforms with hundreds of cores. The concepts of hierarchy and abstraction, which have been useful in the design and analysis of electronic systems, will also be useful in the network design area. In this paper we propose an abstraction for networks to reduce the complexity of design and analysis of deadlock-free routing for large and hierarchical networks. Raising the level of abstraction necessarily leads to loss of some information. This loss of information in turn often results in loss of performance of the design as compared to when the network was considered at a lower level of abstraction. We show that our proposed abstraction leads to very small loss of performance. In particular, we show that average increase in communication distance (hops) is low or comparable to non-abstract design. Our simulation-based evaluation indicates that abstract routing design has no negative impact on message latency. On the contrary, abstract routing shows a slight advantage, which increases if more network communication is local and confined within subnets.