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

Chun-Chao YEH

doi:10.1093/ietisy/e89-d.12.2907

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

Chun-Chao YEH

Full Text Views

0

Share
Cite this

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(nm²) 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(m²) 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.

Publication: IEICE TRANSACTIONS on Information Vol.E89-D No.12 pp.2907-2918

Publication Date: 2006/12/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1093/ietisy/e89-d.12.2907

Type of Manuscript: PAPER

Category: Computation and Computational Models

Cite this

Copy

Chun-Chao YEH, "Power-Aware Allocation of Chain-Like Real-Time Tasks on DVS Processors" in IEICE TRANSACTIONS on Information, vol. E89-D, no. 12, pp. 2907-2918, December 2006, doi: 10.1093/ietisy/e89-d.12.2907.
Abstract: 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(nm²) 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(m²) 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.
URL: https://globals.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.12.2907/_p

Copy

@ARTICLE{e89-d_12_2907,
author={Chun-Chao YEH, },
journal={IEICE TRANSACTIONS on Information},
title={Power-Aware Allocation of Chain-Like Real-Time Tasks on DVS Processors},
year={2006},
volume={E89-D},
number={12},
pages={2907-2918},
abstract={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(nm²) 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(m²) 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.},
keywords={},
doi={10.1093/ietisy/e89-d.12.2907},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - Power-Aware Allocation of Chain-Like Real-Time Tasks on DVS Processors
T2 - IEICE TRANSACTIONS on Information
SP - 2907
EP - 2918
AU - Chun-Chao YEH
PY - 2006
DO - 10.1093/ietisy/e89-d.12.2907
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2006
AB - 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(nm²) 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(m²) 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.
ER -