Document Open Access Logo

Precise Scheduling of DAG Tasks with Dynamic Power Management

Authors Ashikahmed Bhuiyan , Mohammad Pivezhandi, Zhishan Guo , Jing Li , Venkata Prashant Modekurthy, Abusayeed Saifullah

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2023.8.pdf
  • Filesize: 1.01 MB
  • 24 pages

Document Identifiers

Author Details

Ashikahmed Bhuiyan
  • Department of Computer Science, West Chester University, PA, USA
Mohammad Pivezhandi
  • Department of Computer Science, Wayne State University, Detroit, MI, USA
Zhishan Guo
  • Department of Computer Science, North Carolina State University, Raleigh, NC, USA
Jing Li
  • Department of Computer Science, New Jersey Institute of Technology, Newark, NJ, USA
Venkata Prashant Modekurthy
  • Department of Computer Science, University of Nevada, Las Vegas, NV, USA
Abusayeed Saifullah
  • Department of Computer Science, Wayne State University, Detroit, MI,USA

Funding

  • Bhuiyan, Ashikahmed: Provost’s Research Grant, West Cheser University
  • Guo, Zhishan: NSF CCF-2028481, Startup Grant at NC State University
  • Li, Jing: NSF CNS-1948457
  • Modekurthy, Venkata Prashant: UNLV Troesh Center, CNS-2211640
  • Saifullah, Abusayeed: CNS-2301757, CAREER-2306486, CNS-2306745

Cite AsGet BibTex

Ashikahmed Bhuiyan, Mohammad Pivezhandi, Zhishan Guo, Jing Li, Venkata Prashant Modekurthy, and Abusayeed Saifullah. Precise Scheduling of DAG Tasks with Dynamic Power Management. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ECRTS.2023.8

Abstract

The rigid timing requirement of real-time applications biases the analysis to focus on the worst-case performances. Such a focus cannot provide enough information to optimize the system’s typical resource and energy consumption. In this work, we study the real-time scheduling of parallel tasks on a multi-speed heterogeneous platform while minimizing their typical-case CPU energy consumption. Dynamic power management (DPM) policy is integrated to determine the minimum number of cores required for each task while guaranteeing worst-case execution requirements (under all circumstances). A Hungarian Algorithm-based task partitioning technique is proposed for clustered multi-core platforms, where all cores within the same cluster run at the same speed at any time, while different clusters may run at different speeds. To our knowledge, this is the first work aiming to minimize typical-case CPU energy consumption (while ensuring the worst-case timing correctness for all tasks under any execution condition) through DPM for parallel tasks in a clustered platform. We demonstrate the effectiveness of the proposed approach with existing power management techniques using experimental results and simulations. The experimental results conducted on the Intel Xeon 2680 v3 12-core platform show around 7%-30% additional energy savings.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time system architecture
Keywords
  • Parallel task
  • mixed-criticality scheduling
  • energy minimization
  • dynamic power management
  • cluster-based platform

Metrics

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

References

  1. Kunal Agrawal, Sanjoy Baruah, Pontus Ekberg, and Jing Li. Optimal scheduling of measurement-based parallel real-time tasks. Real-Time Systems, pages 1-7, 2020. Google Scholar
  2. 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. IEEE, 2003. Google Scholar
  3. Arm a15 technical reference manual, 2013. URL: https://developer.arm.com/documentation/ddi0438/i/functional-description/power-management/dynamic-power-management?lang=en.
  4. Mario Bambagini, Mauro Marinoni, Hakan Aydin, and Giorgio Buttazzo. Energy-aware scheduling for real-time systems: A survey. ACM Transactions on Embedded Computing Systems (TECS), 15(1):7, 2016. Google Scholar
  5. Sanjoy Baruah. The federated scheduling of systems of mixed-criticality sporadic DAG tasks. In 2016 IEEE Real-Time Systems Symposium (RTSS), pages 227-236. IEEE, 2016. Google Scholar
  6. Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo DAngelo, Haohan Li, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster, and Leen Stougie. The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In 2012 24th Euromicro Conference on Real-Time Systems, pages 145-154. IEEE, 2012. Google Scholar
  7. Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'angelo, Haohan Li, Alberto Marchetti-Spaccamela, Suzanne Van Der Ster, and Leen Stougie. Preemptive uniprocessor scheduling of mixed-criticality sporadic task systems. Journal of the ACM (JACM), 62(2):1-33, 2015. Google Scholar
  8. Sanjoy Baruah, Vincenzo Bonifaci, and Alberto Marchetti-Spaccamela. The global EDF scheduling of systems of conditional sporadic DAG tasks. In ECRTS, 2015. Google Scholar
  9. Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. A generalized parallel task model for recurrent real-time processes. In RTSS. IEEE, 2012. Google Scholar
  10. 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
  11. Ashikahmed Bhuiyan, Di Liu, Aamir Khan, Abusayeed Saifullah, Nan Guan, and Zhishan 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
  12. Ashikahmed Bhuiyan, Federico Reghenzani, William Fornaciari, and Zhishan Guo. Optimizing energy in non-preemptive mixed-criticality scheduling by exploiting probabilistic information. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39(11):3906-3917, 2020. Google Scholar
  13. Ashikahmed Bhuiyan, Sai Sruti, Zhishan Guo, and Kecheng Yang. Precise scheduling of mixed-criticality tasks by varying processor speed. In Proceedings of the 27th International Conference on Real-Time Networks and Systems, pages 123-132, 2019. Google Scholar
  14. Ashikahmed Bhuiyan, Kecheng Yang, Samsil Arefin, Abusayeed Saifullah, Nan Guan, and Zhishan Guo. Mixed-criticality multicore scheduling of real-time gang task systems. In RTSS. IEEE, 2019. Google Scholar
  15. 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
  16. Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller, and Andreas Wiese. Feasibility analysis in the sporadic DAG task model. In ECRTS, 2013. Google Scholar
  17. 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
  18. Hui Cheng and Steve Goddard. Online energy-aware I/O device scheduling for hard real-time systems. In Proceedings of the conference on Design, automation and test in Europe:. European Design and Automation Association, 2006. Google Scholar
  19. Alexei Colin, Arvind Kandhalu, and Ragunathan Rajkumar. Energy-efficient allocation of real-time applications onto heterogeneous processors. In RTCSA, 2014. Google Scholar
  20. Alberto Corpas, Luis Costero, Guillermo Botella, Francisco D Igual, Carlos García, and Manuel Rodríguez. Acceleration and energy consumption optimization in cascading classifiers for face detection on low-cost arm big. little asymmetric architectures. International Journal of Circuit Theory and Applications, 46(9):1756-1776, 2018. Google Scholar
  21. Alejandro Duran, Xavier Teruel, Roger Ferrer, Xavier Martorell, and Eduard Ayguade. Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp. In 2009 international conference on parallel processing, pages 124-131. IEEE, 2009. Google Scholar
  22. Pontus Ekberg and Wang Yi. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems. Real-time systems, 50(1):48-86, 2014. Google Scholar
  23. David Ferry, Jing Li, Mahesh Mahadevan, Kunal Agrawal, Christopher Gill, and Chenyang Lu. A real-time scheduling service for parallel tasks. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 261-272. IEEE, 2013. Google Scholar
  24. Ana Guasque, Patricia Balbastre, Alfons Crespo, and Gerhard Fohler. Energy characterization of real-time partitioned systems. In 2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 118-124. IEEE, 2018. Google Scholar
  25. Zhishan Guo, Ashikahmed Bhuiyan, Di Liu, Aamir Khan, Abusayeed Saifullah, and Nan 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. IEEE, 2019. Google Scholar
  26. 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. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  27. Zhishan Guo, Luca Santinelli, and Kecheng Yang. EDF schedulability analysis on mixed-criticality systems with permitted failure probability. In RTCSA. IEEE, 2015. Google Scholar
  28. Daniel Hackenberg, Robert Schöne, Thomas Ilsche, Daniel Molka, Joseph Schuchart, and Robin Geyer. An energy efficiency feature survey of the intel haswell processor. In 2015 IEEE international parallel and distributed processing symposium workshop, pages 896-904. IEEE, 2015. Google Scholar
  29. Tarek Hagras and Jan Janecek. A high performance, low complexity algorithm for compile-time job scheduling in homogeneous computing environments. In Parallel Processing Workshops. IEEE, 2003. Google Scholar
  30. Marcus Hähnel, Björn Döbel, Marcus Völp, and Hermann Härtig. Measuring energy consumption for short code paths using rapl. ACM SIGMETRICS Performance Evaluation Review, 40(3):13-17, 2012. Google Scholar
  31. Sebastian Herbert and Diana Marculescu. Analysis of dynamic voltage/frequency scaling in chip-multiprocessors. In ISLPED. IEEE, 2007. Google Scholar
  32. 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
  33. Kai Huang, Luca Santinelli, Jian-Jia Chen, Lothar Thiele, and Giorgio C Buttazzo. Applying real-time interface and calculus for dynamic power management in hard real-time systems. Real-Time Systems, 47(2):163-193, 2011. Google Scholar
  34. Pengcheng Huang, Pratyush Kumar, Georgia Giannopoulou, and Lothar Thiele. Energy efficient DVFS scheduling for mixed-criticality systems. In EMSOFT. IEEE, 2014. Google Scholar
  35. Connor Imes, David HK Kim, Martina Maggio, and Henry Hoffmann. Poet: a portable approach to minimizing energy under soft real-time constraints. In 21st IEEE Real-Time and Embedded Technology and Applications Symposium, pages 75-86. IEEE, 2015. Google Scholar
  36. Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955. Google Scholar
  37. Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. Analysis of global EDF for parallel tasks. In ECRTS. IEEE, 2013. Google Scholar
  38. 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 ECRTS. IEEE, 2014. Google Scholar
  39. Jing Li, David Ferry, Shaurya Ahuja, Kunal Agrawal, Christopher Gill, and Chenyang Lu. Mixed-criticality federated scheduling for parallel real-time tasks. Real-time systems, 53(5):760-811, 2017. Google Scholar
  40. Keqin Li. Energy efficient scheduling of parallel tasks on multiprocessor computers. The Journal of Supercomputing, 2012. Google Scholar
  41. Xinmei Li, Lei Mo, Angeliki Kritikakou, and Olivier Sentieys. Approximation-aware task deployment on heterogeneous multi-core platforms with dvfs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022. Google Scholar
  42. Yau-Tsun Steven Li and Sharad Malik. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the ACM SIGPLAN 1995 workshop on Languages, compilers, & tools for real-time systems, pages 88-98, 1995. Google Scholar
  43. Di Liu, Jelena Spasic, Gang Chen, and Todor Stefanov. Energy-efficient mapping of real-time streaming applications on cluster heterogeneous mpsocs. In ESTIMedia. IEEE, 2015. Google Scholar
  44. 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 Systems, 28(1):39-68, 2004. Google Scholar
  45. Agostino Mascitti and Tommaso Cucinotta. Dynamic partitioned scheduling of real-time dag tasks on arm big. little architectures. In 29th International Conference on Real-Time Networks and Systems, pages 1-11, 2021. Google Scholar
  46. Alexander Maxiaguine, Simon Kunzli, and Lothar Thiele. Workload characterization model for tasks with variable execution demand. In Proceedings Design, Automation and Test in Europe Conference and Exhibition, volume 2, pages 1040-1045. IEEE, 2004. Google Scholar
  47. Sujay Narayana, Pengcheng Huang, Georgia Giannopoulou, Lothar Thiele, and R Venkatesha Prasad. Exploring energy saving for mixed-criticality systems on multi-cores. In RTAS. IEEE, 2016. Google Scholar
  48. Odroid xu-3, 2017. URL: http://www.hardkernel.com/.
  49. Chandandeep Singh Pabla. Completely fair scheduler. Linux Journal, 2009(184):4, 2009. Google Scholar
  50. Santiago Pagani and Jian-Jia Chen. Energy efficient task partitioning based on the single frequency approximation scheme. In RTSS. IEEE, 2013. Google Scholar
  51. 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
  52. 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 RTCSA. IEEE, 2014. Google Scholar
  53. Manar Qamhieh, Frédéric Fauberteau, Laurent George, and Serge Midonnet. Global EDF scheduling of directed acyclic graphs on multiprocessor systems. In RTNS. ACM, 2013. Google Scholar
  54. 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). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  55. 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
  56. Abusayeed Saifullah, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. Multi-core real-time scheduling for generalized parallel task models. Real-Time Systems, 2013. Google Scholar
  57. Robert Schöne, Thomas Ilsche, Mario Bielert, Andreas Gocht, and Daniel Hackenberg. Energy efficiency features of the intel skylake-sp processor and their impact on performance. In 2019 International Conference on High Performance Computing & Simulation (HPCS), pages 399-406. IEEE, 2019. Google Scholar
  58. Youngsoo Shin and Kiyoung Choi. Power conscious fixed priority scheduling for hard real-time systems. In Proceedings 1999 Design Automation Conference, pages 134-139. IEEE, 1999. Google Scholar
  59. Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In RTSS. IEEE, 2007. Google Scholar
  60. Kecheng Yang, Ashikahmed Bhuiyan, and Zhishan Guo. F2vd: Fluid rates to virtual deadlines for precise mixed-criticality scheduling on a varying-speed processor. In Proceedings of the 39th International Conference on Computer-Aided Design, pages 1-9, 2020. Google Scholar
  61. Dakai Zhu, Nevine AbouGhazaleh, Daniel Mossé, and Rami Melhem. Power aware scheduling for and/or graphs in multiprocessor real-time systems. In ICPP. IEEE, 2002. Google Scholar
  62. 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 Imprint Privacy Contact