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

• Published in: IEEE transactions on computer-aided design of integrated circuits and systems 2009-11, Vol.28 (11), p.1705-1718
• Main Authors: Chu, E.T.-H., Tai-Yi Huang, Yu-Che Tsai
• Format: Article
• Language: English
• Subjects: Algorithms; Delivery scheduling; Digital signal processing; Embedded system; Energy consumption; Energy-aware systems; Hemp; heterogeneous multiprocessors (HeMPs); Heuristic; Heuristic algorithms; Heuristic methods; Mathematical models; NP-hard problem; Optimization; Partitioning algorithms; Processor scheduling; Processors; Real time systems; Scheduling algorithm; Studies; Voltage; voltage setup
• ISSN: 0278-0070; 1937-4151
• DOI: 10.1109/TCAD.2009.2028683

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.