Minimizing System Cost with Efficient Task Assignment on Heterogeneous Multicore Processors Considering Time Constraint

Abstract

High-performance computing systems typically employ heterogeneous multicore design to improve both execution performance and efficiency. Task assignment is critical in exploiting the diversity of computation capability, energy consumption, as well as communication cost on heterogeneous multicore processors. In this paper, we explore the opportunity of task assignment on heterogeneous multicore processors to minimize execution and communication costs considering time constraint. The general heterogeneous task assignment problem is NP-Complete. However, we find that optimal task assignment can be achieved for widely used, tree-shaped task graphs using dynamic programming. We first propose a dynamic programming algorithm, the Optimal Tree Assign (OTA) algorithm, to generate optimal assignments for trees. Then, we develop the Integer Linear Programming model of the general task assignment problem for Directed Acyclic Graphs. A polynomial-time heuristic, the Extended Tree Assignment algorithm, is also proposed to produce near-optimal solutions for the general heterogeneous task assignment problem efficiently. The experimental results show that the proposed algorithms outperform both homogeneous task assignment method and greedy strategy for all the benchmarks. The OTA algorithm reduces the total system time by 42.5 percent and 23.5 percent on average compared with the homogeneous task assignment method and greedy algorithm, respectively.