Dynamic voltage scaling under EDF revisited |
| |
Authors: | Bruno Gaujal Nicolas Navet |
| |
Affiliation: | (1) INRIA and ID-IMAG Laboratory, 51 avenue Jean Kuntzmann, 38330 Montbonnot, France;(2) INRIA-LORIA, Campus Scientifique, BP-139, 54506 Vandoeuvre-lès-Nancy, France |
| |
Abstract: | Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of
computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically
variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case
complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity
of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks
are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where
the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a
geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal
slope of each path.
|
| |
Keywords: | Real-time systems Low-power design Scheduling Complexity Dynamic voltage scaling |
本文献已被 SpringerLink 等数据库收录! |
|