Feedback EDF scheduling exploiting hardware-assisted asynchronous dynamic voltage scaling

ABSTRACT

Recent processor support for dynamic frequency and voltage scaling (DVS) allows software to affect power consumption by varying execution frequency and supply voltage on the fly. However, processors generally enter a sleep state while transitioning between frequencies/voltages. In this paper, we examine the merits of hardware/software co-design for a feedback DVS algorithm and a novel processor capable of executing instructions during frequency/voltage transitions. We study several power-aware feedback schemes based on earliest-deadline-first (EDF) scheduling that adjust the system behavior dynamically for different workload characteristics. An infrastructure for investigating several hard real-time DVS schemes, including our feedback DVS algorithm, is implemented on an IBM PowerPC 405LP embedded board. Architecture and algorithm overhead is assessed for different DVS schemes. Measurements on the experimentation board provide a quantitative assessment of the potential of energy savings for DVS algorithms as opposed to prior simulation work that could only provide trends. Energy consumption, measured through a data acquisition board, indicates a considerable potential for real-time DVS scheduling algorithms to lower energy up to 64% over the naïve DVS scheme. Our feedback DVS algorithm saves at least as much and often considerably more energy than previous DVS algorithms with peak savings of an additional 24% energy reduction. To the best of our knowledge, this is the first comparative study of real-time DVS algorithms on a concrete micro-architecture and the first evaluation of asynchronous DVS switching.

REFERENCES

• 1: Hakan Aydin , Rami Melhem , Daniel Mossé , Pedro Mejía-Alvarez, Power-Aware Scheduling for Periodic Real-Time Tasks, IEEE Transactions on Computers, v.53 n.5, p.584-600, May 2004 [doi>10.1109/TC.2004.1275298]
• 2: Energy - Responsiveness Tradeoffs for Real-Time Systems with Mixed Workload, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), p.74, May 25-28, 2004
• 3: B. Brock and K. Rajamani. Dynamic power management for embedded systems. In IEEE International SOC Conference, Sept. 2003.
• 4: A. Chandrakasan, S. Sheng, and R. W. Brodersen. Low-power cmos digital design. In IEEE Journal of Solid-State Circuits, Vol. 27, pp. 473--484., April, 1992.
• 5: Ajay Dudani , Frank Mueller , Yifan Zhu, Energy-conserving feedback EDF scheduling for embedded systems with real-time constraints, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 6: Kinshuk Govil , Edwin Chan , Hal Wasserman, Comparing algorithm for dynamic speed-setting of a low-power CPU, Proceedings of the 1st annual international conference on Mobile computing and networking, p.13-25, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215546]
• 7: Flavius Gruian, Hard real-time scheduling for low-energy using stochastic data and DVS processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.46-51, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383092]
• 8: D. Grunwald, P. Levis, C. M. III, M. Neufeld, and K. Farkas. Policies for dynamic clock scheduling. In Symp. on Operating Systems Design and Implementation, Oct 2000.
• 9: IBM and MontaVisa Software. Dynamic power management for embedded systems. white paper.
• 10: R. Jejurikar and R. Gupta. Integrating preemption threshold scheduling and dynamic voltage scaling for energy efficient real-time systems. In Proceedings of the 10th International Conference on Real-Time and Embedded Computing Systems and Applications (RTCSA '04), 25--27 Aug 2004.
• 11: Ravindra Jejurikar , Rajesh Gupta, Optimized Slowdown in Real-Time Task Systems, Proceedings of the 16th Euromicro Conference on Real-Time Systems (ECRTS'04), p.155-164, June 30-July 02, 2004 [doi>10.1109/ECRTS.2004.22]
• 12: Ravindra Jejurikar , Rajesh Gupta, Procrastination scheduling in fixed priority real-time systems, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 13: Dong- In Kang , Stephen P. Crago , Jinwoo Suh, A Fast Resource Synthesis Technique for Energy-Efficient Real-Time Systems, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.225, December 03-05, 2002
• 14: C. Lu, J. A. Stankovic, T. F. Abdelzaher, G. Tao, S. H. Son, and M. Marley. Performance specifications and metrics for adaptive real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, December 2000. 2000.
• 15: Chenyang Lu , John A. Stankovic , Sang H. Son , Gang Tao, Feedback Control Real-Time Scheduling: Framework, Modeling, and Algorithms*, Real-Time Systems, v.23 n.1-2, p.85-126, July-September 2002 [doi>10.1023/A:1015398403337]
• 16: Zhijian Lu , Jason Hein , Marty Humphrey , Mircea Stan , John Lach , Kevin Skadron, Control-theoretic dynamic frequency and voltage scaling for multimedia workloads, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581654]
• 17: R. Minerick, V. W. Freeh, and P. M. Kogge. Dynamic power management using feedback. In Proceedings of Workshop on Compilers and Operating Systems for Low Power, 2002.
• 18: K. J. Nowka , G. D. Carpenter , B. C. Brock, The design and application of the PowerPC 405LP energy-efficient system-on-a-chip, IBM Journal of Research and Development, v.47 n.5-6, p.631-639, September 2003
• 19: T. Pering, T. Burd, and R. Brodersen. The simulation of dynamic voltage scaling algorithms. In Symp. on Low Power Electronics, 1995.
• 20: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 21: D. Shin, W. Kim, J. Jeon, J. Kim, and S. L. Min. Simdvs: An integrated simulation environment for performance evaluation of dynamic voltage scaling algorithms. In Workshop on Power-Aware Computer Systems, Feb. 2002.
• 22: J. A. Stankovic, C. Lu, S. H. Son, and G. Tao. The case for feedback control real-time scheduling. In Proceedings of the EuroMicro Conference on Real-Time Systems, June 1999.
• 23: Ankush Varma , Brinda Ganesh , Mainak Sen , Suchismita Roy Choudhury , Lakshmi Srinivasan , Jacob Bruce, A control-theoretic approach to dynamic voltage scheduling, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951744]
• 24: M. Weiser, B. Welch, A. Demers, and S. Shenker. Scheduling for reduced cpu energy. In 1st Symp. on Operating Systems Design and Implementation, Nov 1994.
• 25: Feedback EDF Scheduling Exploiting Dynamic Voltage Scaling, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'04), p.84, May 25-28, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Experimentation

Keywords:
dynamic voltage scaling, feedback control, real-time systems, scheduling