1. Speed Scaling of Tasks with Precedence Constraints.
- Author
-
Pruhs, Kirk, Stee, Rob, and Uthaisombut, Patchrawat
- Subjects
- *
ENERGY conservation , *MULTIPROCESSORS , *PERFORMANCE standards , *ENERGY auditing , *PRECEDENCE , *MANAGEMENT controls , *INDUSTRIAL management , *ELECTRONIC data processing , *ALGORITHMS - Abstract
We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm | prec | C max . We extend the standard 3-field notation and denote this problem as Sm | prec, energy | C max . We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm | prec | C max to obtain a poly-log( m)-approximation algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF