Saad Zia Sheikh
Muhammad Adeel Pasha
Skip Abstract Section
Abstract
As real-time embedded systems are evolving in scale and complexity, the demand for a higher performance at a minimum energy consumption has become a necessity. Consequently, many embedded systems are now adopting multicore architectures into their design. However, scheduling on multicores is not a trivial task and scheduling to minimize the energy consumption further increases the complexity of the problem. This problem is especially aggravated for hard real-time systems where failure to meet a deadline can be catastrophic. Such scheduling algorithms yearn for a polynomial time complexity for the task-to-core assignment problem with an objective to minimize the overall energy consumption. There is now a trend toward heterogeneous multicores where cores differ in power, performance, and architectural capabilities. The desired performance and energy consumption is attained by assigning a task to the core that is best suited for it. In this article, we present a survey on energy-efficient multicore scheduling algorithms for hard real-time systems. We summarize various algorithms reported in the literature and classify them based on Partitioned, Semi-Partitioned, and Global scheduling techniques for both homogeneous and heterogeneous multicores. We also present a detailed discussion on various open issues within this domain.
- Björn Andersson and Jan Jonsson. 2000. Some insights on fixed-priority preemptive non-partitioned multiprocessor scheduling. In Proceedings of the IEEE Real-Time Systems Symposium, Work-in-Progress Session.Google Scholar
- Muhammad Ali Awan. 2014. Energy and Temperature Aware Real-Time Systems. Ph.D. Dissertation. University of Porto.Google Scholar
- Muhammad Ali Awan and Stefan M. Petters. 2013. Energy-aware partitioning of tasks onto a heterogeneous multi-core platform. In Proceedings of the IEEE 19th Real-Time and Embedded Tech. and Applications Symposium (RTAS’13). IEEE, 205--214. Google ScholarDigital Library
- Hakan Aydin, Rami Melhem, Daniel Mossé, and Pedro Mejía-Alvarez. 2001. Determining optimal processor speeds for periodic real-time tasks with different power characteristics. In Proceedings of the 13th Euromicro Conference on Real-Time Systems (RTS’01). IEEE, 225--232. Google ScholarDigital Library
- Hakan Aydin and Qi Yang. 2003. Energy-aware partitioning for multiprocessor real-time systems. In Proceedings of the International Parallel and Distributed Processing Symposium, 2003. IEEE, 9--pp. Google ScholarDigital Library
- Mario Bambagini, Mauro Marinoni, Hakan Aydin, and Giorgio Buttazzo. 2016. Energy-aware scheduling for real-time systems: A survey. ACM Trans. Embed. Comput. Syst. 15, 1 (2016), 7. Google ScholarDigital Library
- Sanjoy Baruah, Marko Bertogna, and Giorgio Buttazzo. 2015. Multiprocessor Scheduling for Real-Time Systems. Springer. Google ScholarDigital Library
- Sanjoy K. Baruah. 2004. Partitioning real-time tasks among heterogeneous multiprocessors. In Proceedings of the International Conference on Parallel Processing (ICPP’04). IEEE, 467--474. Google ScholarDigital Library
- Michela Becchi and Patrick Crowley. 2006. Dynamic thread assignment on heterogeneous multiprocessor architectures. In Proceedings of the 3rd Conference on Computing Frontiers. ACM, 29--40. Google ScholarDigital Library
- Marko Bertogna. 2008. Real-time scheduling analysis for multiprocessor platforms. Doctoral Dissertation. Scuola Superiore Sant'Anna, Pisa, Italy. Retrieved from algogroup.unimore.it.Google Scholar
- Khurram Bhatti, Cecile Belleudy, and Michel Auguin. 2010. Power management in real time embedded systems through online and adaptive interplay of DPM and DVFS policies. In Proceedings of the IEEE/IFIP 8th International Conference on Embedded and Ubiquitous Computing (EUC’10). IEEE, 184--191. Google ScholarDigital Library
- Muhammad Khurram Bhatti, Cécile Belleudy, and Michel Auguin. 2010. An inter-task real time DVFS scheme for multiprocessor embedded systems. In Proceedings of the Euromicro Conference on Digital System Design and Architectures for Signal and Image Processing (DASIP’10). IEEE, 136--143.Google ScholarCross Ref
- Bach D. Bui, Marco Caccamo, Lui Sha, and Joseph Martinez. 2008. Impact of cache partitioning on multi-tasking real time embedded systems. In Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’08). IEEE, 101--110. Google ScholarDigital Library
- Alan Burns, Robert I. Davis, P. Wang, and Fengxiang Zhang. 2012. Partitioned EDF scheduling for multiprocessors using a C= D task splitting scheme. Real-Time Syst. 48, 1 (2012), 3--33. Google ScholarDigital Library
- 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, Heng-Ruey Hsu, Kai-Hsiang Chuang, Chia-Lin Yang, Ai-Chun Pang, and Tei-Wei Kuo. 2004. Multiprocessor energy-efficient scheduling with task migration considerations. In Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS’04). IEEE, 101--108. Google ScholarDigital Library
- Jian-Jia Chen, Heng-Ruey Hsu, and Tei-Wei Kuo. 2006. Leakage-aware energy-efficient scheduling of real-time tasks in multiprocessor systems. In Proceedings of the 12th IEEE Real-Time and Embedded Tech. and Applications Symposium. IEEE, 408--417. Google ScholarDigital Library
- Jian-Jia Chen and Tei-Wei Kuo. 2005. Multiprocessor energy-efficient scheduling for real-time tasks with different power characteristics. In Proceedings of the International Conference on Parallel Processing (ICPP’05). IEEE, 13--20. Google ScholarDigital Library
- Hui Cheng and Steve Goddard. 2005. Integrated device scheduling and processor voltage scaling for system-wide energy conservation. In Proceedings of the 2005 Workshop on Power Aware Real-time Computing. Citeseer.Google Scholar
- Hoon Sung Chwa, Jaebaek Seo, Jinkyu Lee, and Insik Shin. 2015. Optimal real-time scheduling on two-type heterogeneous multicore platforms. In Proceedings of the Real-Time Systems Symposium. IEEE, 119--129. Google ScholarDigital Library
- Alexei Colin, Arvind Kandhalu, and Ragunathan Raj Rajkumar. 2016. Energy-efficient allocation of real-time applications onto single-ISA heterogeneous multi-core processors. J. Sig. Proc. Syst. 84, 1 (2016), 91--110. Google ScholarDigital Library
- Robert I. Davis and Alan Burns. 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surveys 43, 4 (2011), 35. Google ScholarDigital Library
- Vinay Devadas and Hakan Aydin. 2012. On the interplay of voltage/frequency scaling and device power management for frame-based real-time embedded applications. IEEE Trans. Comput. 61, 1 (2012), 31--44. Google ScholarDigital Library
- Abdullah Elewi, Mohamed Shalan, Medhat Awadalla, and Elsayed M. Saad. 2014. Energy-efficient task allocation techniques for asymmetric multiprocessor embedded systems. ACM Trans. Embed. Comput. Syst. 13, 2s (2014), 71. Google ScholarDigital Library
- Xing Fu, Khairul Kabir, and Xiaorui Wang. 2011. Cache-aware utilization control for energy efficiency in multi-core real-time systems. In Proceedings of the 23rd Euromicro Conference on Real-Time Systems (ECRTS’11). IEEE, 102--111. Google ScholarDigital Library
- Marco E. T. Gerards, Johann L. Hurink, and Philip K. F. Hölzenspies. 2016. A survey of offline algorithms for energy minimization under deadline constraints. J. Schedul. 19, 1 (2016), 3--19. Google ScholarDigital Library
- Marco E. T. Gerards, Johann L. Hurink, and Jan Kuper. 2015. On the interplay between global DVFS and scheduling tasks with precedence constraints. IEEE Trans. Comput. 64, 6 (2015), 1742--1754.Google Scholar
- Marco E. T. Gerards and Jan Kuper. 2013. Optimal DPM and DVFS for frame-based real-time systems. ACM Trans. Architect. Code Optim. 9, 4 (2013), 41. Google ScholarDigital Library
- Giovani Gracioli, Ahmed Alhammad, Renato Mancuso, Antônio Augusto Fröhlich, and Rodolfo Pellizzoni. 2015. A survey on cache management mechanisms for real-time embedded systems. ACM CSUR 48, 2 (2015), 32. Google ScholarDigital Library
- Nan Guan, Martin Stigge, Wang Yi, and Ge Yu. 2009. Cache-aware scheduling and analysis for multicores. In Proceedings of the 7th ACM International Conference on Embedded Software. ACM, 245--254. 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 LIPIcs-Leibniz International Proceedings in Informatics, Vol. 76. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.Google Scholar
- Jian-Jun Han, Xiaodong Wu, Dakai Zhu, Hai Jin, Laurence T. Yang, and Jean-Luc Gaudiot. 2012. Synchronization-aware energy management for VFI-based multicore real-time systems. IEEE Trans. Comput. 61, 12 (2012), 1682--1696. Google ScholarDigital Library
- Vinay Hanumaiah and Sarma Vrudhula. 2012. Temperature-aware DVFS for hard real-time applications on multicore processors. IEEE Trans. Comput. 61, 10 (2012), 1484--1494. Google ScholarDigital Library
- Shaoxiong Hua and Gang Qu. 2005. Power minimization techniques on distributed real-time systems by global and local slack management. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference. ACM, 830--835. Google ScholarDigital Library
- Kai Huang, Luca Santinelli, Jian-Jia Chen, Lothar Thiele, and Giorgio C. Buttazzo. 2009. Periodic power management schemes for real-time event streams. In Proceedings of the 48th IEEE Conference on Decision and Control, 2009 Held Jointly with the 2009 28th Chinese Control Conference (CDC/CCC’09). IEEE, 6224--6231.Google Scholar
- Tai-Yi Huang, Yu-Che Tsai, and Edward T.-H. Chu. 2007. A near-optimal solution for the heterogeneous multi-processor single-level voltage setup problem. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS’07). IEEE, 1--10.Google Scholar
- Tohru Ishihara and Hiroto Yasuura. 1998. Voltage scheduling problem for dynamically variable voltage processors. In Proceedings of the 1998 International Symposium on Low Power Electronics and Design. ACM, 197--202. Google ScholarDigital Library
- Ravindra Jejurikar, Cristiano Pereira, and Rajesh Gupta. 2004. Leakage aware dynamic voltage scaling for real-time embedded systems. In Proceedings of the 41st Annual Design Automation Conference. ACM, 275--280. Google ScholarDigital Library
- Hyeran Jeon, Woo Hyong Lee, and Sung Woo Chung. 2010. Load unbalancing strategy for multicore embedded processors. IEEE Trans. Comput. 59, 10 (2010), 1434--1440. Google ScholarDigital Library
- Omer Khan and Sandip Kundu. 2010. A self-adaptive scheduler for asymmetric multi-cores. In Proceedings of the 20th Great Lakes Symposium on International Conference on Very Large Scale Integration (VLSI’10). ACM, 397--400. Google ScholarDigital Library
- Hyoseung Kim, Arvind Kandhalu, and Ragunathan Rajkumar. 2013. A coordinated approach for practical OS-level cache management in multi-core real-time systems. In Proceedings of the 25th Euromicro Conference on Real-Time Systems (ECRTS’13). IEEE, 80--89. Google ScholarDigital Library
- Fanxin Kong, Nan Guan, Qingxu Deng, and Wang Yi. 2011. Energy-efficient scheduling for parallel real-time tasks based on level-packing. In Proceedings of the 2011 ACM Symposium on Applied Computing. ACM, 635--640. Google ScholarDigital Library
- Fanxin Kong, Wang Yi, and Qingxu Deng. 2011. Energy-efficient scheduling of real-time tasks on cluster-based multicores. In Proceedings of the Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE’11). IEEE, 1--6.Google Scholar
- Chin-Fu Kuo and Yung-Feng Lu. 2014. Energy-efficient assignment for tasks on non-dvs heterogeneous multiprocessor system. In Proceedings of the 2014 Conference on Research in Adaptive and Convergent Systems. ACM, 314--319. Google ScholarDigital Library
- Yann-Hang Lee, Krishna P. Reddy, and C. Mani Krishna. 2003. Scheduling techniques for reducing leakage power in hard real-time systems. In Proceedings of the 15th Euromicro Conference on Real-Time Systems. IEEE, 105--112.Google Scholar
- Vincent Legout, Mathieu Jan, and Laurent Pautet. 2013. A scheduling algorithm to reduce the static energy consumption of multiprocessor real-time systems. In Proceedings of the 21st International Conference on Real-Time Networks and Systems. ACM, 99--108. Google ScholarDigital Library
- Dawei Li and Jie Wu. 2012. Energy-aware scheduling for frame-based tasks on heterogeneous multiprocessor platforms. In Proceedings of the 41st International Conference on Parallel Processing (ICPP’12). IEEE, 430--439. Google ScholarDigital Library
- Di Liu, Jelena Spasic, Gang Chen, and Todor Stefanov. 2015. Energy-efficient mapping of real-time streaming applications on cluster heterogeneous mpsocs. In Proceedings of the 13th IEEE Symposium on Embedded Systems for Real-time Multimedia (ESTIMedia’15). IEEE, 1--10.Google ScholarCross Ref
- Di Liu, Jelena Spasic, Peng Wang, and Todor Stefanov. 2016. Energy-efficient scheduling of real-time tasks on heterogeneous multicores using task splitting. In Proceedings of the IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’16). IEEE, 149--158.Google ScholarCross Ref
- Jiong Luo and Niraj K. Jha. 2007. Power-efficient scheduling for heterogeneous distributed real-time embedded systems. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 26, 6 (2007), 1161--1170. Google ScholarDigital Library
- Yangchun Luo, Venkatesan Packirisamy, Wei-Chung Hsu, and Antonia Zhai. 2010. Energy efficient speculative threads: Dynamic thread allocation in Same-ISA heterogeneous multicore systems. In Proceedings of the 19th International Conference on Parallel Architectures and Compilation Techniques. ACM, 453--464. Google ScholarDigital Library
- Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. 2016. A survey on static cache analysis for real-time systems. Leibniz Trans. Embed. Syst. 3, 1 (2016), 05--1.Google Scholar
- Rajib Mall. 2009. Real-time Systems: Theory and Practice. Pearson Education India. Google ScholarDigital Library
- José Luis March, Salvador Petit, Julio Sahuquillo, Houcine Hassan, and José Duato. 2014. Dynamic WCET estimation for real-time multicore embedded systems supporting DVFS. In Proceedings of the IEEE International Conference on High Performance Computing and Communications. IEEE, 27--33. Google ScholarDigital Library
- José Luis March, Julio Sahuquillo, Salvador Petit, Houcine Hassan, and José Duato. 2013. Power-aware scheduling with effective task migration for real-time multicore embedded systems. Concurr. Comput.: Pract. Exper. 25, 14 (2013), 1987--2001.Google ScholarCross Ref
- Alessandra Melani, Marko Bertogna, Robert I. Davis, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Giorgio Buttazzo. 2017. Exact response time analysis for fixed priority memory-processor co-scheduling. IEEE Trans. Comput. 66, 4 (2017), 631--646. Google ScholarDigital Library
- Sparsh Mittal. 2014. A survey of architectural techniques for improving cache power efficiency. Sustain. Comput.: Info. Syst. 4, 1 (2014), 33--43.Google ScholarCross Ref
- Sparsh Mittal. 2016. A survey of techniques for architecting and managing asymmetric multicore processors. ACM Comput. Surveys 48, 3 (2016), 45. 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 (RTCSA’14). IEEE, 1--10.Google ScholarCross Ref
- Sangyoung Park, Jaehyun Park, Donghwa Shin, Yanzhi Wang, Qing Xie, Massoud Pedram, and Naehyuck Chang. 2013. Accurate modeling of the delay and energy overhead of dynamic voltage and frequency scaling in modern microprocessors. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 32, 5 (2013), 695--708. Google ScholarDigital Library
- Vinicius Petrucci, Orlando Loques, Daniel Mossé, Rami Melhem, Neven Abou Gazala, and Sameh Gobriel. 2015. Energy-efficient thread assignment optimization for heterogeneous multicore systems. ACM Trans. Embed. Comput. Syst. 14, 1 (2015), 15. Google ScholarDigital Library
- Mihai Pricopi, Thannirmalai Somu Muthukaruppan, Vanchinathan Venkataramani, Tulika Mitra, and Sanjay Vishin. 2013. Power-performance modeling on asymmetric multi-cores. In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES’13). IEEE, 1--10. Google ScholarDigital Library
- Xuan Qi, Dakai Zhu, and Hakan Aydin. 2010. Global reliability-aware power management for multiprocessor real-time systems. In Proceedings of the IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’10). IEEE, 183--192. Google ScholarDigital Library
- Robert R. Schaller. 1997. Moore’s law: Past, present and future. IEEE Spectr. 34, 6 (1997), 52--59. Google ScholarDigital Library
- Marcus T. Schmitz and Bashir M. Al-Hashimi. 2001. Considering power variations of DVS processing elements for energy minimisation in distributed systems. In Proceedings of the 14th International Symposium on Systems Synthesis. ACM, 250--255. Google ScholarDigital Library
- Euiseong Seo, Jinkyu Jeong, Seonyeong Park, and Joonwon Lee. 2008. Energy efficient scheduling of real-time tasks on multicore processors. IEEE Trans. Parallel Distrib. Syst. 19, 11 (2008), 1540--1552. Google ScholarDigital Library
- Jagpreet Singh and Nitin Auluck. 2016. Real time scheduling on heterogeneous multiprocessor systems - A survey. In Proceedings of the 4th International Conference on Parallel, Distributed and Grid Computing (PDGC’16). IEEE, 73--78.Google ScholarCross Ref
- Jelena Spasic, Di Liu, and Todor Stefanov. 2016. Energy-efficient mapping of real-time applications on heterogeneous mpsocs using task replication. In Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS’16). IEEE, 1--10. Google ScholarDigital Library
- Tomohiro Tatematsu, Hideki Takase, Gang Zeng, Hiroyuki Tomiyama, and Hiroaki Takada. 2011. Checkpoint extraction using execution traces for intra-task DVFS in embedded systems. In Proceedings of the 6th IEEE International Symposium on Electronic Design, Test and Application (DELTA’11). IEEE, 19--24. Google ScholarDigital Library
- Mason Thammawichai and Eric C. Kerrigan. 2016. Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors. arXiv preprint arXiv:1607.07763.Google Scholar
- Xiaodong Wu, Yuan Lin, Jian-Jun Han, and Jean-Luc Gaudiot. 2010. Energy-efficient scheduling of real-time periodic tasks in multicore systems. In Proceedings of the IFIP International Conference on Network and Parallel Computing. Springer, 344--357. Google ScholarDigital Library
- Changjiu Xian, Yung-Hsiang Lu, and Zhiyuan Li. 2007. Energy-aware scheduling for real-time multiprocessor systems with uncertain task execution time. In Proceedings of the 44th ACM/IEEE Design Automation Conference (DAC’07). IEEE, 664--669. Google ScholarDigital Library
- Frances Yao, Alan Demers, and Scott Shenker. 1995. A scheduling model for reduced CPU energy. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science. IEEE, 374--382. Google ScholarDigital Library
- Han-Saem Yun and Jihong Kim. 2003. On energy-optimal voltage scheduling for fixed-priority hard real-time systems. ACM Trans. Embed. Comput. Syst. 2, 3 (2003), 393--430. Google ScholarDigital Library
- Gang Zeng, Tetsuo Yokoyama, Hiroyuki Tomiyama, and Hiroaki Takada. 2009. Practical energy-aware scheduling for real-time multiprocessor systems. In Proceedings of the 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’09). IEEE, 383--392. Google ScholarDigital Library
- Yumin Zhang, Xiaobo Sharon Hu, and Danny Z. Chen. 2002. Task scheduling and voltage selection for energy minimization. In Proceedings of the 39th Annual Design Automation Conference. ACM, 183--188. Google ScholarDigital Library
- Liu Zheng. 2007. A task migration constrained energy-efficient scheduling algorithm for multiprocessor real-time systems. In Proceedings of the International Conference on Wireless Communications (WiCom’07). IEEE, 3055--3058.Google ScholarCross Ref
- Dakai Zhu, Rami Melhem, and Bruce R. Childers. 2003. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems. IEEE Trans. Parallel Distrib. Syst. 14, 7 (2003), 686--700. Google ScholarDigital Library
Index Terms
- Energy-Efficient Multicore Scheduling for Hard Real-Time Systems: A Survey
Recommendations
Energy-efficient Real-time Scheduling on Multicores: A Novel Approach to Model Cache Contention
With the increasing demand for higher performance, the adoption of multicores has been a major stepping stone in the evolution of hard real-time systems. Though the computational bandwidth is increased due to parallel processing, the indispensable ...
Energy-Efficient Real-Time Scheduling of DAG Tasks
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 ...
Reliability-Aware Energy Management for Embedded Real-Time Systems with (m, k)-Hard Timing Constraint
While energy consumption and Quality of Service (QoS) are primary concerns for the design of embedded systems, reliability requirement has become increasingly important in the development of today's pervasive computing systems. In this paper, we present ...
Comments