Susanne Albers
ABSTRACT
In this paper we investigate algorithmic instruments leading to low powerconsumption in computing devices. While previous work on energy-efficient algorithms has mostly focused on single processor environments, in this paper we investigate multi-processor settings. We study the basic problem of scheduling a set of jobs, each specified by a release time, a deadline and a processing volume, on variable speed processors so as to minimize the total energy consumption. We first settle the complexity of speed scaling with unit size jobs. More specifically, we devise a polynomial time algorithm for agreeable deadlines and prove NP-hardness results for arbitrary release dates and deadlines. For the latter setting we also develop a polynomial time algorithm achieving a constant factor approximation guarantee that is independent of the number of processors. Additionally, we study speed scaling of jobs with arbitrary processing requirements and, again, develop constant factor approximation algorithms. We finally transform our offline algorithms into constant competitive online strategies.
- S. Albers and H. Fujiwara. Energy-efficient algorithms for flow time minimization. Proc. 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 3884, 621--633, 2006. Google Scholar
Digital Library
- J. Augustine, S. Irani and C. Swamy. Optimal power-down strategies. Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, 530--539, 2004. Google ScholarDigital Library
- N. Bansal, T. Kimbrel and K. Pruhs. Dynamic speed scaling to manage energy and temperature. Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, 520--529, 2004. Google ScholarDigital Library
- P. Baptiste. Scheduling unit tasks to minimize the number of idle periods: A polynomial time algorithm for offline dynamic power management. Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 364--367, 2006. Google ScholarDigital Library
- L.A. Barroso. The price of performance. ACM Queue, 3(7), September 2005. Google ScholarDigital Library
- N. Bansal and K. Pruhs. Speed scaling to manage temperature. Proc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 3404, 460--471, 2005. Google ScholarDigital Library
- J.-J. Chen, H.-R. Hsu, K.-H. Chuang, C.-L. Yang, A.-C. Pang and T.-W. Kuo. Multiprocessor energy efficient scheduling with task migration considerations. Proc. 16th Euromicro Conference of Real-Time Systems, 101--108, 2004. Google ScholarDigital Library
- J.-J. Chen, T.-W. Kuo, H.-I. Lu. Power-saving scheduling for weakly dynamic voltage scaling devices. Proc. 9th International Workshop on Algorithms and Data Structures, Springer LNCS 3608, 338--349, 2005. Google ScholarDigital Library
- D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM, 34:144--162, 1987. Google ScholarDigital Library
- Intel pressroom. http://www.intel.com/pressroom/kits/teraflops/ or http://download.intel.com/pressroom/kits/Teraflops/Teraflops Research Chip Overview.pdfGoogle Scholar
- S. Irani, S. Shukla and R. Gupta. Algorithms for power savings. Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 37--46, 2003. Google ScholarDigital Library
- K. Pruhs, R. van Stee, P. Uthaisombut. Speed scaling of tasks with precedence constraints. Proc. 3rd International Workshop on Approximation and Online Algorithms (WAOA), Springer LNCS 3879, 307--319, 2005. Google ScholarDigital Library
- K. Pruhs, P. Uthaisombut and G. Woeginger. Getting the best response for your erg. Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT), Springer LNCS 3111, 15--25, 2004.Google Scholar
- D.D. Sleator und R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202--208, 1985. Google ScholarDigital Library
- F. Yao, A. Demers and S. Shenker. A scheduling model for reduced CPU energy. Proc. 36th Annual Symposium on Foundations of Computer Science, 374--382, 1995. Google ScholarDigital Library
Index Terms
- Speed scaling on parallel processors
Recommendations
Scheduling parallel jobs to minimize the makespan
We consider the NP-hard problem of scheduling parallel jobs with release dates on identical parallel machines to minimize the makespan. A parallel job requires simultaneously a prespecified, job-dependent number of machines when being processed. We ...
Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate of $$s^\alpha $$ s when running at speed $$s$$ s , where $$\alpha \ge 2$$ 2 . The problem is to dispatch jobs to processors and determine the speed and jobs to run for ...
From preemptive to non-preemptive speed-scaling scheduling
We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed ...
Comments