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 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.