Power-Aware Allocation of Chain-Like Real-Time Tasks on DVS Processors

Chun-Chao YEH  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.12   pp.2907-2918
Publication Date: 2006/12/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.12.2907
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computation and Computational Models
Keyword: 
resource allocation,  power-aware,  real-time task,  dynamic voltage scaling,  

Full Text: PDF>>
Buy this Article




Summary: 
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 mn. For completeness, we also discuss cases without contiguity constraints. We show under such cases the problems become at least as hard as NP-hard.