Previous [1] [2] [3] [4] [5] [6] [7] [8] [9]


Journal of Information Science and Engineering, Vol.19 No.3, pp.433-449 (May 2003)

Resource Allocation for Independent Real-Time Tasks in
Heterogeneous Systems for Energy Minimization*

Yang Yu and Viktor K. Prasanna
Department of EE-Systems
University of Southern California
Los Angeles, CA 90089-2562, U.S.A.
E-mail: {yangyu, prasanna}

In recent years, power management and power reduction have become critical issues in portable systems that are designed for real-time use. In this paper, we study the problem of statically allocating a set of independent real-time tasks to a system consisting of heterogeneous processing elements, each enabled with discrete Dynamic Voltage Scaling. The goal is to minimize the overall energy dissipation of the system without violating the real-time requirements of the tasks. The problem is first formulated as an extended Generalized Assignment Problem. A linearization heuristic (LR-heuristic) is then extended to solve the problem. An analysis of the upper bound on the number of tasks that the heuristic may fail to allocate is also presented. Our experiments show that when the average utilization of the system is high, the LR-heuristic achieves 15% off the optimal energy dissipation for small size problems, while the performance of a classic greedy heuristic is around 90% off the optimal. A relative performance improvement of up-to 40% over the classic greedy heuristic is also observed for large size problems. Finally, an analytical performance comparison between the LR-heuristic and the greedy heuristic is presented.

Keywords: energy minimization, real-time, task allocation, generalized assignment problem, linearization heuristic

Full Text () Retrieve PDF document (200305_03.pdf)

Received May 15, 2002; accepted July 25, 2002.
Communicated by Biing-Feng Wang, Stephan Olariu and Gen-Huey Chen.
*This work is supported by the DARPA Power Aware Computing and Communication Program under contract No. F33615-C-00-1633. A preliminary version of the paper was presented at the 2002 International Conference on Parallel and Distributed Systems, Chungli, Taiwan.