Optimal voltage allocation techniques for dynamically variable voltage processors

ABSTRACT

This paper presents important, new results of a study on the problem of task scheduling and voltage allocation in dynamically variable voltage processors, the purpose of which was minimization of processor energy consumption. The contributions are twofold: (1) For given multiple discrete supply voltages and tasks with arbitrary arrival-time/deadline constraints, we propose a voltage allocation technique that produces a feasible task schedule with optimal processor energy consumption. (2) We then extend the problem to include the case in which tasks have nonuniform loads (i.e.; switched) capacitances and solve it optimally. The proposed technique, called Alloc-vt, in (1) is based on the prior results in [Yao, Demers and Shenker. 1995. In Proceedings of IEEE Symposium on Foundations of Computer Science. 374--382] (which is optimal for dynamically continuously variable voltages, but not for discrete ones) and [Ishihara and Yasuura. 1998. In Proceedings of International Symposium on Low Power Electronics and Design. 197--202] (which is optimal for a single task, but not for multiple tasks), whereas the proposed technique, called Alloc-vt_cap, in (2) is based on an efficient linear programming (LP) formulation. Both techniques solve the allocation problems optimally in polynomial time.

REFERENCES

• 1: http://www.ilog.com. ILOG, Inc.
• 2: Hakan Aydin , Rami Melhem , Daniel Mossé , Pedro Mejía-Alvarez, Determining Optimal Processor Speeds for Periodic Real-Time Tasks with Different Power Characteristics, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.225, June 13-15, 2001
• 3: Neal K. Bambha , Shuvra S. Bhattacharyya , Jürgen Teich , Eckart Zitzler, Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessors, Proceedings of the ninth international symposium on Hardware/software codesign, p.243-248, April 2001, Copenhagen, Denmark [doi>10.1145/371636.371744]
• 4: Dimitris Bertsimas , John Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997
• 5: Lama H. Chandrasena , Priyadarshana Chandrasena , Michael J. Liebelt, An energy efficient rate selection algorithm for voltage quantized dynamic voltage scaling, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500031]
• 6: Jui-Ming Chang , Massoud Pedram, Energy minimization using multiple supply voltages, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.436-443, Dec. 1997 [doi>10.1109/92.645070]
• 7: Inki Hong , Darko Kirovski , Gang Qu , Miodrag Potkonjak , Mani B. Srivastava, Power optimization of variable voltage core-based systems, Proceedings of the 35th annual conference on Design automation, p.176-181, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277088]
• 8: 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]
• 9: Mark C. Johnson , Kaushik Roy, Datapath scheduling with multiple supply voltages and level converters, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.227-248, July 1997 [doi>10.1145/264995.264997]
• 10: 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]
• 11: Yann-Rue Lin , Cheng-Tsung Hwang , Allen C.-H. Wu, Scheduling techniques for variable voltage low power designs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.2, p.81-97, April 1997 [doi>10.1145/253052.253054]
• 12: Jiong Luo , Niraj K. Jha, Power-profile Driven Variable Voltage Sealing for Heterogeneous Distributed Real-time Embedded Systems, Proceedings of the 16th International Conference on VLSI Design, p.369, January 04-08, 2003
• 13: Ali Manzak , Chaitali Chakrabarti, Variable voltage task scheduling algorithms for minimizing energy/power, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.11 n.2, p.270-276, April 2003 [doi>10.1109/TVLSI.2003.810801]
• 14: 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]
• 15: Gang Quan , Xiaobo Hu, Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors, Proceedings of the 38th conference on Design automation, p.828-833, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379074]
• 16: G. Quan , X. Hu, Minimum Energy Fixed-Priority Scheduling for Variable Voltage Processor, Proceedings of the conference on Design, automation and test in Europe, p.782, March 04-08, 2002
• 17: Salil Raje , Majid Sarrafzadeh, Variable voltage scheduling, Proceedings of the 1995 international symposium on Low power design, p.9-14, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224084]
• 18: Marcus T. Schmitz , Bashir M. Al-Hashimi, Considering power variations of DVS processing elements for energy minimisation in distributed systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500060]
• 19: Li Shang , Li-Shiuan Peh , Niraj K. Jha, Dynamic Voltage Scaling with Links for Power Optimization of Interconnection Networks, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.91, February 08-12, 2003
• 20: 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]
• 21: 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
• 22: Amit Sinha , Anantha P. Chandrakasan, JouleTrack: a web based tool for software energy profiling, Proceedings of the 38th conference on Design automation, p.220-225, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378467]
• 23: Amit Sinha , Anantha P. Chandrakasan, Energy efficient real-time scheduling, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 24: 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:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Design, Performance

Keywords:
Dynamic voltage scaling, low power design, scheduling, variable voltage processor