Multiprocessor Energy-Efficient Scheduling with Task Migration Considerations.
Journal
16th Euromicro Conference on Real-Time Systems (ECRTS 2004), 30 June - 2 July 1004, Catania, Italy, Proceedings
Pages
101-108
Date Issued
2004
Author(s)
Chen, Jian-Jia
Hsu, Heng-Ruey
Chuang, Kai-Hsiang
Yang, Chia-Lin
Pang, Ai-Chun
Abstract
This paper targets energy-efficient scheduling of tasks over multiple processors, where tasks share a common deadline. Distinct from many research results on heuristics-based energy-efficient scheduling, we propose approximation algorithms with different approximation bounds for processors with/without constraints on the maximum processor speed, where no task migration is allowed. When there is no constraint on processor speeds, we propose an approximation algorithm for two-processor scheduling to provide trade-offs among the specified error, the running time, the approximation ratio, and the memory space complexity. An approximation algorithm with a 1.13-approximation ratio for M-processor systems is also derived (M > 2). When there is an upper bound on processor speeds, an artificial-bound approach is taken to minimize the energy consumption with a 1.13-approximation ratio. An optimal scheduling algorithm is then proposed in the minimization of the energy consumption when task migration is allowed.
SDGs
Type
conference paper