Susanne Albers
ABSTRACT
We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. Previous work has focused mostly on the setting where a single variable-speed processor is available. In this paper we study multi-processor environments with m parallel variable-speed processors assuming that job migration is allowed, i.e. whenever a job is preempted it may be moved to a different processor.
We first study the offline problem and show that optimal schedules can be computed efficiently in polynomial time. In contrast to a previously known strategy, our algorithm does not resort to linear programming. We develop a fully combinatorial algorithm that relies on repeated maximum flow computations. The approach might be useful to solve other problems in dynamic speed scaling. For the online problem, we extend two algorithms Optimal Available and Average Rate proposed by Yao et al. [16] for the single processor setting. We prove that Optimal Available is αα-competitive, as in the single processor case. Here α>1 is the exponent of the power consumption function. While it is straightforward to extend Optimal Available to parallel processing environments, the competitive analysis becomes considerably more involved. For Average Rate we show a competitiveness of (3\α)α/2 + 2α.
- S. Albers, F. Müller and S. Schmelzer. Speed scaling on parallel processors. Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures, 289--298, 2007. Google Scholar
Digital Library
- N. Bansal, D.P. Bunde, H.-L. Chan and K. Pruhs. Average rate speed scaling. Proc. 8th Latin American Symposium on Theoretical Informatics, Springer LNCS 4957, 240--251, 2008. Google ScholarDigital Library
- N. Bansal, H.-L. Chan, T.-W. Lam and L.-K. Lee. Scheduling for speed bounded processors. Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP), Springer LNCS 5125, 409--420, 2008. Google ScholarDigital Library
- N. Bansal, H.-L. Chan, K. Pruhs and D. Katz. Improved bounds for speed scaling in devices obeying the cube-root rule. Proc. 36th International Colloqium on Automata, Languages and Programming, Springer LNCS 5555, 144--155, 2009. Google ScholarDigital Library
- N. Bansal, T. Kimbrel and K. Pruhs. Speed scaling to manage energy and temperature. Journal of the ACM, 54, 2007. Google ScholarDigital Library
- B.D. Bingham and M.R. Greenstreet. Energy optimal scheduling on multiprocessors with migration. Proc. IEEE International Symposium on Parallel and Distributed Processing with Applications, 143--152, 2008. Google ScholarDigital Library
- H.-L. Chan, W.-T. Chan, T.-W. Lam, L.-K. Lee, K.-S. Mak and P.W.H. Wong. Energy efficient online deadline scheduling. Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 795--804, 2007. Google ScholarDigital Library
- R.L. Graham. Bounds on multi-processing timing anomalies. SIAM Journal on Applied Mathematics, 17:416--429, 1969.Google ScholarCross Ref
- G. Greiner, T. Nonner and A. Souza. The bell is ringing in speed-scaled multiprocessor scheduling. Proc. 21st Annual ACM Symposium on Parallel Algorithms and Architectures, 11--18, 2009. Google ScholarDigital Library
- S. Irani, S.K. Shukla and R. Gupta. Algorithms for power savings. ACM Transactions on Algorithms, 3, 2007. Google ScholarDigital Library
- T.-W. Lam, L.-K. Lee, I.K.-K. To and P.W.H. Wong. Energy efficient deadline scheduling in two processor systems. Proc. 18th International Symposium on Algorithms and Computation, Springer LNCS 4835, 476--487, 2007. Google ScholarDigital Library
- M. Li, B.J. Liu and F.F. Yao. Min-energy voltage allocation for tree-structured tasks. J. Comb. Optim., 11:305--319, 2006.Google ScholarCross Ref
- M. Li, A.C. Yao and F.F. Yao. Discrete and continuous min-energy schedules for variable voltage processors. Proc. National Academy of Sciences USA, 103:3983--3987, 2006.Google ScholarCross Ref
- M. Li and F.F. Yao. An efficient algorithm for computing optimal discrete voltage schedules. SIAM Journalon Computing, 35:658--671, 2005. Google ScholarDigital Library
- D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202--208, 1985. Google ScholarDigital Library
- F.F. Yao, A.J. Demers and S. Shenker. A scheduling model for reduced CPU energy. Proc. 36th IEEE Symposium on Foundations of Computer Science, 374--382, 1995. Google ScholarDigital Library
Index Terms
- On multi-processor speed scaling with migration: extended abstract
Recommendations
On multi-processor speed scaling with migration
We investigate a very basic problem in dynamic speed scaling where a sequence of jobs, each specified by an arrival time, a deadline and a processing volume, has to be processed so as to minimize energy consumption. We study multi-processor environments ...
Optimal algorithms for online single machine scheduling with deteriorating jobs
In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job's deterioration effect. Such effect is unexplored in the context of online environment. ...
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 ...
Comments