Ashikahmed Bhuiyan
Abusayeed Saifullah
Haoyi Xiong
Skip Abstract Section
Abstract
This work studies 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 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. First, we 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. The effectiveness of the proposed approach is evaluated both theoretically via approximation ratio bounds and also experimentally through simulation study. Experimental results on randomly generated workloads show that our algorithms achieve an energy saving of 60% to 68% compared to existing DAG task schedulers.
- Hakan Aydin and Qi Yang. 2003. Energy-aware partitioning for multiprocessor real-time systems. In Proceedings of the International Parallel and Distributed Processing Symposium. IEEE, 9--pp. Google Scholar
Digital Library
- Sanjoy Baruah. 2014. Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In Proceedings of the 26th Euromicro Conference on Real-Time Systems. IEEE, 97--105. Google ScholarDigital Library
- Sanjoy Baruah, Vincenzo Bonifaci, and Alberto Marchetti-Spaccamela. 2015. The global EDF scheduling of systems of conditional sporadic DAG tasks. In Proceedings of the 27th Euromicro Conference on Real-Time Systems. IEEE, 222--231. Google ScholarDigital Library
- Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. 2012. A generalized parallel task model for recurrent real-time processes. In Proceedings of the 33rd IEEE Real-Time Systems Symposium (RTSS’12). IEEE, 63--72. Google ScholarDigital Library
- Cristina Bazgan, Bruno Escoffier, and Vangelis Th. Paschos. 2005. Completeness in standard and differential approximation classes: Poly-APX- and PTAS-completeness. Theor. Comput. Sci. 339, 2--3 (2005), 272--292. Google ScholarDigital Library
- Enrico Bini, Giorgio Buttazzo, and Giuseppe Lipari. 2009. Minimizing CPU energy in real-time systems with discrete speed management. ACM Trans. Embed. Comput. Syst. 8, 4 (2009), 31. Google ScholarDigital Library
- Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Sebastian Stiller, and Andreas Wiese. 2013. Feasibility analysis in the sporadic DAG task model. In Proceedings of the 25th Euromicro Conference on Real-Time Systems. IEEE, 225--233. Google ScholarDigital Library
- Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press. Google ScholarDigital Library
- David Chandler. 1987. Introduction to Modern Statistical Mechanics. Oxford University Press, Oxford, 288.Google Scholar
- Gang Chen, Kai Huang, and Alois Knoll. 2014. Energy optimization for real-time multiprocessor system-on-chip with optimal DVFS and DPM combination. ACM Trans. Embed. Comput. Syst. 13, 3s (2014), 111. Google ScholarDigital Library
- Jian-Jia Chen, Andreas Schranzhofer, and Lothar Thiele. 2009. Energy minimization for periodic real-time tasks on heterogeneous processing units. In Proceedings of the IEEE International Symposium on Parallel 8 Distributed Processing (IPDPS’09). IEEE, 1--12. Google ScholarDigital Library
- Daniel Cordeiro, Gregory Mouni, Swann Perarnau, Denis Trystram, Jean-Marc Vincent, and Frederic Wagner. 2010. Random graph generation for scheduling simulations. In Proceedings of the 3rd International ICST Conference on Simulation Tools and Techniques. Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, 60. Google ScholarDigital Library
- Vinay Devadas and Hakan Aydin. 2010. Coordinated power management of periodic real-time tasks on chip multiprocessors. In Proceedings of the 2010 International Green Computing Conference. IEEE, 61--72. Google ScholarDigital Library
- Nathan Fisher, Jian-Jia Chen, Shengquan Wang, and Lothar Thiele. 2009. Thermal-aware global real-time scheduling on multicore systems. In Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium, (RTAS’09). IEEE, 131--140. Google ScholarDigital Library
- Fmincon. 2018. Retrieved from https://www.mathworks.com/help/optim/ug/fmincon.html.Google Scholar
- Gamma Distribution. 2018. Retrieved from https://en.wikipedia.org/wiki/Gamma_distribution.Google Scholar
- Yifeng Guo, Dakai Zhu, and Hakan Aydin. 2011. Reliability-aware power management for parallel real-time applications with precedence constraints. In Proceedings of the 2011 International Green Computing Conference and Workshops (IGCC’11). IEEE, 1--8. Google ScholarDigital Library
- Zhishan Guo, Ashikahmed Bhuiyan, Abusayeed Saifullah, Nan Guan, and Haoyi Xiong. 2017. Energy-efficient multi-core scheduling for real-time DAG tasks. In Proceedings of the LIPIcs-Leibniz International Proceedings in Informatics, Vol. 76. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.Google Scholar
- Magnús Halldórssonz and Jaikumar Radhakrishnan. 1997. Greed is good: Approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18, 1 (1997), 145--163. Google ScholarDigital Library
- Ravindra Jejurikar. 2005. Energy aware non-preemptive scheduling for hard real-time systems. In Proceedings of the 17th Euromicro Conference on Real-Time Systems (ECRTS’05). IEEE, 21--30. Google ScholarDigital Library
- Xu Jiang, Nan Guan, Xiang Long, and Wang Yi. 2017. Semi-federated scheduling of parallel real-time tasks on multiprocessors. arXiv Preprint arXiv:1705.03245 (2017).Google Scholar
- Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2013. Outstanding paper award: Analysis of global EDF for parallel tasks. In Proceedings of the 25th Euromicro Conference on Real-Time Systems. IEEE, 3--13. Google ScholarDigital Library
- Jing Li, Jian-Jia Chen, Kunal Agrawal, Chenyang Lu, Chris Gill, and Abusayeed Saifullah. 2014. Analysis of federated and global scheduling for parallel real-time tasks. In Proceedings of the 26th Euromicro Conference on Real-Time Systems. IEEE, 85--96. Google ScholarDigital Library
- Keqin Li. 2012. Energy efficient scheduling of parallel tasks on multiprocessor computers. J. Supercomput. 60, 2 (2012), 223--247. Google ScholarDigital Library
- Cong Liu, Jian Li, Wei Huang, Juan Rubio, Evan Speight, and Xiaozhu Lin. 2012. Power-efficient time-sensitive mapping in heterogeneous systems. In Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques. ACM, 23--32. Google ScholarDigital Library
- Jing Mei, Kenli Li, and Keqin Li. 2014. Energy-aware task scheduling in heterogeneous computing environments. Cluster Comput. 17, 2 (2014), 537--550. Google ScholarCross Ref
- Sujay Narayana, Pengcheng Huang, Georgia Giannopoulou, Lothar Thiele, and R. Venkatesha Prasad. 2016. Exploring energy saving for mixed-criticality systems on multi-cores. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’16). IEEE, 1--12.Google Scholar
- ODROID XU-3. 2013. Retrieved from http://www.hardkernel.com/main/main.php.Google Scholar
- Santiago Pagani and Jian-Jia Chen. 2013. Energy efficient task partitioning based on the single frequency approximation scheme. In Proceedings of the IEEE 34th Real-Time Systems Symposium (RTSS’13). IEEE, 308--318. Google ScholarDigital Library
- Santiago Pagani and Jian-Jia Chen. 2014. Energy efficiency analysis for the single frequency approximation (SFA) scheme. ACM Trans. Embed. Comput. Syst. 13, 5s (2014), 158. Google ScholarDigital Library
- Antonio Paolillo, Joël Goossens, Pradeep M. Hettiarachchi, and Nathan Fisher. 2014. Power minimization for parallel real-time systems with malleable jobs and homogeneous frequencies. In Proceedings of the IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications. IEEE, 1--10.Google ScholarCross Ref
- Antonio Paolillo, Paul Rodriguez, Nikita Veshchikov, Joël Goossens, and Ben Rodriguez. 2016. 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. ACM, 329--338. Google ScholarDigital Library
- Risat Pathan, Petros Voudouris, and Per Stenström. 2018. Scheduling parallel real-time recurrent tasks on multicore platforms. IEEE Trans. Parallel Distrib. Syst. 29, 4 (2018), 915--928.Google ScholarCross Ref
- Xuan Qi and Dakai Zhu. 2011. Energy efficient block-partitioned multicore processors for parallel applications. J. Comput. Sci. Technol. 26, 3 (2011), 418--433.Google ScholarCross Ref
- Jaeyong Rho, Takuya Azumi, Mayo Nakagawa, Kenya Sato, and Nobuhiko Nishio. 2017. Scheduling parallel and distributed processing for automotive data stream management system. J. Parallel Distrib. Comput. 109 (2017), 286--300. Google ScholarDigital Library
- Abusayeed Saifullah, David Ferry, Jing Li, Kunal Agrawal, Chenyang Lu, and Christopher D. Gill. 2014. Parallel real-time scheduling of DAGs. IEEE Trans. Parallel Distrib. Syst. 25, 12 (2014), 3242--3252.Google ScholarCross Ref
- Sebastian Siebert and Jochen Teizer. 2014. Mobile 3D mapping for surveying earthwork projects using an unmanned aerial vehicle (UAV) system. Autom. Construct. 41 (2014), 1--14.Google ScholarCross Ref
- Huiting Xu, Fanxin Kong, and Qingxu Deng. 2012. Energy minimizing for parallel real-time tasks based on level-packing. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. IEEE, 98--103. Google ScholarDigital Library
- Ruibin Xu, Dakai Zhu, Cosmin Rusu, Rami Melhem, and Daniel Mossé. 2005. Energy-efficient policies for embedded clusters. In ACM SIGPLAN Notices, Vol. 40. ACM, 1--10. Google ScholarDigital Library
- Dakai Zhu, Nevine AbouGhazaleh, Daniel Mossé, and Rami Melhem. 2002. Power aware scheduling for AND/OR graphs in multiprocessor real-time systems. In Proceedings of the International Conference on Parallel Processing, 2002. IEEE, 593--601. Google ScholarDigital Library
- Dakai Zhu, Daniel Mosse, and Rami Melhem. 2004. Power-aware scheduling for AND/OR graphs in real-time systems. IEEE Trans. Parallel Distrib. Syst. 15, 9 (2004), 849--864. Google ScholarDigital Library
Index Terms
- Energy-Efficient Real-Time Scheduling of DAG Tasks
Recommendations
Real-Time Scheduling of DAG Tasks with Arbitrary Deadlines
Real-time and embedded systems are shifting from single-core to multi-core processors, on which the software must be parallelized to fully utilize the computation capacity of the hardware. Recently, much work has been done on real-time scheduling of ...
Analysis on quantum-based fixed priority scheduling of real-time tasks
ICUIMC '09: Proceedings of the 3rd International Conference on Ubiquitous Information Management and CommunicationFixed priority schedulers are widely used for real-time systems, and there were efforts to improve the schedulability. Preemption threshold scheduling is one of such efforts with a dual priority scheme. It increases the schedulability by introducing ...
Decomposition-based scheduling for parallel real-time tasks on multiprocessors
AbstractThis paper addresses the problem of multiprocessor real-time scheduling for parallel tasks modeled as directed acyclic graph (DAG). We propose a new decomposition-based scheduling algorithm to schedule parallel DAG tasks with implicit-...
Graphical abstractDisplay Omitted
Highlights- An improved decomposition-based scheduling algorithm is proposed for parallel tasks.
Comments