PERFORMANCE EVALUATION OF META-HEURISTICS IN ENERGY AWARE REAL-TIME SCHEDULING PROBLEMS

(Received: 2015-12-15, Revised: 2016-02-03 , Accepted: 2016-02-10)

Authors Ashraf Suyyagh, Jason G. Tong, Zeljko Zilic,

Keywords #Real-time systems #Embedded systems #Energy-aware scheduling #Meta-heuristics #DVFS #DPM.

Abstract Energy efficient real-time systems have been a prime concern in the past few years. Techniques at all levels of system design are being developed to reduce energy consumption. At the physical level, new fabrication technologies attempt to minimize overall chipset power. At the system design level, technologies such as Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Management (DPM) allow for changing the processor frequency on-the-fly or go into sleep modes to minimize operational power. At the operating system level, energy-efficient scheduling utilizes DVFS and DPM at the task level to achieve further energy savings. Most energy-efficient scheduling research efforts focused on reducing processor power. Recently, system-wide solutions have been investigated. In this work, we extend on the previous work by adapting two evolutionary algorithms for system-wide energy minimization. We analyse the performance of our algorithms under variable initial conditions. We further show that our meta-heuristics statistically provide energy minimizations that are closer to the optimum 85% of the time compared to about 30% of those achieved by simulated annealing over 500 unique test sets. Our results further demonstrate that in over 95% of the cases, meta-heuristics provide more minimizations than the CS-DVS static method.

References

[1] P. Pillai and K. G. Shin, "Real-time Dynamic Voltage Scaling for Low-power Embedded Operating Systems," in Proc. of the 18th ACM Symp. on Operating Systems Principles (SOSP ’01), New York, NY, USA , pp. 89-102, 2001.

[2] S. Saewong and R. Rajkumar, "Practical Voltage-scaling for Fixed-priority RT-Systems," in the 9th IEEE Proc. on Real-Time and Embedded Technology and Applications, pp. 106–114, 2003.

[3] L. Benini et al. "A Survey of Design Techniques for System-level Dynamic Power Management," Proc. in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 8, no. 3, pp. 299–316, 2000.

[4] H. Cheng and S. Goddard, "Online Energy-aware I/O Device Scheduling for Hard Real-time Systems," in Proc. of Design, Automation and Test in Europe (DATE ’06), volume 1, pp. 1055-1060, Munich, 6-10 March 2006.

[5] V. Swaminathan and K. Chakrabarty, "Pruning-based Energy-optimal Device Scheduling for Hard Real-time Systems," in Proc. of the 10th International Symp. on Hardware/Software Co-design (CODES 2002), pp. 175–180, 2002.

[6] V. Devadas and H. Aydin, "On the Interplay of Voltage/frequency Scaling and Device Power Management for Frame-based Real-time Embedded Applications," Proc. of the IEEE Transaction on Comput., vol. 61, no. 1, pp. 31–44, 2012.

[7] R. Jejurikar and R. Gupta, "Dynamic Voltage Scaling for System Wide Energy Minimization in Real-time Embedded Systems," Proc. of the 2004 International Symp. on Low Power Electronics and Design (ISLPED ’04), pp. 78–81, 2004.

[8] W. Wang et al. "System-wide Energy Optimization with DVS and DCR," Proc. of Dynamic Reconfiguration in Real-Time Systems, no. 4, pp. 129–163, Springer, New York, 2013.

[9] F. Kong et al. "Minimizing Multi-resource Energy for Real-time Systems with Discrete Operation Modes," in Proc. of the 22nd Euromicro Conference on Real-Time Systems (ECRTS ’10), Washington, DC, USA, pp. 113–122, 2010.

[10] D. He and W. Mueller, "Online Energy-efficient Hard Real-time Scheduling for Component Oriented Systems," Proc.of the IEEE 15th International Symp. on Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC), pp. 56–63, 2012.

[11] V. Devadas and H. Aydin, "DFR-EDF: A Unified Energy Management Framework for Real-time Systems," Proc. of the 16th IEEE Real-Time and Embedded Technology and Applications Symp. (RTAS), pp. 121– 130, 2010.

[12] L. Niu, "System-level Energy-efficient Scheduling for Hard Real-time Embedded Systems," in Design, Automation Test in Europe Conference Exhibition (DATE), pp. 1–4, 2011.

[13] B. A. Mahafzah and B. A. Jaradat, "The Hybrid Dynamic Parallel Scheduling Algorithm for Load Balancing on Chained-cubic Tree Interconnection Networks," in Journal of Supercomputing, vol. 52, no. 3, pp.224– 252, 2010.

[14] J. Zhao and H. Qiu, "Genetic Algorithm and Ant Colony Algorithm Based Energy-efficient Task Scheduling," in International Conference on Inform. Science and Technology (ICIST), pp. 946– 950, 2013.

[15] S. G. Ahmad et al. "PEGA: A Performance Effective Genetic Algorithm for Task Scheduling in Heterogeneous Systems," in IEEE 14th Intl. Conference on High Performance Computing and Commun. IEEE 9th Intl. Conference on Embedded Software and Systems (HPCC-ICESS), pp. 1082–1087, 2012.

[16] M. A Alshraideh et al. "Using Genetic Algorithm as Test Data Generator for Stored pl/sql Program Units," in Journal of Software Eng. and Applicat, vol. 6, no. 2, p. 65, 2013.

[17] D. Simon, Evolutionary Optimization Algorithms, Wiley, 2013.

[18] G. Chen et al. "Effective Online Power Management with Adaptive Interplay of DVS and DPM for Embedded Real-time System," in Euromicro Conference on Digital System Design (DSD), pp. 881–889, 2013.

[19] J. Xu, "A Method for Adjusting the Periods of Periodic Processes to Reduce the Least Common Multiple of the Period Lengths in Real-time Embedded Systems," in IEEE/ASME Intl. Conference on Mechatronics and Embedded Syst. and Applicat. (MESA), pp. 288–294, 2010.

[20] R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms, Wiley InterScience Electronic Collection, Wiley, 2004.

[21] R. Jejurikar and R. Gupta, "Optimized Slowdown in Real-time Task Systems," Proc. in IEEE Computer Trans., vol. 55, no. 12, pp. 1588–1598, 2006.

[22] B. A. Mahafzah and B. A. Jaradat, "The Load Balancing Problem in OTIS-Hypercube Interconnection Networks," in Journal of Supercomputing, vol. 46, no. 3, pp. 276-297, 2008.

[23] V. Devadas and H. Aydin, "On the Interplay of Voltage/Frequency Scaling and Device Power Management for Frame-Based Real-Time Embedded Applications," Proc. in IEEE Transactions on Computers, vol. 61, no. 1, pp. 31–44, 2012.