Low-energy intra-task voltage scheduling using static timing analysis

ABSTRACT

We propose an intra-task voltage scheduling algorithm for low-energy hard real-time applications. Based on a static timing analysis technique, the proposed algorithm controls the supply voltage within an individual task boundary. By fully exploiting all the slack times, a scheduled program by the proposed algorithm always complete its execution near the deadline, thus achieving a high energy reduction ratio. In order to validate the effectiveness of the proposed algorithm, we built a software tool that automatically converts a DVS-unaware program into an equivalent low-energy program. Experimental results show that the low-energy version of an MPEG-4 encoder/decoder (converted by the software tool) consumes less than 7$\sim$25% of the original program running on a fixed-voltage system with a power-down mode.

REFERENCES

• 1: T. Burd, T. Pering, A. Stratakos, and R. Brodersen. A dynamic voltage scaled microprocessor system. In Proc. of IEEE International Solid-State Circuits Conference, pages 294-295, 2000.
• 2: M. Fleischmann. Crusoe power management: reducing the operating power with LongRun. In Proc. of HotChips 12 Symposium, 2000.
• 3: C. A. Healy , D. B. Whalley , M. G. Harmon, Integrating the timing analysis of pipelining and instruction caching, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.288, December 05-07, 1995
• 4: 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
• 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: Seongsoo Lee , Takayasu Sakurai, Run-time voltage hopping for low-power real-time systems, Proceedings of the 37th conference on Design automation, p.806-809, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337785]
• 7: Yann-Hang Lee , C. M. Krishna, Voltage-Clock Scaling for Low Energy Consumption in Real-Time Embedded Systems, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.272, December 13-15, 1999
• 8: Sung-Soo Lim , Young Hyun Bae , Gyu Tae Jang , Byung-Do Rhee , Sang Lyul Min , Chang Yun Park , Heonshik Shin , Kunsoo Park , Soo-Mook Moon , Chong Sang Kim, An Accurate Worst Case Timing Analysis for RISC Processors, IEEE Transactions on Software Engineering, v.21 n.7, p.593-604, July 1995 [doi>10.1109/32.392980]
• 9: Takanori Okuma , Tohru Ishihara , Hiroto Yasuura, Real-Time Task Scheduling for a Variable Voltage Processor, Proceedings of the 12th international symposium on System synthesis, p.24, November 01-04, 1999
• 10: T. Sakurai and A. Newton. Alpha-power law MOSFET model and its application to CMOS inverter delay and other formulas. IEEE Journal of Solid State Circuits, 25(2):584-594, 1990.
• 11: Youngsoo Shin , Kiyoung Choi, Power conscious fixed priority scheduling for hard real-time systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.134-139, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309901]
• 12: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
  B.8 Performance and Reliability

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory