Reclaiming the energy of a schedule: models and algorithms

Details Reclaiming the energy of a schedule: models and algorithms Reclaiming the energy of a schedule: models and algorithms

2012-04-04

arxiv.org/abs/1204.0939v1

Computer Science

Distributed, Parallel, and Cluster Computing

A two-page extended abstract of this work appeared as a short presentation in SPAA'2011, while the long version has been accep

Scientific paper

We consider a task graph to be executed on a set of processors. We assume that the mapping is given, say by an ordered list of tasks to execute on each processor, and we aim at optimizing the energy consumption while enforcing a prescribed bound on the execution time. While it is not possible to change the allocation of a task, it is possible to change its speed. Rather than using a local approach such as backfilling, we consider the problem as a whole and study the impact of several speed variation models on its complexity. For continuous speeds, we give a closed-form formula for trees and series-parallel graphs, and we cast the problem into a geometric programming problem for general directed acyclic graphs. We show that the classical dynamic voltage and frequency scaling (DVFS) model with discrete modes leads to a NP-complete problem, even if the modes are regularly distributed (an important particular case in practice, which we analyze as the incremental model). On the contrary, the VDD-hopping model leads to a polynomial solution. Finally, we provide an approximation algorithm for the incremental model, which we extend for the general DVFS model.

Affiliated with

Also associated with

No associations

Rating

Reclaiming the energy of a schedule: models and algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reclaiming the energy of a schedule: models and algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reclaiming the energy of a schedule: models and algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-32165