A deferred-workload-based inter-task dynamic voltage scaling algorithm for portable multimedia devices

ABSTRACT

In this paper, we propose a deferred-workload-based inter-task DVS (dynamic voltage scaling) algorithm (dwDVS), which has two features, for portable multimedia devices. The first is that we reserve a time interval for each task to execute and its workload can be completed in this time interval even in the worst-case condition, which means that the actual workload (execution time) of each task is equal to its worst-case execution time. In this way, we can estimate the slack time from lower priority tasks more aggressively. The second is that we defer these reserved time intervals, which means that a reserved time interval will be shifted to the deadline of its corresponding task as close as possible. Thus, the operating frequency can be reduced even without slack time. Simulation results show that the proposed dwDVS reduces the energy consumption by 40-70%, 10-20%, and 3-10% compared with the static voltage scaling (Static), laEDF, and DRA algorithms, respectively, and approaches theoretical low bound (Bound) by a margin of at most 12%.

REFERENCES

• 1: 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
• 2: 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]
• 3: B. Moyer, "Low-Power Design for Embedded Processors," in Proceedings of IEEE, Volume 89, Issue 11, pp. 1576--1587, November 2001.
• 4: Intel, PXA255 Processor Electrical, Mechanical, and Thermal Specification, 2004.
• 5: Intel, PXA270 Processor Electrical, Mechanical, and Thermal Specification, 2004.
• 6: Transmeta Corporation, http://www.transmeta.com/
• 7: Woonseok Kim , Dongkun Shin , Han-Saem Yun , Jihong Kim , Sang Lyul Min, Performance Comparison of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems, Proceedings of the Eighth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'02), p.219, September 25-27, 2002
• 8: W. Kim , J. Kim , S. Min, A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real-Time Systems Using Slack Time Analysis, Proceedings of the conference on Design, automation and test in Europe, p.788, March 04-08, 2002
• 9: C. M. Krishna , Yann-Hang Lee, Voltage-Clock-Scaling Adaptive Scheduling Techniques for Low Power in Hard Real-Time Systems, IEEE Transactions on Computers, v.52 n.12, p.1586-1593, December 2003 [doi>10.1109/TC.2003.1252854]
• 10: Youngsoo Shin , Kiyoung Choi , Takayasu Sakurai, Power optimization of real-time embedded systems on variable speed processors, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 11: Venkat Rao , Gaurav Singhal , Anshul Kumar, Real Time Dynamic Voltage Scaling For Embedded Systems, Proceedings of the 17th International Conference on VLSI Design, p.650, January 05-09, 2004
• 12: 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]
• 13: Dongkun Shin , Jihong Kim , Seongsoo Lee, Intra-Task Voltage Scheduling for Low-Energy, Hard Real-Time Applications, IEEE Design & Test, v.18 n.2, p.20-30, March 2001 [doi>10.1109/54.914596]
• 14: 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]
• 15: Taewhan Kim, Application-Driven Low-Power Techniques Using Dynamic Voltage Scaling, Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, p.199-206, August 16-18, 2006 [doi>10.1109/RTCSA.2006.16]
• 16: J. Lehoczkym L. Sha, and Y. Ding, "The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior," in Proceedings of the IEEE Real-Time Systems Symposium, pp. 166--171, December 1989.
• 17: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms

Keywords:
actual workload, deferred-workload-based, hard real-time system, inter-task dynamic voltage scaling, slack time, worst-case execution time