Robust Online Speed Scaling With Deadline Uncertainty

Authors Goonwanth Reddy, Rahul Vaze



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.22.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Goonwanth Reddy
  • Department of Electrical Engineering, Indian Institute of Technology, Madras, Chennai, India
Rahul Vaze
  • School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai, India

Cite AsGet BibTex

Goonwanth Reddy and Rahul Vaze. Robust Online Speed Scaling With Deadline Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.22

Abstract

A speed scaling problem is considered, where time is divided into slots, and jobs with payoff v arrive at the beginning of the slot with associated deadlines d. Each job takes one slot to be processed, and multiple jobs can be processed by the server in each slot with energy cost g(k) for processing k jobs in one slot. The payoff is accrued by the algorithm only if the job is processed by its deadline. We consider a robust version of this speed scaling problem, where a job on its arrival reveals its payoff v, however, the deadline is hidden to the online algorithm, which could potentially be chosen adversarially and known to the optimal offline algorithm. The objective is to derive a robust (to deadlines) and optimal online algorithm that achieves the best competitive ratio. We propose an algorithm (called min-LCR) and show that it is an optimal online algorithm for any convex energy cost function g(.). We do so without actually evaluating the optimal competitive ratio, and give a general proof that works for any convex g, which is rather novel. For the popular choice of energy cost function g(k) = k^alpha, alpha >= 2, we give concrete bounds on the competitive ratio of the algorithm, which ranges between 2.618 and 3 depending on the value of alpha. The best known online algorithm for the same problem, but where deadlines are revealed to the online algorithm has competitive ratio of 2 and a lower bound of sqrt{2}. Thus, importantly, lack of deadline knowledge does not make the problem degenerate, and the effect of deadline information on the optimal competitive ratio is limited.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Online Algorithms
  • Speed Scaling
  • Greedy Algorithms
  • Scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Susanne Albers, Fabian Müller, and Swen Schmelzer. Speed scaling on parallel processors. Algorithmica, 68(2):404-425, 2014. Google Scholar
  2. Yossi Azar, Nikhil R Devanur, Zhiyi Huang, and Debmalya Panigrahi. Speed scaling in the non-clairvoyant model. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 133-142. ACM, 2015. Google Scholar
  3. Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R Pruhs, and Orli Waarts. Online load balancing of temporary tasks. In Workshop on algorithms and data structures, pages 119-130. Springer, 1993. Google Scholar
  4. Nikhil Bansal, Ho-Leung Chan, Tak-Wah Lam, and Lap-Kei Lee. Scheduling for speed bounded processors. In International Colloquium on Automata, Languages, and Programming, pages 409-420. Springer, 2008. Google Scholar
  5. Nikhil Bansal, Ho-Leung Chan, Kirk Pruhs, and Dmitriy Katz. Improved bounds for speed scaling in devices obeying the cube-root rule. Automata, languages and programming, pages 144-155, 2009. Google Scholar
  6. Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Speed scaling to manage energy and temperature. Journal of the ACM (JACM), 54(1):3, 2007. Google Scholar
  7. Nikhil Bansal, Kirk Pruhs, and Cliff Stein. Speed scaling for weighted flow time. SIAM Journal on Computing, 39(4):1294-1308, 2009. Google Scholar
  8. Neal Barcelo, Peter Kling, Michael Nugent, and Kirk Pruhs. Optimal Speed Scaling with a Solar Cell, pages 521-535. Springer International Publishing, Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-48749-6_38.
  9. Sanjoy Baruah, Gilad Koren, Bhubaneswar Mishra, Arvind Raghunathan, Louis Rosier, and Dennis Shasha. On-line scheduling in the presence of overload. In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 100-110. IEEE, 1991. Google Scholar
  10. Ho-Leung Chan, Joseph Wun-Tat Chan, Tak-Wah Lam, Lap-Kei Lee, Kin-Sum Mak, and Prudence WH Wong. Optimizing throughput and energy in online deadline scheduling. ACM Transactions on Algorithms (TALG), 6(1):10, 2009. Google Scholar
  11. Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, and Kirk Pruhs. Nonclairvoyant speed scaling for flow and energy. Algorithmica, 61(3):507-517, 2011. Google Scholar
  12. Aaron Coté, Adam Meyerson, Alan Roytman, Michael Shindler, and Brian Tagiku. Energy-efficient online scheduling with deadlines. unpublished manuscript, 2010. Google Scholar
  13. Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs. Nonclairvoyantly scheduling power-heterogeneous processors. Sustainable Computing: Informatics and Systems, 1(3):248-255, 2011. Google Scholar
  14. Xin Han, Tak-Wah Lam, Lap-Kei Lee, Isaac KK To, and Prudence WH Wong. Deadline scheduling and power management for speed bounded processors. Theoretical Computer Science, 411(40-42):3587-3600, 2010. Google Scholar
  15. Sandy Irani, Sandeep Shukla, and Rajesh Gupta. Algorithms for power savings. ACM Transactions on Algorithms (TALG), 3(4):41, 2007. Google Scholar
  16. Tak-Wah Lam, Lap-Kei Lee, Isaac KK To, and Prudence WH Wong. Speed scaling functions for flow time scheduling based on active job count. In European Symposium on Algorithms, pages 647-659. Springer, 2008. Google Scholar
  17. Marco Riedel. Online request server matching. Theoretical computer science, 268(1):145-160, 2001. Google Scholar
  18. Adam Wierman, Lachlan LH Andrew, and Ao Tang. Power-aware speed scaling in processor sharing systems. In INFOCOM 2009, IEEE, pages 2007-2015. IEEE, 2009. Google Scholar
  19. Frances Yao, Alan Demers, and Scott Shenker. A scheduling model for reduced cpu energy. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 374-382. IEEE, 1995. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail