Document Open Access Logo

Improving the Bounds of the Online Dynamic Power Management Problem

Authors Ya-Chun Liang, Kazuo Iwama, Chung-Shou Liao

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.28.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Ya-Chun Liang
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan
Kazuo Iwama
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan
Chung-Shou Liao
  • Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu, Taiwan

Funding

  • Iwama, Kazuo: Supported by MOST Taiwan under Grants 110-2223-E-007-001, 110-2811-E-007-507 and KAKENHI Japan under Grant 16H02782.
  • Liao, Chung-Shou: Supported by MOST Taiwan under Grants 110-2221-E-007-106-MY3 and 110-2622-8-007-017.

Cite AsGet BibTex

Ya-Chun Liang, Kazuo Iwama, and Chung-Shou Liao. Improving the Bounds of the Online Dynamic Power Management Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.28

Abstract

We investigate the power-down mechanism which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle cost and switching cost, is minimized. In contrast to most of the previous studies on the offline model, we focus on the online model in which a sequence of jobs with their release time, execution time and deadline, arrive in an online fashion. More precisely, we exploit a different switching on and off strategy and present an upper bound of 3, and further show a lower bound of 2.1, in a dual-machine model, introduced by Chen et al. in 2014 [STACS 2014: 226-238], both of which beat the currently best result.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Online algorithm
  • Energy scheduling
  • Dynamic power management

Metrics

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

References

  1. Susanne Albers and Antonios Antoniadis. Race to idle: new algorithms for speed scaling with a sleep state. ACM Transactions on Algorithms (TALG), 10(2):9, 2014. Google Scholar
  2. Susanne Albers, Antonios Antoniadis, and Gero Greiner. On multi-processor speed scaling with migration. Journal of Computer and System Sciences, 81(7):1194-1209, 2015. Google Scholar
  3. Antonios Antoniadis, Naveen Garg, Gunjan Kumar, and Nikhil Kumar. Parallel machine scheduling to minimize energy consumption. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2758-2769. SIAM, 2020. Google Scholar
  4. Antonios Antoniadis, Chien-Chung Huang, and Sebastian Ott. A fully polynomial-time approximation scheme for speed scaling with sleep state. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1102-1113. SIAM, 2015. Google Scholar
  5. 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
  6. Luca Benini, Alessandro Bogliolo, and Giovanni De Micheli. A survey of design techniques for system-level dynamic power management. IEEE transactions on very large scale integration (VLSI) systems, 8(3):299-316, 2000. Google Scholar
  7. Jian-Jia Chen, Mong-Jen Kao, DT Lee, Ignaz Rutter, and Dorothea Wagner. Online dynamic power management with hard real-time guarantees. Theoretical Computer Science, 595:46-64, 2015. Google Scholar
  8. Jian-Jia Chen and Tei-Wei Kuo. Procrastination for leakage-aware rate-monotonic scheduling on a dynamic voltage scaling processor. ACM SIGPLAN Notices, 41(7):153-162, 2006. Google Scholar
  9. Jian-Jia Chen and Tei-Wei Kuo. Procrastination determination for periodic real-time tasks in leakage-aware dynamic voltage scaling systems. In Computer-Aided Design, 2007. ICCAD 2007. IEEE/ACM International Conference on, pages 289-294. IEEE, 2007. Google Scholar
  10. Houssine Chetto and Maryline Chetto. Scheduling periodic and sporadic tasks in a real-time system. Information Processing Letters, 30(4):177-184, 1989. Google Scholar
  11. Erik D Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S Sayedi-Roshkhar, and Morteza Zadimoghaddam. Scheduling to minimize gaps and power consumption. Journal of Scheduling, 16(2):151-160, 2013. Google Scholar
  12. Sandy Irani and Anna R. Karlin. Online Computation, pages 521-564. PWS Publishing Co., USA, 1996. Google Scholar
  13. Sandy Irani and Kirk R Pruhs. Algorithmic problems in power management. ACM Sigact News, 36(2):63-76, 2005. Google Scholar
  14. Sandy Irani, Sandeep Shukla, and Rajesh Gupta. Online strategies for dynamic power management in systems with multiple power-saving states. ACM Transactions on Embedded Computing Systems (TECS), 2(3):325-346, 2003. 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. Anna R Karlin, Mark S Manasse, Larry Rudolph, and Daniel D Sleator. Competitive snoopy caching. Algorithmica, 3(1):79-119, 1988. Google Scholar
  17. Ya-Chun Liang, Kazuo Iwama, and Chung-Shou Liao. Improving the bounds of the online dynamic power management problem, 2022. URL: http://arxiv.org/abs/2209.12021.
  18. Adam Wierman, Lachlan Leicester Henry Andrew, and Minghong Lin. Speed scaling: An algorithmic perspective, pages 385-406. CRC Press, 2012. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact