A fast and energy efficient branch and bound algorithm for NoC task mapping

This paper proposes an enhanced Branch and Bound (B&B) algorithm for Network-on-Chip (NoC) task mapping. The novelty of the algorithm can be summarized in two aspects. First, a more accurate method is proposed to estimate the lower bound cost. Second, an automatic method to generate the task binding rules is proposed based on the Task Binding Graph (TBG). Both of the two improvements contribute to designing a high speed B&B algorithm with global optimized mapping result, aiming to reduce the communication energy consumption. The experiment results show that the proposed algorithm is nearly 3.5 times faster and the communication energy consumption is 35% less than the state-of-art B&B algorithm in average. Comparing to the Genetic Algorithm, the proposed algorithm is similarly fast and reduce the communication energy consumption by 24% in average. Particularly, as the size of the NoC grows larger, the superiorities of our proposed algorithm become more significant.