Real-time dynamic voltage scaling for low-power embedded operating systems

ABSTRACT

In recent years, there has been a rapid and wide spread of non-traditional computing platforms, especially mobile and portable computing devices. As applications become increasingly sophisticated and processing power increases, the most serious limitation on these devices is the available battery life. Dynamic Voltage Scaling (DVS) has been a key technique in exploiting the hardware characteristics of processors to reduce energy dissipation by lowering the supply voltage and operating frequency. The DVS algorithms are shown to be able to make dramatic energy savings while providing the necessary peak computation power in general-purpose systems. However, for a large class of applications in embedded real-time systems like cellular phones and camcorders, the variable operating frequency interferes with their deadline guarantee mechanisms, and DVS in this context, despite its growing importance, is largely overlooked/under-developed. To provide real-time guarantees, DVS must consider deadlines and periodicity of real-time tasks, requiring integration with the real-time scheduler. In this paper, we present a class of novel algorithms called real-time DVS (RT-DVS) that modify the OS's real-time scheduler and task management service to provide significant energy savings while maintaining real-time deadline guarantees. We show through simulations and a working prototype implementation that these RT-DVS algorithms closely approach the theoretical lower bound on energy consumption, and can easily reduce energy consumption 20% to 40% in an embedded real-time system.

REFERENCES

• 1: ADVANCED MICRO DEVICES CORPORATION. Mobile AMD-K6-2 + Processor Data Sheet, June 2000. Publication # 23446.
• 2: T. D. Burd , R. W. Brodersen, Energy efficient CMOS microprocessor design, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS'95), p.288, January 04-07, 1995
• 3: Carla Schlatter Ellis, The Case for Higher-Level Power Management, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.162, March 28-30, 1999
• 4: Krisztián Flautner , Steve Reinhardt , Trevor Mudge, Automatic performance setting for dynamic voltage scaling, Proceedings of the 7th annual international conference on Mobile computing and networking, p.260-271, July 2001, Rome, Italy [doi>10.1145/381677.381702]
• 5: Jason Flinn , M. Satyanarayanan, Energy-aware adaptation for mobile applications, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.48-63, December 12-15, 1999, Charleston, South Carolina, United States
• 6: Jason Flinn , M. Satyanarayanan, PowerScope: A Tool for Profiling the Energy Usage of Mobile Applications, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.2, February 25-26, 1999
• 7: 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]
• 8: 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]
• 9: INTEL CORPORATION. http://developer.intel.com/design/intelxscal/.
• 10: INTEL CORPORATION. Mobile lntel Pentium lll Processor in BGA2 and MicroPGA2 Packages, 2000. Order Number 245483-003.
• 11: Robin Kravets , P. Krishnan, Power management techniques for mobile communication, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.157-168, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288276]
• 12: C. M. Krishna , Yann-Hang Lee, Voltage-Clock-Scaling Adaptive Scheduling Techniques for Low Power in Hard Real-Time Systems, Proceedings of the Sixth IEEE Real Time Technology and Applications Symposium (RTAS 2000), p.156, May 31-June 02, 2000
• 13: C.M. M. Krishna , C. M. Krishna, Real-Time Systems, McGraw-Hill Higher Education, 1996
• 14: LEHOCZKY, J., SHA, L., AND DING, Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In Proceedings of the IEEE Real-Time Systems Symposium (1989), pp. 166-171.
• 15: LEHOCZKY, J., AND THUEL, S. Algorithms for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing. In Proceedings of the IEEE Real-Time Systems Symposium (1994).
• 16: LEHOCZKY, J. P., SHA, L., AND STROSNIDER, J. K. Enhanced aperiodic responsiveness in hard real-time environments. In Proc. of the 8th IEEE Real-Time Systems Symposium (Los Alamitos, CA, Dec. 1987), pp. 261-270.
• 17: LEUNO, J. Y.-T., AND WHITEHEAD, J. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation 2, 4 (Dec. 1982), 237-250.
• 18: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 19: Jacob R. Lorch , Alan Jay Smith, Improving dynamic voltage scaling algorithms with PACE, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.50-61, June 2001, Cambridge, Massachusetts, United States
• 20: Jacob R. Lorch , Alan Jay Smith, Apple Macintosh's Energy Consumption, IEEE Micro, v.18 n.6, p.54-63, November 1998 [doi>10.1109/40.743684]
• 21: MOSSE, D., AYDIN, H., CHILDERS, B., AND MELHEM, R. Compiler-assisted dynamic power-aware scheduling for real-time applications. In Workshop on Compilers and Operating Systems for Low-Power (COLP'O0) (Philadelphia, PA, Oct. 2000).
• 22: PERING, T., AND BRODERSEN, R. Energy efficient voltage scheduling for real-time operating systems. In Proceedings of the 4th IEEE Real-Time Technology and Applications Symposium RTAS'98, Work in Progress Session (Denver, CO, June 1998).
• 23: Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
• 24: Trevor Pering , Thomas Burd , Robert Brodersen, Voltage scheduling in the IpARM microprocessor system, Proceedings of the 2000 international symposium on Low power electronics and design, p.96-101, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344530]
• 25: Johan Pouwelse , Koen Langendoen , Henk Sips, Dynamic voltage scaling on a low-power microprocessor, Proceedings of the 7th annual international conference on Mobile computing and networking, p.251-259, July 2001, Rome, Italy [doi>10.1145/381677.381701]
• 26: Johan Pouwelse , Koen Langendoen , Henk Sips, Energy priority scheduling for variable voltage processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.28-33, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383089]
• 27: John A. Stankovic , Krithi Ramamritham , Marco Spuri, Deadline Scheduling for Real-Time Systems: Edf and Related Algorithms, Kluwer Academic Publishers, Norwell, MA, 1998
• 28: SWAMINATHAN, V., AND CHAKRABARTY, K. Real-time task scheduling for energy-aware embedded systems. In Proceedings of the IEEE Real-Time Systems Syrup. (Work-in-Progress Session) (Orlando, FL, Nov. 2000).
• 29: TRANSMETA CORPORATION. http://www.transmeta.com/.
• 30: WEISER, M., WELCH, B., DEMERS, m., AND SHENKER, S. Scheduling for reduced CPU energy. In Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI) (Monterey, CA, Nov. 1994), pp. 13-23.
• 31: Khawar M. Zuberi , Padmanabhan Pillai , Kang G. Shin, EMERALDS: a small-memory real-time microkernel, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.277-299, December 12-15, 1999, Charleston, South Carolina, United States

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
      D.4.8 Performance
          Subjects: Simulation

General Terms:
Algorithms, Measurement, Performance