[ACM Press the eighteenth annual ACM symposium - Cambridge, Massachusetts, USA (2006.07.30-2006.08.02)] Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures - SPAA '06 - Power-aware scheduling for makespan and flow

✍ Scribed by Bunde, David P.

• Book ID: 120817195
• Publisher: ACM Press
• Year: 2006
• Tongue: English
• Weight: 166 KB
• Edition: 2006
• Category: Article
• ISBN-13: 9781595934529
• DOI: 10.1145/1148109.1148140

✦ Synopsis

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 arbitrarilygood approximation for scheduling equal-work jobs on a multiprocessor.