Document Open Access Logo

Energy-Efficient Multi-Core Scheduling for Real-Time DAG Tasks

Authors Zhishan Guo, Ashikahmed Bhuiyan, Abusayeed Saifullah, Nan Guan, Haoyi Xiong

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.22.pdf
  • Filesize: 0.67 MB
  • 21 pages

Document Identifiers

Author Details

Zhishan Guo
Ashikahmed Bhuiyan
Abusayeed Saifullah
Nan Guan
Haoyi Xiong

Cite As Get BibTex

Zhishan Guo, Ashikahmed Bhuiyan, Abusayeed Saifullah, Nan Guan, and Haoyi Xiong. Energy-Efficient Multi-Core Scheduling for Real-Time DAG Tasks. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 22:1-22:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.22

Abstract

In this work, we study energy-aware real-time scheduling of a set of sporadic Directed Acyclic Graph (DAG) tasks with implicit deadlines. While meeting all real-time constraints, we try to identify the best task allocation and execution pattern such that the average power consumption of the whole platform is minimized. To the best of our knowledge, this is the first work that addresses the power consumption issue in scheduling multiple DAG tasks on multi-cores and allows intra-task processor sharing. We first adapt the decomposition-based framework for federated scheduling and propose an energy-sub-optimal scheduler. Then we derive an approximation algorithm to identify processors to be merged together for further improvements in energy-efficiency and to prove the bound of the approximation ratio. We perform a simulation study to demonstrate the effectiveness and efficiency of the proposed scheduling. The simulation results show that our algorithms achieve an energy saving of 27% to 41% compared to existing DAG task
schedulers.

Subject Classification

Keywords
  • Parallel task
  • Real-time scheduling
  • Energy minimization
  • Convex optimization

Metrics

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

References

  1. 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
  2. Sanjoy Baruah. Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In 26th Euromicro Conference on Real-Time Systems, pages 97-105. IEEE, 2014. Google Scholar
  3. 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
  4. 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
  5. Cristina Bazgan, Bruno Escoffier, and Vangelis Th. Paschos. Completeness in standard and differential approximation classes: Poly-apx- and ptas-completeness. Theoretical Computer Science, 339(2-3):272-292, 2005. Google Scholar
  6. 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
  7. 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
  8. Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004. Google Scholar
  9. David Chandler. Introduction to modern statistical mechanics. pp. 288. Foreword by David Chandler. Oxford University Press, Sep 1987. ISBN-10: 0195042778. ISBN-13: 9780195042771, page 288, 1987. Google Scholar
  10. 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
  11. 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
  12. 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
  13. 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
  14. Nathan Fisher, Jian-Jia Chen, Shengquan Wang, and Lothar Thiele. Thermal-aware global real-time scheduling on multicore systems. In Real-Time and Embedded Technology and Applications Symposium, 2009. RTAS 2009. 15th IEEE, pages 131-140. IEEE, 2009. Google Scholar
  15. https://www.mathworks.com/help/optim/ug/fmincon.html. URL: https://www.mathworks.com/help/optim/ug/fmincon.html..
  16. https://en.wikipedia.org/wiki/Gamma_distribution URL: https://en.wikipedia.org/wiki/Gamma_distribution.
  17. 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
  18. Magnús Halldórssonz and Jaikumar Radhakrishnan. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica, 18(1):145-163, 1997. Google Scholar
  19. 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
  20. 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
  21. 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
  22. 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
  23. Keqin Li. Energy efficient scheduling of parallel tasks on multiprocessor computers. J. Supercomput, 60:223-247, 2012. Google Scholar
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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. ACM, 2016. Google Scholar
  29. 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
  30. 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
  31. 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
  32. Ruibin Xu, Dakai Zhu, Cosmin Rusu, Rami Melhem, and Daniel Mossé. Energy-efficient policies for embedded clusters. ACM SIGPLAN Notices, 40(7):1-10, 2005. Google Scholar
  33. 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
  34. 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
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