Minimizing CPU energy in real-time systems with discrete speed management

ABSTRACT

This article presents a general framework to analyze and design embedded systems minimizing the energy consumption without violating timing requirements. A set of realistic assumptions is considered in the model in order to apply the results in practical real-time applications. The processor is assumed to have as a set of discrete operating modes, each characterized by speed and power consumption. The energy overhead and the transition delay incurred during mode switches are considered. Task computation times are modeled with a part that scales with the speed and a part having a fixed duration, to take I/O operations into account.

The proposed method allows to compute the optimal sequence of voltage/speed changes that approximates the minimum continuous speed, which guarantees the feasibility of a given set of real-time tasks, without violating the deadline constraints. The analysis is performed both under fixed and dynamic priority assignments.

REFERENCES

• 1: Nevine AbouGhazaleh , Daniel Mossé , Bruce Childers , Rami Melhem, Toward the placement of power management points in real-time applications, Compilers and operating systems for low power, Kluwer Academic Publishers, Norwell, MA, 2003
• 2: Almeida, L., Pedreiras, P., and Fonseca, J. A. G. 2002. The FTT-CAN protocol: Why and how. IEEE Trans. Ind. Electron. 49, 6, 1189--1201.
• 3: Hakan Aydin , Vinay Devadas , Dakai Zhu, System-Level Energy Management for Periodic Real-Time Tasks, Proceedings of the 27th IEEE International Real-Time Systems Symposium, p.313-322, December 05-08, 2006 [doi>10.1109/RTSS.2006.48]
• 4: 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]
• 5: Sanjoy K. Baruah , Louis E. Rosier , R. R. Howell, Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor, Real-Time Systems, v.2 n.4, p.301-324, Nov. 1990 [doi>10.1007/BF01995675]
• 6: Bini, E. 2004. The design domain of real-time system. Ph.D. Thesis, Scuola Superiore Sant'Anna, Pisa, Italy. http://retis.sssup.it/~bini/thesis/
• 7: Enrico Bini , Giorgio Buttazzo , Giuseppe Lipari, Speed Modulation in Energy-Aware Real-Time Systems, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.3-10, July 06-08, 2005 [doi>10.1109/ECRTS.2005.29]
• 8: Giorgio C. Buttazzo, Hard Real-time Computing Systems: Predictable Scheduling Algorithms And Applications (Real-Time Systems Series), Springer-Verlag TELOS, Santa Clara, CA, 2004
• 9: Anantha P. Chandrakasan , Robert W. Brodersen, Low Power Digital CMOS Design, Kluwer Academic Publishers, Norwell, MA, 1995
• 10: Xiang (Alex) Feng , Aloysius K. Mok, A Model of Hierarchical Real-Time Virtual Resources, Proceedings of the 23rd IEEE Real-Time Systems Symposium, p.26, December 03-05, 2002
• 11: Gresser, K. 1993. An event model for deadline verification of hard real-time systems. In Proceedings of the 5th Euromicro Workshop on Real-Time Systems. IEEE, Los Alamitos, CA, 118--123.
• 12: I. Hong , G. Qu , M. Potkonjak , M. B. Srivastava, Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors, Proceedings of the IEEE Real-Time Systems Symposium, p.178, December 02-04, 1998
• 13: Sandy Irani , Sandeep Shukla , Rajesh Gupta, Algorithms for power savings, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 14: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 15: Ravindra Jejurikar , Rajesh Gupta, Dynamic voltage scaling for systemwide energy minimization in real-time embedded systems, Proceedings of the 2004 international symposium on Low power electronics and design, August 09-11, 2004, Newport Beach, California, USA [doi>10.1145/1013235.1013261]
• 16: Seongsoo Lee , Takayasu Sakurai, Run-time voltage hopping for low-power real-time systems, Proceedings of the 37th Annual Design Automation Conference, p.806-809, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337785]
• 17: Lehoczky, J. P., Sha, L., and Ding, Y. 1989. The rate-monotonic scheduling algorithm: Exact characterization and average case behavior. In Proceedings of the 10th IEEE Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 166--171.
• 18: Lipari, G. and Bini, E. 2003. Resource partitioning among real-time applications. In Proceedings of the 15th Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 151--158.
• 19: 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]
• 20: Yanbin Liu , Aloysius K. Mok, An Integrated Approach for Applying Dynamic Voltage Scaling to Hard Real-Time Systems, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.116, May 27-30, 2003
• 21: Bren Mochocki , Xiaobo Sharon Hu , Gang Quan, A realistic variable voltage scheduling model for real-time applications, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.726-731, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774679]
• 22: 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
• 23: Ala' Qadi , Steve Goddard , Shane Farritor, A Dynamic Voltage Scaling Algorithm for Sporadic Tasks, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.52, December 03-05, 2003
• 24: Gang Quan , Linwei Niu , Xiaobo Sharon Hu , Bren Mochocki, Fixed Priority Scheduling for Reducing Overall Energy on Variable Voltage Processors, Proceedings of the 25th IEEE International Real-Time Systems Symposium, p.309-318, December 05-08, 2004 [doi>10.1109/REAL.2004.23]
• 25: Jan M. Rabaey, Digital integrated circuits: a design perspective, Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 26: K. Richter , R. Ernst, Event Model Interfaces for Heterogeneous System Analysis, Proceedings of the conference on Design, automation and test in Europe, p.506, March 04-08, 2002
• 27: Ismael Ripoll , Alfons Crespo , Aloysius K. Mok, Improvement in feasibility testing for real-time tasks, Real-Time Systems, v.11 n.1, p.19-39, July 1996 [doi>10.1007/BF00365519]
• 28: Saowanee Saewong , Ragunathan (Raj) Rajkumar, Practical Voltage-Scaling for Fixed-Priority RT-Systems, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.106, May 27-30, 2003
• 29: Claudio Scordino , Giuseppe Lipari, A Resource Reservation Algorithm for Power-Aware Scheduling of Periodic and Aperiodic Real-Time Tasks, IEEE Transactions on Computers, v.55 n.12, p.1509-1522, December 2006 [doi>10.1109/TC.2006.190]
• 30: Kiran Seth , Aravindh Anantaraman , Frank Mueller , Eric Rotenberg, FAST: Frequency-Aware Static Timing Analysis, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.40, December 03-05, 2003
• 31: Insik Shin , Insup Lee, Periodic Resource Model for Compositional Real-Time Guarantees, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.2, December 03-05, 2003
• 32: Tal, J. and Person, E. K. 1978. Pulsewidth modulated amplifier for dc servo system. DC motor and control systems. http://icat.snu.ac.kr:3333/ww/pdf/ww_1993_30.pdf.
• 33: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.374, October 23-25, 1995
• 34: Jianli Zhuo , Chaitali Chakrabarti, System-level energy-efficient dynamic task scheduling, Proceedings of the 42nd annual Design Automation Conference, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065744]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Real time

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
CPU energy, Real-time systems