Dynamic voltage scaling for multitasking real-time systems with uncertain execution time

ABSTRACT

Dynamic voltage scaling (DVS) for real-time systems has been extensively studied to save energy. Previous studies consider the probabilistic distributions of tasks' execution time to assist DVS in task scheduling. These studies use probability information for intra-task frequency scheduling but do not sufficiently explore the opportunities for inter-task scheduling to save more energy. This paper presents a new approach to integrate intra-task and inter-task frequency scheduling for better energy savings in hard real-time systems with uncertain task execution time. Our approach has two steps: (a) We calculate statistically optimal frequency schedules for multiple periodic tasks using earliest deadline first (EDF) scheduling for processors that can change frequencies continuously. (b) For processors with a limited range of discrete frequencies, we further present a heuristic algorithm to construct frequency schedules. Our evaluation shows that our approach saves up to 23% more energy than existing solutions.

REFERENCES

• 1: Giorgio C. Buttazzo , Giorgio Buttanzo, Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 2: 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]
• 3: Intel XScale Microarchitecture. (http://developer.intel.com/design/xscale).
• 4: 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]
• 5: J. L. W. V. Jensen. Sur Les Fonctions Convexes Et Les Inegalites Entre Les Valeurs Moyennes. Acta Math, 30:175--193, 1906.
• 6: 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]
• 7: J. R. Lorch and A. J. Smith. Improving Dynamic Voltage Scaling Algorithms with PACE. In the 2001 ACM SIGMETRICS, pages 50--61, June 2001.
• 8: 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
• 9: Ruibin Xu , Daniel Mossé , Rami Melhem, Minimizing expected energy in real-time embedded systems, Proceedings of the 5th ACM international conference on Embedded software, September 18-22, 2005, Jersey City, NJ, USA [doi>10.1145/1086228.1086274]
• 10: Ruibin Xu , Chenhai Xi , Rami Melhem , Daniel Moss, Practical PACE for embedded systems, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017767]
• 11: Wanghong Yuan , Klara Nahrstedt, Energy-efficient soft real-time CPU scheduling for mobile multimedia systems, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 12: Yan Zhang , Zhijian Lu , John Lach , Kevin Skadron , Mircea R. Stan, Optimal procrastinating voltage scheduling for hard real-time systems, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065816]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Algorithms, Design, Performance

Keywords:
dynamic voltage scaling, hard real-time, low energy, multitasking, probability