Congestion-aware core mapping for Network-on-Chip based systems using betweenness centrality

Abstract

Network congestion poses significant impact on application performance and network throughput in Network-on-Chip (NoC) based systems. Efficient core mapping can significantly reduce the network contention and end-to-end latency leading to improved application performance in NoC based multicore systems. In this work, we propose a Congestion-Aware (CA) core mapping heuristic based on betweenness centrality metric. The proposed CA algorithm optimizes core mapping using betweenness centrality of links to alleviate congestion from highly loaded NoC links. We use modified betweenness centrality metric to identify highly loaded NoC links that are more prone to congestion. In contrast to traditional betweenness centrality metric, which is generally used to measure the structural/static characteristics of the system, the adapted betweenness centrality metric utilizes the volume of communication traversing through the edges (NoC links) to capture the operational and dynamic characteristics of the system. The experimental results demonstrate that our proposed algorithm achieved significantly lower average channel load and end-to-end latency compared to the baseline First Fit (FF) and Nearest Neighbor (NN) core mapping algorithms. Particularly, CA algorithm achieved up to 46% and 12% lower channel load and end-to-end latency compared to FF algorithm, respectively. Moreover, proposed algorithm exhibits an average gain of 32% in terms of reduced network energy consumption compared to the baseline configuration. 2016 Elsevier B.V.