Profile-based optimal intra-task voltage scheduling for hard real-time applications

ABSTRACT

This paper presents a set of comprehensive techniques for the intra-task voltage scheduling problem to reduce energy consumption in hard real-time tasks of embedded systems. Based on the execution profile of the task, a voltage scheduling technique that optimally determines the operating voltages to individual basic blocks in the task is proposed. The obtained voltage schedule guarantees minimum average energy consumption. (The proof of the optimality is included.) The proposed technique is then extended to solve practical issues regarding transition overheads, which are totally or partially ignored in the existing approaches. Finally, a technique involving a novel extension of our optimal scheduler is proposed to solve the scheduling problem in a discretely variable voltage environment. In summary, it is confirmed from experiments that the proposed optimal scheduling technique reduces energy consumption by 20.2 over that of one of the state-of-the-art schedulers citeshin2 and, further, the extended technique in a discrete voltage environment reduces energy consumption by 45.3 on average.

REFERENCES

• 1: 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
• 2: 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]
• 3: Inki Hong , Miodrag Potkonjak , Mani B. Srivastava, On-line scheduling of hard real-time tasks on variable voltage processor, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.653-656, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289105]
• 4: 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]
• 5: 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]
• 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: D. Mosse it et al., "Compiler-Assisted Dynamic Power-Aware Scheduling for Real-Time Applications", COLP, 2000.
• 8: Chung-Hsing Hsu , Ulrich Kremer , Michael Hsiao, Compiler-directed dynamic voltage/frequency scheduling for energy reduction in mircoprocessors, Proceedings of the 2001 international symposium on Low power electronics and design, p.275-278, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383165]
• 9: 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]
• 10: 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]
• 11: Dongkun Shin , Jihong Kim, A profile-based energy-efficient intra-task voltage scheduling algorithm for real-time applications, Proceedings of the 2001 international symposium on Low power electronics and design, p.271-274, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383162]
• 12: A. Azevedo , I. Issenin , R. Cornea , R. Gupta , N. Dutt , A. Veidenbaum , A. Nicolau, Profile-Based Dynamic Voltage Scheduling Using Program Checkpoints, Proceedings of the conference on Design, automation and test in Europe, p.168, March 04-08, 2002
• 13: Thomas D. Burd , Robert W. Brodersen, Processor design for portable systems, Journal of VLSI Signal Processing Systems, v.13 n.2-3, p.203-221, Aug./Sept. 1996 [doi>10.1007/BF01130406]
• 14: Intel Corporation, Enhanced Intel SpeedStep technology, 2003 http://www.intel.com
• 15: Advanced Micro Devices, Inc. AMD PowerNow! technology, 2003 http://www.amd.com
• 16: Transmeta Corporation, Crusoe Processor Specification, 2003 http://www.transmeta.com
• 17: 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]
• 18: Johan Pouwelse , Koen Langendoen , Henk Sips, Dynamic voltage scaling on a low-power microprocessor, Proceedings of the 7th annual international conference on Mobile computing and networking, p.251-259, July 2001, Rome, Italy [doi>10.1145/381677.381701]
• 19: W. H. Press, B. P. Flannery, S. A. Teukolsky and W. T. Vetterling, Numerical Recipes in C, Cambridge University Press, 1988.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
DVS, intra-task voltage scheduling, low energy design