Expected energy consumption minimization in DVS systems with discrete frequencies

ABSTRACT

Energy-efficiency has been an important system issue in hardware and software designs to extend operation duration or out power bils. This research explores systems with probabilistic distribution on the execution time of real-time tasks for systems with discrete frequencies. Most previous studies consider DVS systems with continuous frequencies for the minimization of expected energy consumption under timing constraints. However, these approaches cannot guarantee the minimization of expected energy consumption when only discrete frequencies are available. This paper presents new approaches to minimize the expected energy consumption. By applying intra-task frequency scheduling, we develop an efficient algorithm to derive optimal frequency scheduling for a single task. The algorithm is then extended to cope with periodic real-time tasks with different power characteristics. With inter-task and intra-task frequency scheduling, we present a linear-programming approach to derive optimal solutions for frame-based real-time tasks and an on-line algorithm for periodic real-time tasks. Experimental results show that the proposed algorithms can effectively reduce the expected energy consumption.

REFERENCES

• 1: Hakan Aydi , Pedro Mejía-Alvarez , Daniel Mossé , Rami Melhem, Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems, Proceedings of the 22nd IEEE Real-Time Systems Symposium (RTSS'01), p.95, December 03-06, 2001
• 2: Jian-Jia Chen , Chin-Fu Kuo, Energy-Efficient Scheduling for Real-Time Systems on Dynamic Voltage Scaling (DVS) Platforms, Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.28-38, August 21-24, 2007 [doi>10.1109/RTCSA.2007.37]
• 3: 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]
• 4: Flavius Gruian , Krzysztof Kuchcinski, Uncertainty-based scheduling: energy-efficient ordering for tasks with variable execution time, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871621]
• 5: 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]
• 6: Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775867]
• 7: PACE: A New Approach to Dynamic Voltage Scaling, IEEE Transactions on Computers, v.53 n.7, p.856-869, July 2004 [doi>10.1109/TC.2004.35]
• 8: Zhijian Lu , Yan Zhang , Mircea Stan , John Lach , Kevin Skadron, Procrastinating voltage scheduling with discrete frequency sets, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 9: 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
• 10: Changjiu Xian , Yung-Hsiang Lu, Dynamic voltage scaling for multitasking real-time systems with uncertain execution time, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA [doi>10.1145/1127908.1127998]
• 11: 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]
• 12: 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
• 13: 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, Anaheim, California, USA [doi>10.1145/1065579.1065816]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.8 Performance
          Subjects: Operational analysis

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Design, Performance

Keywords:
dynamic voltage scaling, energy-efficient scheduling, expected energy consumption minimization, probability