An Optimal Solution for the Heterogeneous Multiprocessor Single-Level Voltage-Setup Problem

A heterogeneous multiprocessor (HeMP) system consists of several heterogeneous processors, each of which is specially designed to deliver the best energy-saving performance for a particular category of applications. A low-power real-time scheduling algorithm is required to schedule tasks on such a system to minimize its energy consumption and complete all tasks by their deadlines. Existing works assume that processor speeds are known as a priori and cannot deliver the optimal energy-saving performance. The problem of determining the optimal voltage for each processor to minimize the total energy consumption is called a voltage-setup problem. To the best of our knowledge, this is the first paper to propose the optimal solution for the HeMP single-level voltage-setup problem. This paper provides an optimal solution for the HeMP single-level voltage-setup problem. We first formulate the problem as a nonlinear generalized assignment problem that has been proved to be nondeterministic polynomial-time hard (NP-hard). We next develop a pruning-based algorithm to obtain the optimal solution. A heuristic algorithm is also proposed to derive an approximate solution. After obtaining the optimal partition, each processor´s speed is determined by its final workload. In our simulations, we model more than a couple dozens of off-the-shelf embedded processors including ARM processor and TI DSP. The results show that the pruning-based algorithm reduces the time needed to derive the optimal solution by at least 98%, compared with the exhaustive search. Also, our heuristic algorithm achieves the minimum energy consumption over existing works.