Power-aware scheduling for makespan and flow

Details Power-aware scheduling for makespan and flow Power-aware scheduling for makespan and flow

2006-05-26

arxiv.org/abs/cs/0605126v1

Computer Science

Data Structures and Algorithms

13 pages, 3 figures. To appear in 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2006

Scientific paper

We consider offline scheduling algorithms that incorporate speed scaling to address the bicriteria problem of minimizing energy consumption and a scheduling metric. For makespan, we give linear-time algorithms to compute all non-dominated solutions for the general uniprocessor problem and for the multiprocessor problem when every job requires the same amount of work. We also show that the multiprocessor problem becomes NP-hard when jobs can require different amounts of work. For total flow, we show that the optimal flow corresponding to a particular energy budget cannot be exactly computed on a machine supporting arithmetic and the extraction of roots. This hardness result holds even when scheduling equal-work jobs on a uniprocessor. We do, however, extend previous work by Pruhs et al. to give an arbitrarily-good approximation for scheduling equal-work jobs on a multiprocessor.

Affiliated with

Also associated with

No associations

Rating

Power-aware scheduling for makespan and flow 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 Power-aware scheduling for makespan and flow, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Power-aware scheduling for makespan and flow will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-680509