Profitable scheduling on multiple speed-scalable processors

ABSTRACT

We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors. Moreover, we provide a tight analysis of the algorithm's competitiveness. Our results generalize and improve upon work by Chan et al. [10], which considers a single speed-scalable processor. Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm.

In our scheduling problem, jobs arrive over time and are preemptable. They have different workloads, values, and deadlines. The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value. However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy. The cost of a schedule is the sum of lost values and invested energy. In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly. A processor's energy consumption is power P_α(s) integrated over time, where P_α(s) = s^α is the power consumption when running at speed s. Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs. This problem was introduced by Chan et al. [10] for the case of a single processor. They presented an online algorithm which is α^α +2eα-competitive. We provide an online algorithm for the case of multiple processors with an improved competitive ratio of α^α.

References

1. S. Albers. Algorithms for dynamic speed scaling. In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science, pages 1--11. Schloss Dagstuhl, 2011.
2. S. Albers, A. Antoniadis, and G. Greiner. On multi-processor speed scaling with migration. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 279--288, 2011.
3. N. Bansal, T. Kimbrel, and K. Pruhs. Dynamic speed scaling to manage energy and temperature. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS), pages 520--529, 2004.
4. N. Bansal, T. Kimbrel, and K. Pruhs. Speed scaling to manage energy and temperature. Journal of the ACM, 54 (1): 1--39, 2007.
5. N. Bansal, H.-L. Chan, K. Pruhs, and D. Katz. Improved bounds for speed scaling in devices obeying the cube-root rule. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), pages 144--155. Springer, 2009.
6. A. Barroso and U. Hölzle. The case for energy-proportional computing. Computer, 40 (12): 33--37, 2007.
7. B. D. Bingham and M. R. Greenstreet. Energy optimal scheduling on multiprocessors with migration. In Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA), pages 153--161. IEEE Computer Society, 2008.
8. S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 7 edition, 2004.
9. N. Buchbinder and J. Naor. The Design of Competitive Online Algorithms via a Primal-Dual Approach. Now Publishers Inc., 2009.
10. H.-L. Chan, T.-W. Lam, and R. Li. Tradeoff between energy and throughput for online deadline scheduling. In WAOA, pages 59--70. Springer, 2010.
11. 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. In Proc. of the 16th Euromicro Conference on Real-Time Systems, pages 101--108, 2004.
12. A. Gupta, R. Krishnaswamy, and K. Pruhs. Online primal-dual for non-linear optimization with applications to speed scaling. In WAOA, 2012.
13. P. Kling and P. Pietrzyk. Profitable scheduling on multiple speed-scalable processors, 2012. arXiv:1209.3868.
14. K. Pruhs and C. Stein. How to schedule when you have to buy your energy. In APPROX/RANDOM, pages 352--365. Springer, 2010.
15. F. F. Yao, A. J. Demers, and S. Shenker. A scheduling model for reduced cpu energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pages 374--382, 1995.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

      • Continuous optimization

        • Convex optimization

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Mathematical optimization

      • Continuous optimization

        • Convex optimization

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Models of computation

    • Concurrency

      • Parallel computing models

    • Interactive computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Online learning theory

      • Reinforcement learning

        • Sequential decision making