Energy and communication aware task mapping for MPSoCs

Minimizing energy consumption and network load is a major challenge for network-on-chip (NoC) based multi-processor systems-on-chip (MPSoCs). Efficient task and core mapping can greatly reduce the overall energy consumption and communication overhead among the interdependent tasks. In this paper, we propose a novel Knapsack based bin packing algorithm for workload consolidation that places tasks in such a manner that utilization of available processing elements is maximized, while network overhead, regarding the communication among the tasks, is minimized. We also propose a task swapping algorithm that attempts to further optimize the task placement produced by the bin packing algorithms. Moreover, several core mapping techniques are implemented and the performance of each technique is evaluated under varying configurations. In addition, we also apply a Pareto-efficient algorithm, on top of the bin packing algorithms, attempting to explore the solution in two dimensions, i.e., energy consumption and network load. The experimental results show that the proposed Knapsack based bin packing algorithm coupled with the Pareto-efficient algorithm achieves significant energy savings and reduction in network load as compared to state-of-the-art algorithms, as well as the greedy algorithm. Particularly, the Pareto-efficient algorithm when applied on top of the Knapsack algorithm shows on average 50% and 55% reduction in energy consumption and network load as compared to the greedy algorithm, respectively. While the proposed Pareto-efficient algorithm applied with Knapsack algorithm also demonstrate superior performance compared to three other state-of-the-art heuristics.