For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Power-Aware Allocation of Chain-Like Real-Time Tasks on DVS Processors
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2006/12/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
resource allocation, power-aware, real-time task, dynamic voltage scaling,
Full Text: PDF>>
Viable techniques such as dynamic voltage scaling (DVS) provide a new design technique to balance system performance and energy saving. In this paper, we extend previous works on task assignment problems for a set of linear-pipeline tasks over a set of processors. Different from previous works, we revisit the problems with two additional system factors: deadline and energy-consumption, which are key factors in real-time and power-aware computation. We propose an O(nm2) time complexity algorithm to determine optimal task-assignment and speed-setting schemes leading to minimal energy consumption, for a given set of m real-time tasks running on n identical processors (with or without DVS supports). The same result can be extended to a restricted form of heterogeneous processor model. Meanwhile, we show that on homogeneous processor model more efficient algorithms can be applied and result in time complexity of O(m2) when m ≤ n. For completeness, we also discuss cases without contiguity constraints. We show under such cases the problems become at least as hard as NP-hard.