Iterative schedule optimization for voltage scalable distributed embedded systems

ABSTRACT

We present an iterative schedule optimization for multirate system specifications, mapped onto heterogeneous distributed architectures containing dynamic voltage scalable processing elements (DVS-PEs). To achieve a high degree of energy reduction, we formulate a generalized DVS problem, taking into account the power variations among the executing tasks. An efficient heuristic is presented that identifies optimized supply voltages by not only "simply" exploiting slack time, but under the additional consideration of the power profiles. Thereby, this algorithm minimizes the energy dissipation of heterogeneous architectures, including power-managed processing elements, effectively. Further, we address the simultaneous schedule optimization toward timing behavior and DVS utilization by integrating the proposed DVS heuristic into a genetic list scheduling approach. We investigate and analyze the possible energy reduction at both steps of the co-synthesis (voltage scaling and scheduling), including the power variations effects. Extensive experiments indicate that the presented work produces solutions with high quality.

REFERENCES

• 1: 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]
• 2: C. Brandolese , W. Fornaciari , F. Salice , D. Sciuto, Energy estimation for 32-bit microprocessors, Proceedings of the eighth international workshop on Hardware/software codesign, p.24-28, May 2000, San Diego, California, United States [doi>10.1145/334012.334017]
• 3: Burd, T. D. 2001. Energy-efficient processor system design. Ph.D. thesis, University of California at Berkeley.
• 4: 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]
• 5: Burd, T. D., Pering, T. A., Stratakos, A. J., and Brodersen, R. W. 2000. A dynamic voltage scaled microprocessor system. IEEE J. Solid-State Circuits 35, 11 (Nov.), 1571--1580.
• 6: Chretienne, P., Coffman, E. G., Lenstra, J. K., and Liu, Z. 1995. Scheduling Theory and its Applications. Wiley, New York.
• 7: Srinivas Devadas , Sharad Malik, A survey of optimization techniques targeting low power VLSI circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.242-247, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217536]
• 8: Dhodhi, M. K., Ahmad, I., and Storer, R. 1995. SHEMUS: Synthesis of heterogeneous multiprocessor systems. J. Microprocessors and Microsystems 19, 6 (Aug.), 311--319.
• 9: Robert P. Dick , David L. Rhodes , Wayne Wolf, TGFF: task graphs for free, Proceedings of the 6th international workshop on Hardware/software codesign, p.97-101, March 15-18, 1998, Seattle, Washington, United States
• 10: Dick, R. P. and Jha, N. K. 1998. MOGAC: A multiobjective genetic algorithm for hardware-software co-synthesis of distributed embedded systems. IEEE Trans. Computer-Aided Design 17, 10 (Oct.), 920--935.
• 11: Eles, P., Peng, Z., Kuchcinski, K., and Doboli, A. 1997. System level hardware/software partitioning based on simulated annealing and tabu search. J. Design Automation Embedded Systems 2, 5--32.
• 12: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964 ]
• 13: Terence C. Fogarty, Varying the Probability of Mutation in the Genetic Algorithm, Proceedings of the 3rd International Conference on Genetic Algorithms, p.104-109, June 01, 1989
• 14: William Fornaciari , Donatella Sciuto , Christina Silvano, Power estimation for architectural exploration of HW/SW communication on system-level buses, Proceedings of the seventh international workshop on Hardware/software codesign, p.152-156, March 1999, Rome, Italy [doi>10.1145/301177.301516]
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 17: Martin Grajcar, Genetic list scheduling algorithm for scheduling and allocation on a loosely coupled heterogeneous multiprocessor system, Proceedings of the 36th ACM/IEEE conference on Design automation, p.280-285, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309931]
• 18: Flavius Gruian, System-Level Design Methods for Low-Energy Architectures Containing Variable Voltage Processors, Proceedings of the First International Workshop on Power-Aware Computer Systems-Revised Papers, p.1-12, November 12, 2000
• 19: Flavius Gruian , Krzysztof Kuchcinski, LEneS: task scheduling for low-energy systems using variable supply voltage processors, Proceedings of the 2001 conference on Asia South Pacific design automation, p.449-455, January 2001, Yokohama, Japan [doi>10.1145/370155.370511]
• 20: Vadim Gutnik , Anantha P. Chandrakasan, Embedded power supply for low-power DSP, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.4, p.425-435, Dec. 1997 [doi>10.1109/92.645069 ]
• 21: Henkel, J., Benner, T., and Ernst, R. 1993. Hardware generation and partitioning effects in the COSYMA system. In Proceedings of the International Workshop on Hardware/Software Co-Design (Codes/CASHE'93).
• 22: Jörg Henkel , Rolf Ernst, An approach to automated hardware/software partitioning using a flexible granularity that is driven by high-level estimation techniques, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.2, p.273-290, April 2001 [doi>10.1109/92.924041 ]
• 23: Hong, I., Kirovski, D., Qu, G., Potkonjak, M., and Srivastava, M. B. 1999. Power optimization of variable-voltage core-based systems. IEEE Trans. Computer-Aided Design 18, 12 (Dec.), 1702--1714.
• 24: Junwei Hou , Wayne Wolf, Process Partitioning for Distributed Embedded Systems, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.70, March 18-20, 1996
• 25: Intel® XScaleRM. 2000. Developer's Manual. Order number 273473--001.
• 26: 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]
• 27: Asawaree Prabhakar Kalavade , Edward A. Lee, System-level codesign of mixed hardware-software systems, 1995
• 28: Darko Kirovski , Miodrag Potkonjak, System-level synthesis of low-power hard real-time systems, Proceedings of the 34th annual conference on Design automation, p.697-702, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266325]
• 29: Klaiber, A. 2000. The Technology behind crusoe processors. http://www.transmeta.com.
• 30: 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]
• 31: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 32: Jinfeng Liu , Pai H. Chou , Nader Bagherzadeh , Fadi Kurdahi, Power-aware scheduling under timing constraints for mission-critical embedded systems, Proceedings of the 38th conference on Design automation, p.840-845, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379076]
• 33: Jiong Luo , Niraj K. Jha, Power-conscious joint scheduling of periodic task graphs and aperiodic tasks in distributed real-time embedded systems, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 34: Jiong Luo , Niraj K. Jha, Battery-aware static scheduling for distributed real-time embedded systems, Proceedings of the 38th conference on Design automation, p.444-449, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378553]
• 35: Manzak, A. and Chakrabarti, C. 2000. Variable voltage task scheduling for minimizing energy or minimizing power. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing (ICASSP00), 3239--3242.
• 36: Micheli, G. D. and Gupta, R. K. 1997. Hardware/software co-design. In Proceedings of the IEEE, 349--365.
• 37: Mobile AMD AthlonTM4. 2000. Processor model 6 CPGA data sheet. Publication no 24319 Rev E.
• 38: Radu Muresan , Catherine H. Gebotys, Current consumption dynamics at instruction and program level for a VLIW DSP processor, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500032]
• 39: 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
• 40: Takanori Okuma , Hiroto Yasuura , Tohru Ishihara, Software Energy Reduction Techniques for Variable-Voltage Processors, IEEE Design & Test, v.18 n.2, p.31-41, March 2001 [doi>10.1109/54.914613 ]
• 41: Massoud Pedram, Power minimization in IC design: principles and applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.1, p.3-56, Jan. 1996 [doi>10.1145/225871.225877]
• 42: Trevor Pering , Tom Burd , Robert Brodersen, The simulation and evaluation of dynamic voltage scaling algorithms, Proceedings of the 1998 international symposium on Low power electronics and design, p.76-81, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280790]
• 43: Prakash, S. and Parker, A. 1992. SOS: Synthesis of application-specific heterogeneous multiprocessor systems. J. Parallel & Distributed Computing, 338--351.
• 44: 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]
• 45: 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
• 46: Rogers, A. and Prügel-Bennett, A. 1999. Modelling the dynamics of a steady-state genetic algorithm. In Foundations of Genetic Algorithms (FOGA-5). 57--68.
• 47: Schmitz, M. T. 2003. Energy minimization techniques for distributed embedded systems. Ph.D. thesis, University of Southampton.
• 48: 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]
• 49: M. Schmitz , B. Al-Hashimi , P. Eles, Energy-Efficient Mapping and Scheduling for DVS Enabled Distributed Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.514, March 04-08, 2002
• 50: 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]
• 51: 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
• 52: G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593 ]
• 53: Tajana Simunic , Luca Benini , Andrea Acquaviva , Peter Glynn , Giovanni De Micheli, Dynamic voltage scaling and power management for portable systems, Proceedings of the 38th conference on Design automation, p.524-529, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379016]
• 54: J. Teich , T. Blickle , L. Thiele, An evolutionary approach to system-level synthesis, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.167, March 24-26, 1997
• 55: Vivek Tiwari , Sharad Malik , Andrew Wolfe, Power analysis of embedded software: a first step towards software power minimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.437-445, Dec. 1994 [doi>10.1109/92.335012 ]
• 56: Weiser, M., Welch, B., Demers, A., and Shenker, S. 1994. Scheduling for reduced CPU energy. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 13--23.
• 57: WITAS. The Wallenberg Laboratory for research on information technology and autonomous system. http://www.ida.liu.se/ext/witas/.
• 58: Wolf, W. H. 1994. Hardware/software co-design of embedded systems. In Proceedings of the IEEE, 967--989.
• 59: Wayne H. Wolf, An architectural co-synthesis algorithm for distributed, embedded computing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.2, p.218-229, June 1997 [doi>10.1109/92.585225 ]
• 60: M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160 ]
• 61: Y. Xie , W. Wolf, Allocation and scheduling of conditional task graph in hardware/software co-synthesis, Proceedings of the conference on Design, automation and test in Europe, p.620-625, March 2001, Munich, Germany
• 62: Yumin Zhang , Xiaobo Sharon Hu , Danny Z. Chen, Task scheduling and voltage selection for energy minimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513966]

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
Dynamic voltage scaling, embedded systems, energy minimization, heterogeneous distributed systems, scheduling, system synthesis