Power efficient rate monotonic scheduling for multi-core systems. (English) Zbl 1231.68087
Summary: More computational power is offered by current real-time systems to cope with CPU intensive applications. However, this facility comes at the price of more energy consumption and eventually higher heat dissipation. As a remedy, these issues are being encountered by adjusting the system speed on the fly so that application deadlines are respected and also, the overall system energy consumption is reduced. In addition, the current state of the art of multi-core technology opens further research opportunities for energy reduction through power efficient scheduling. However, the multi-core front is relatively unexplored from the perspective of task scheduling. To the best of our knowledge, very little is known as of yet to integrate power efficiency component into real-time scheduling theory that is tailored for multi-core platforms. In this paper, we first propose a technique to find the lowest core speed to schedule individual tasks. The proposed technique is experimentally evaluated and the results show the supremacy of our test over the existing counterparts. Following that, the lightest task shifting policy is adapted for balancing core utilization, which is utilized to determine the uniform system speed for a given task set. The aforementioned guarantees that: (i) all the tasks fulfill their deadlines and (ii) the overall system energy consumption is reduced.
MSC:
| 68M14 | Distributed systems |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Keywords:
real-time systems; non-preemptive scheduling; fixed-priority scheduling; feasibility analysis; online schedulability testsReferences:
| [1] | N. AbouGhazaleh, B. Childers, D. Mosse, R. Melhem, M. Craven, Energy management for real-time embedded applications with compiler support, in: ACM SIGPLAN Conference on Languages, Compilers, and Tools for Embedded Systems, 2003, pp. 284–293. |
| [2] | J. Anderson, S. Baruah, Energy-efficient synthesis of periodic task systems upon identical multiprocessor platforms, in: Proc. Distributed Computing Systems, 24th International Conference, 2004, pp. 428–435. |
| [3] | H. Aydin, R. Melhem, D. Mosse, P. Alvarez, Dynamic and aggressive scheduling techniques for power-aware real-time systems, in: Proc. IEEE Real-Time Syst. Symp., 2001, p. 95. |
| [4] | Bini, E.; Buttazzo, G. C.; Buttazzo, G.: Rate monotonic analysis: the hyperbolic bound, IEEE trans. Comput. 7, No. 52, 933-942 (2003) |
| [5] | Bini, E.; Buttazzo, G. C.; Lipari, G.: Minimizing CPU energy in real-time systems with discrete speed management, ACM trans. Embedded comput. Syst. 8, No. 4 (2009) |
| [6] | J. Brateman, C. Xian, Y. Lu, Frequency and speed setting for energy conservation in autonomous mobile robots, in: Proceedings of the IFIP International Federation for Information Processing, vol. 249/2008, 2008, pp. 197–216. |
| [7] | Burd, T. D.; Pering, T. A.; Stratakos, A. J.; Brodersen, R. W.: A dynamic voltage scaled microprocessor system, IEEE J. Solid state circuits 35, No. 11, 1571-1580 (2000) |
| [8] | Burns, A.; Wellings, A. J.: Real-time systems and programming languages, (2009) · Zbl 0768.68009 |
| [9] | Chandrakasan, A. P.; Brodersen, R. W.: Low power design, (1995) |
| [10] | Chandrakasan, A. P.; Sheng, S.; Brodersen, R. W.: Low power CMOS digital design, IEEE J. Solid state circuits, 472-484 (1992) |
| [11] | Crusoe Processor Model TM5800 Specifications, http://www.charmed.com/PDF/TM5800.pdf,2011. |
| [12] | Davis, R. I.; Rothvo, T.; Baruah, S. K.; Burns, A.: Exact quantification of the sub-optimality of uniprocessor fixed priority pre-emptive scheduling, Real time syst. 43, No. 3, 211-258 (2009) · Zbl 1184.68121 · doi:10.1007/s11241-009-9079-4 |
| [13] | L. George, N. Riverre N, M. Spuri, Preemptive and Non-Preemptive Real-Time Uniprocessor Scheduling, Research Report 2966, INRIA, France, 1996. |
| [14] | Gloker, T.; Meyr, H.: Design of energy-efficient application-specific instruction set processors, (2004) · Zbl 1053.68017 |
| [15] | E. Humenay, D. Tarjan, K. Skadron, Impact of process variations on multicore performance symmetry, in: Proceedings of the Conference on Design, Automation and Test in Europe, 2007, pp. 1653–1658. |
| [16] | T. Ishihara, H. Yashura, Voltage scheduling problem for dynamically variable voltage processors, in: International Symposium on Low Power Electronics and Design, 1998, pp. 197–202. |
| [17] | Jensen, J. L. W.V.: Sur LES fonctions convexes et LES inegalites entreles valeurs moyennes, Acta math. 30, No. 1, 175-193 (1906) · JFM 37.0422.02 · doi:10.1007/BF02418571 |
| [18] | Krishna, C. M.; Shin, Kang G.: Real-time systems, (2001) · Zbl 0910.68078 |
| [19] | K. Lakshmanan, R. Rajkumar, J.P. Lehoczky, Partitioned fixed-priority preemptive scheduling for multi-core processors, in: Proceedings of the 21st Euromicro Conference on Real-Time Systems, 2009, pp. 239–148. |
| [20] | Lee, W.; Kim, H.; Lee, H.: Maximum-utility scheduling of operation modes with probabilistic task execution times under energy constraints, IEEE trans. Comput. aided des. Integr. circuits syst. 28, No. 10, 1531 (2009) |
| [21] | J.P. Lehoczky, Fixed priority scheduling of periodic task sets with arbitrary deadline, in: Proceedings of the 11-th IEEE Real-Time System Symposium, 1990, pp. 201–209. |
| [22] | J.Y.T. Leung, J. Whitehead J., On the complexity of fixed-priority scheduling of periodic, Real-time tasks performance evaluation 2 (1982) 237–250. · Zbl 0496.90046 · doi:10.1016/0166-5316(82)90024-4 |
| [23] | Liu, J. W. S.: Real time systems, (2000) |
| [24] | Liu, C. L.; Layland, J. W.: Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM 20, No. 1, 40-61 (1973) · Zbl 0265.68013 · doi:10.1145/321738.321743 |
| [25] | Li, F.; Yao, F. F.: An efficient algorithm for computing optimal discrete voltage schedules, SIAM J. Comput. 35, 658-671 (2005) · Zbl 1122.90041 · doi:10.1137/050629434 |
| [26] | Min-Allah, N.; Ali, I.; Xing, J.; Wang, Y.: Utilization bound for periodic task set with composite deadline, J. comput. Electr. eng. 36, No. 6, 1101-1109 (2010) · Zbl 1210.68039 · doi:10.1016/j.compeleceng.2010.04.003 |
| [27] | Min-Allah, N.; Khan, S. U.: A hybrid test for faster feasibility analysis of periodic tasks, Ijicic 7, No. 10, 5689-5698 (2011) |
| [28] | Min-Allah, N.; Khan, Su; Wang, Y.: Optimal task execution times for periodic tasks using nonlinear constrained optimization, J. supercomput. (2010) |
| [29] | Min-Allah, N.; Wang, Y.; Jian-Sheng, X.; Liu, J.: Revisiting fixed priority techniques, Lncs 4808, 134-145 (2007) |
| [30] | P. Pillai, K.G. Shin, Real-time dynamic voltage scaling for lowpower embedded operating systems, in: Proceedings of the 18th ACM Symposium on Operating Systems Principles, 2001, pp. 21–24. |
| [31] | Raghunathan, V.; Pereira, C.; Srivastava, M.; Gupta, R.: Energy aware wireless systems with adaptive power-fidelity tradeoffs, IEEE trans. Very large scale integr. (VLSI) syst. 13, No. 2 (2005) |
| [32] | S. Saewong, R. Rajkumar, Practical voltage-scaling for fixedpriority rt-systems, in: Proceedings of the 9th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS03, 2003, pp. 106–115. |
| [33] | J. Sartori, A. Pant, R. Kumar, P. Gupta, Variation aware speed binning of multi-core processors, in: Proceedings of the 11-th IEEE International Symposium on Quality Electronic Design, 2010, pp. 307–314. |
| [34] | Seo, E.; Koo, Y.; Lee, J.: Dynamic repartitioning of real-time schedule on a multicore processor for energy efficiency, Lncs 4096/2006, 69-78 (2006) |
| [35] | Xin, H.; Kenli, L.; Renfa, L.: A energy efficient scheduling base on dynamic voltage and frequency scaling for multi-core embedded real-time system, Lncs 5574, 137-145 (2009) |
| [36] | F. Zhang, S. Chanson, Processor voltage scheduling for realtime tasks with non-preemptible sections, in: Real-Time System Symposium, Austin, TX, Dec. 2002. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
