HEURISTICS IN ENERGY AWARE REAL-TIME SCHEDULING PROBLEMS

(Received: 2015-12-15, Revised: 2016-02-03 , Accepted: 2016-02-10)
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.
  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