Document Open Access Logo

CPU Energy-Aware Parallel Real-Time Scheduling

Authors Abusayeed Saifullah , Sezana Fahmida, Venkata P. Modekurthy, Nathan Fisher, Zhishan Guo

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2020.2.pdf
  • Filesize: 2.94 MB
  • 26 pages

Document Identifiers

Author Details

Abusayeed Saifullah
  • Wayne State University, Detroit, MI, USA
Sezana Fahmida
  • Wayne State University, Detroit, MI, USA
Venkata P. Modekurthy
  • Wayne State University, Detroit, MI, USA
Nathan Fisher
  • Wayne State University, Detroit, MI, USA
Zhishan Guo
  • University of Central Florida, Orlando, FL, USA

Funding

This work was supported by National Science Foundation through grants CAREER-1846126, CNS-1618185, IIS-1724227, and CNS-1850851, by Wayne State University through Rumble Fellowship, and by University of Central Florida through a startup grant.

Cite As Get BibTex

Abusayeed Saifullah, Sezana Fahmida, Venkata P. Modekurthy, Nathan Fisher, and Zhishan Guo. CPU Energy-Aware Parallel Real-Time Scheduling. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 2:1-2:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ECRTS.2020.2

Abstract

Both energy-efficiency and real-time performance are critical requirements in many embedded systems applications such as self-driving car, robotic system, disaster response, and security/safety control. These systems entail a myriad of real-time tasks, where each task itself is a parallel task that can utilize multiple computing units at the same time. Driven by the increasing demand for parallel tasks, multi-core embedded processors are inevitably evolving to many-core. Existing work on real-time parallel tasks mostly focused on real-time scheduling without addressing energy consumption. In this paper, we address hard real-time scheduling of parallel tasks while minimizing their CPU energy consumption on multicore embedded systems. Each task is represented as a directed acyclic graph (DAG) with nodes indicating different threads of execution and edges indicating their dependencies. Our technique is to determine the execution speeds of the nodes of the DAGs to minimize the overall energy consumption while meeting all task deadlines. It incorporates a frequency optimization engine and the dynamic voltage and frequency scaling (DVFS) scheme into the classical real-time scheduling policies (both federated and global) and makes them energy-aware. The contributions of this paper thus include the first energy-aware online federated scheduling and also the first energy-aware global scheduling of DAGs. Evaluation using synthetic workload through simulation shows that our energy-aware real-time scheduling policies can achieve up to 68% energy-saving compared to classical (energy-unaware) policies. We have also performed a proof of concept system evaluation using physical hardware demonstrating the energy efficiency through our proposed approach.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time system specification
Keywords
  • Real-time scheduling
  • multicore
  • energy-efficiency
  • embedded systems

Metrics

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

References

  1. URL: https://www.greentechmedia.com.
  2. URL: https://web.archive.org/web/20090326020946/http://www.aero.org/conferences/mrqw/2002-papers/A_Burcin.pdf.
  3. Intel SCC. URL: https://www.intel.cn/content/dam/www/public/us/en/documents/technology-briefs/intel-labs-single-chip-cloud-overview-paper.pdf.
  4. Matlab fmincon. URL: https://www.mathworks.com/help/optim/ug/fmincon.html.
  5. Pc 205. URL: https://en.wikipedia.org/wiki/PicoChip.
  6. Smartpower. URL: https://hardkernel.com/shop/smartpower2-with-15v-4a/.
  7. TILE-Gxtrademark. URL: http://www.tilera.com/products/processors/TILE-Gx_Family.
  8. Björn Andersson and Dionisio de Niz. Analyzing global-edf for multiprocessor scheduling of parallel tasks. In OPODIS, pages 16-30. Springer, 2012. Google Scholar
  9. Björn Andersson and Jan Jonsson. The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%. In 15th Euromicro Conference on Real-Time Systems, 2003. Proceedings., pages 33-40, 2003. Google Scholar
  10. Hakan Aydin and Qi Yang. Energy-aware partitioning for multiprocessor real-time systems. In Parallel and Distributed Processing Symposium. Proceedings. International, pages 9-pp. IEEE, 2003. Google Scholar
  11. Mario Bambagini, Mauro Marinoni, Hakan Aydin, and Giorgio Buttazzo. Energy-aware scheduling for real-time systems: A survey. ACM Trans. Embed. Comput. Syst., 15(1):7:1-7:34, January 2016. Google Scholar
  12. Sanjoy Baruah. Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In 26th Euromicro Conference on Real-Time Systems, pages 97-105, 2014. Google Scholar
  13. Sanjoy Baruah, Vincenzo Bonifaci, and Alberto Marchetti-Spaccamela. The global EDF scheduling of systems of conditional sporadic DAG tasks. In 27th Euromicro Conference on Real-Time Systems, pages 222-231. IEEE, 2015. Google Scholar
  14. Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. A generalized parallel task model for recurrent real-time processes. In Real-Time Systems Symposium (RTSS), IEEE 33rd, pages 63-72. IEEE, 2012. Google Scholar
  15. A. Bhuiyan, D. Liu, A. Khan, A. Saifullah, N. Guan, and Z. Guo. Energy-efficient parallel real-time scheduling on clustered multi-core. IEEE Transactions on Parallel and Distributed Systems, 31(9):2097-2111, 2020. Google Scholar
  16. A. A. Bhuiyan, K. Yang, S. Arefin, A. Saifullah, N. Guan, and Z. Guo. Mixed-criticality multicore scheduling of real-time gang task systems. In 2019 IEEE Real-Time Systems Symposium (RTSS), pages 469-480, 2019. Google Scholar
  17. Ashikahmed Bhuiyan, Zhishan Guo, Abusayeed Saifullah, Nan Guan, and Haoyi Xiong. Energy-efficient real-time scheduling of dag tasks. ACM Transactions on Embedded Computing Systems (TECS), 17(5):84, 2018. Google Scholar
  18. Enrico Bini, Giorgio Buttazzo, and Giuseppe Lipari. Minimizing CPU energy in real-time systems with discrete speed management. ACM Transactions on Embedded Computing Systems (TECS), 8(4):31, 2009. Google Scholar
  19. Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller, and Andreas Wiese. Feasibility analysis in the sporadic DAG task model. In 25th Euromicro Conference on Real-Time Systems, pages 225-233. IEEE, 2013. Google Scholar
  20. Gang Chen, Kai Huang, and Alois Knoll. Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination. ACM Transactions on Embedded Computing Systems (TECS), 13(3s):111, 2014. Google Scholar
  21. Jian-Jia Chen, Heng-Ruey Hsu, and Tei-Wei Kuo. Leakage-aware energy-efficient scheduling of real-time tasks in multiprocessor systems. In 12th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'06), pages 408-417. IEEE, 2006. Google Scholar
  22. Jian-Jia Chen, Andreas Schranzhofer, and Lothar Thiele. Energy minimization for periodic real-time tasks on heterogeneous processing units. In Parallel & Distributed Processing. IPDPS 2009. IEEE International Symposium on, pages 1-12. IEEE, 2009. Google Scholar
  23. Yixin Chen and Minmin Chen. Extended duality for nonlinear programming. Comput. Optim. Appl., 47:33-59, 2010. Google Scholar
  24. Alexei Colin, Arvind Kandhalu, and Ragunathan Rajkumar. Energy-efficient allocation of real-time applications onto heterogeneous processors. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2014 IEEE 20th International Conference on, pages 1-10. IEEE, 2014. Google Scholar
  25. Daniel Cordeiro, Gregory Mouni, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, and Frederic Wagner. Random graph generation for scheduling simulations. In Proceedings of the 3rd international ICST conference on simulation tools and techniques, page 60. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2010. Google Scholar
  26. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  27. Vinay Devadas and Hakan Aydin. Coordinated power management of periodic real-time tasks on chip multiprocessors. In Green Computing Conference, 2010 International, pages 61-72. IEEE, 2010. Google Scholar
  28. David Ferry, Jing Li, Mahesh Mahadevan, Kunal Agrawal, Christopher Gill, and Chenyang Lu. A real-time scheduling service for parallel tasks. In RTAS'13, 2013. Google Scholar
  29. James H. Gawron, Gregory A. Keoleian, Robert D. De Kleine, Timothy J. Wallington, and Hyung Chul Kim. Life cycle assessment of connected and automated vehicles: Sensing and computing subsystem and vehicle level effects. Environmental Science & Technology, 52(5):3249-3256, 2018. Google Scholar
  30. Michael Grant and Stephen Boyd. CVX: MATLAB software for disciplined convex programming, 2012. URL: http://cvxr.com/cvx/.
  31. Akhil Guliani and Michael M. Swift. Per-application power delivery. In Proceedings of the Fourteenth EuroSys Conference 2019, EuroSys '19, pages 5:1-5:16, 2019. Google Scholar
  32. Yifeng Guo, Dakai Zhu, and Hakan Aydin. Reliability-aware power management for parallel real-time applications with precedence constraints. In Green Computing Conference and Workshops (IGCC), 2011 International, pages 1-8. IEEE, 2011. Google Scholar
  33. Z. Guo, A. Bhuiyan, D. Liu, A. Khan, A. Saifullah, and N. Guan. Energy-efficient real-time scheduling of dags on clustered multi-core platforms. In 2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 156-168, 2019. Google Scholar
  34. Zhishan Guo, Ashikahmed Bhuiyan, Abusayeed Saifullah, Nan Guan, and Haoyi Xiong. Energy-efficient multi-core scheduling for real-time DAG tasks. In LIPIcs-Leibniz International Proceedings in Informatics, volume 76. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  35. Jason Howard, Saurabh Dighe, Sriram R Vangal, Gregory Ruhl, Nitin Borkar, Shailendra Jain, Vasantha Erraguntla, Michael Konow, Michael Riepen, Matthias Gries, et al. A 48-core ia-32 processor in 45 nm cmos using on-die message-passing and dvfs for performance and power scaling. IEEE Journal of Solid-State Circuits, 46(1):173-183, 2011. Google Scholar
  36. IPOPT. Interior point optimizer, 2011. URL: https://projects.coin-or.org/Ipopt.
  37. Ravindra Jejurikar. Energy aware non-preemptive scheduling for hard real-time systems. In 17th Euromicro Conference on Real-Time Systems (ECRTS'05), pages 21-30. IEEE, 2005. Google Scholar
  38. Xu Jiang, Nan Guan, Xiang Long, and Wang Yi. Semi-federated scheduling of parallel real-time tasks on multiprocessors. arXiv preprint arXiv:1705.03245, 2017. Google Scholar
  39. J. Kim, H. Kim, K. Lakshmanan, and R. Rajkumar. Parallel scheduling for cyber-physical systems: Analysis and case study on a self-driving car. In 2013 ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), pages 31-40, 2013. Google Scholar
  40. Junsung Kim, Hyoseung Kim, Karthik Lakshmanan, and Ragunathan Raj Rajkumar. Parallel scheduling for cyber-physical systems: Analysis and case study on a self-driving car. In Proceedings of the ACM/IEEE 4th International Conference on Cyber-Physical Systems, pages 31-40. ACM, 2013. Google Scholar
  41. Fanxin Kong, Nan Guan, Qingxu Deng, and Wang Yi. Energy-efficient scheduling for parallel real-time tasks based on level-packing. In Proceedings of the 2011 ACM Symposium on Applied Computing, pages 635-640. ACM, 2011. Google Scholar
  42. Wan Yeon Lee. Energy-efficient scheduling of periodic real-time tasks on lightly loaded multicore processors. IEEE Transactions on Parallel and Distributed Systems, 23(3):530-537, 2012. Google Scholar
  43. Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. Outstanding paper award: Analysis of global EDF for parallel tasks. In 25th Euromicro Conference on Real-Time Systems, pages 3-13. IEEE, 2013. Google Scholar
  44. Jing Li, Jian-Jia Chen, Kunal Agrawal, Chenyang Lu, Chris Gill, and Abusayeed Saifullah. Analysis of federated and global scheduling for parallel real-time tasks. In 26th Euromicro Conference on Real-Time Systems, pages 85-96. IEEE, 2014. Google Scholar
  45. Keqin Li. Energy efficient scheduling of parallel tasks on multiprocessor computers. J Supercomput, 60:223-247, 2012. Google Scholar
  46. Cong Liu, Jian Li, Wei Huang, Juan Rubio, Evan Speight, and Xiaozhu Lin. Power-efficient time-sensitive mapping in heterogeneous systems. In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, pages 23-32. ACM, 2012. Google Scholar
  47. Di Liu, Jelena Spasic, Gang Chen, and Todor Stefanov. Energy-efficient mapping of real-time streaming applications on cluster heterogeneous mpsocs. In Embedded Systems For Real-time Multimedia (ESTIMedia), 2015 13th IEEE Symposium on, pages 1-10. IEEE, 2015. Google Scholar
  48. José María López, José Luis Díaz, and Daniel F García. Utilization bounds for edf scheduling on real-time multiprocessor systems. Real-Time Syst., 28(1):39-68, October 2004. Google Scholar
  49. Junyang Lu and Yao Guo. Energy-aware fixed-priority multi-core scheduling for real-time systems. In 2011 IEEE 17th International Conference on Embedded and Real-Time Computing Systems and Applications, pages 277-281, 2011. Google Scholar
  50. G. Luo, B. Guo, Y. Shen, H. Liao, and L. Ren. Analysis and optimization of embedded software energy consumption on the source code and algorithm level. In 2009 Fourth International Conference on Embedded and Multimedia Computing, pages 1-5, 2009. Google Scholar
  51. Oliver Mitchell. Self-driving cars have power consumption problems, 2018. URL: https://www.therobotreport.com/self-driving-cars-power-consumption/.
  52. Sujay Narayana, Pengcheng Huang, Georgia Giannopoulou, Lothar Thiele, and R Venkatesha Prasad. Exploring energy saving for mixed-criticality systems on multi-cores. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 1-12. IEEE, 2016. Google Scholar
  53. Geoffrey Nelissen, Vandy Berten, Joël Goossens, and Dragomir Milojevic. Techniques optimizing the number of processors to schedule multi-threaded tasks. In 2012 24th Euromicro Conference on Real-Time Systems, pages 321-330. IEEE, 2012. Google Scholar
  54. ODROID XU-4. http://www.hardkernel.com/. Google Scholar
  55. Santiago Pagani and Jian-Jia Chen. Energy efficient task partitioning based on the single frequency approximation scheme. In Real-Time Systems Symposium (RTSS), IEEE 34th, pages 308-318. IEEE, 2013. Google Scholar
  56. Santiago Pagani and Jian-Jia Chen. Energy efficiency analysis for the single frequency approximation (SFA) scheme. ACM Transactions on Embedded Computing Systems (TECS), 13(5s):158, 2014. Google Scholar
  57. Antonio Paolillo, Joël Goossens, Pradeep M Hettiarachchi, and Nathan Fisher. Power minimization for parallel real-time systems with malleable jobs and homogeneous frequencies. In IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, pages 1-10. IEEE, 2014. Google Scholar
  58. Antonio Paolillo, Paul Rodriguez, Nikita Veshchikov, Joël Goossens, and Ben Rodriguez. Quantifying energy consumption for practical fork-join parallelism on an embedded real-time operating system. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, pages 329-338, 2016. Google Scholar
  59. Sangyoung Park, Jaehyun Park, Donghwa Shin, Yanzhi Wang, Qing Xie, Massoud Pedram, and Naehyuck Chang. Accurate modeling of the delay and energy overhead of dynamic voltage and frequency scaling in modern microprocessors. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(5):695-708, 2013. Google Scholar
  60. Xuan Qi and Dakai Zhu. Energy efficient block-partitioned multicore processors for parallel applications. Journal of Computer Science and Technology, 26(3):418-433, 2011. Google Scholar
  61. Abusayeed Saifullah, Kunal Agrawal, Chenyang Lu, and Christopher Gill. Multi-core real-time scheduling for generalized parallel task models. In RTSS '11, 2011. Google Scholar
  62. Abusayeed Saifullah, David Ferry, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher D Gill. Parallel real-time scheduling of DAGs. IEEE Transactions on Parallel and Distributed Systems, 25(12):3242-3252, 2014. Google Scholar
  63. Abusayeed Saifullah, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems, 49(4):404-435, 2013. Google Scholar
  64. Abusayeed Saifullah, Chengjie Wu, Paras Tiwari, You Xu, Yong Fu, Chenyang Lu, and Yixin Chen. Near optimal rate selection for wireless control systems. ACM Transactions on Embedded Computing Systems, 13(4s):128:1-128:25, 2013. Special Issue on Real-Time and Embedded Systems. Google Scholar
  65. Euiseong Seo, Jinkyu Jeong, Seonyeong Park, and Joonwon Lee. Energy efficient scheduling of real-time tasks on multicore processors. IEEE transactions on parallel and distributed systems, 19(11):1540-1552, 2008. Google Scholar
  66. Jack Stewart. Self-driving cars use crazy amounts of power, and it’s becoming a problem, 2018. URL: https://www.wired.com/story/self-driving-cars-power-consumption-nvidia-chip/.
  67. Corey Tessler, Venkata Modekurthy, Nathan Fisher, and Abusayeed Saifullah. Bringing inter-thread cache benefits to federated scheduling. In The 26th IEEE/USENIX Real-Time and Embedded Technology and Applications Symposium (RTAS), 2020. Google Scholar
  68. Leping Wang and Ying Lu. Efficient power management of heterogeneous soft real-time clusters. In Real-Time Systems Symposium, 2008, pages 323-332. IEEE, 2008. Google Scholar
  69. Lizhe Wang, Samee U. Khan, Dan Chen, Joanna KolOdziej, Rajiv Ranjan, Cheng-Zhong Xu, and Albert Zomaya. Energy-aware parallel task scheduling in a cluster. Future Gener. Comput. Syst., 29(7):1661-1670, 2013. Google Scholar
  70. Lizhe Wang, Gregor Von Laszewski, Jay Dayal, and Fugang Wang. Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with dvfs. In Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, pages 368-377. IEEE Computer Society, 2010. Google Scholar
  71. Huiting Xu, Fanxin Kong, and Qingxu Deng. Energy minimizing for parallel real-time tasks based on level-packing. In IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pages 98-103. IEEE, 2012. Google Scholar
  72. Ruibin Xu, Dakai Zhu, Cosmin Rusu, Rami Melhem, and Daniel Mossé. Energy-efficient policies for embedded clusters. In ACM SIGPLAN Notices, volume 40(7), pages 1-10. ACM, 2005. Google Scholar
  73. Chuan-Yue Yang, Jian-Jia Chen, and Tei-Wei Kuo. An approximation algorithm for energy-efficient scheduling on a chip multiprocessor. In Proceedings of the conference on Design, Automation and Test in Europe-Volume 1, pages 468-473. IEEE Computer Society, 2005. Google Scholar
  74. Dakai Zhu, Nevine AbouGhazaleh, Daniel Mossé, and Rami Melhem. Power aware scheduling for and/or graphs in multiprocessor real-time systems. In Parallel Processing, 2002. Proceedings. International Conference on, pages 593-601. IEEE, 2002. Google Scholar
  75. Dakai Zhu, Daniel Mosse, and Rami Melhem. Power-aware scheduling for and/or graphs in real-time systems. IEEE Transactions on Parallel and Distributed Systems, 15(9):849-864, 2004. 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 About DROPS Imprint Privacy Contact