Hybrid global/local search strategies for dynamic voltage scaling in embedded multiprocessors

ABSTRACT

In this paper, we explore a hybrid global/local search optimization framework for dynamic voltage scaling in embedded multiprocessor systems. The problem is to find, for a multiprocessor system in which the processors are capable of dynamically varying their core voltages, the optimum voltage levels for all the tasks in order to minimize the average power consumption under a given performance constraint. An effective local search approach for static voltage scaling based on the concept of a period graph has been demonstrated in [1]. To make use of it in an optimization problem, the period graph must be integrated into a global search algorithm. Simulated heating, a general optimization framework developed in [19], is an efficient method for precisely this purpose of integrating local search into global search algorithms. However, little is known about the management of computational (compile-time) resources between global search and local search in hybrid algorithms, such as those coordinated by simulated heating. In this paper, we explore various hybrid search management strategies for power optimization under the framework of simulated heating. We demonstrate that careful search management leads to significant power consumption improvement over add-hoc global search / local search integration, and explore alternative approaches to performing hybrid search management for dynamic voltage scaling.

REFERENCES

• 1: Neal K. Bambha , Shuvra S. Bhattacharyya, A joint power/performance optimization algorithm for multiprocessor systems using a period graph construct, Proceedings of the 13th international symposium on System synthesis, September 20-22, 2000, Madrid, Spain [doi>10.1145/501790.501812]
• 2: Thomas D. Burd , Robert W. Brodersen, Design issues for dynamic voltage scaling, Proceedings of the 2000 international symposium on Low power electronics and design, p.9-14, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344181]
• 3: A. P. Chandrakasan, S. Sheng, and R. W. Brodersen. Low-power CMOS digital design. 1EEE Journal of Solid State Circuits, 27(4):473-484, 1992.
• 4: Jui-Ming Chang , Massoud Pedram, Register allocation and binding for low power, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.29-35, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217502]
• 5: A. Dasdan and 1L K. Gupta. Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and @stems, 17(10):889-899, October 1998.
• 6: Aurobindo Dasgupta , Ramesh Karri, Simultaneous scheduling and binding for power minimization during microarchitecture synthesis, Proceedings of the 1995 international symposium on Low power design, p.69-74, April 23-26, 1995, Dana Point, California, United States [doi>10.1145/224081.224094]
• 7: D. E. Goldberg and S. Voessner. Optimizing global-local search hybrids. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 220-228, 1999.
• 8: Laurence Goodby , Alex Orailoglu , Paul M. Chau, Microarchitectural Synthesis of Performance-Constrained, Low-Power VLSI Designs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.323-326, October 10-12, 1994
• 9: H. Ishibuchi and T. Murata. Multi-objective genetic local search algorithm. In Proceedings of the IEEE Conference on Evolutionary Computation, pages 119-124, 1996.
• 10: A. Kahn, C. McCreary, J. Thompson, and M. McArdle, "A Comparison of Multiprocessor Scheduling Heuristics", in Proceedings of 1994 International Conference on Parallel Processing vol. II, pages 243-250, 1994.
• 11: E. A. Lee and S. Ha. Scheduling strategies for multipreoessor real time DSP. In Proceedings of the Global Telecommunications Conference, November 1989.
• 12: Yau-Tsun Steven Li , Sharad Malik, Performance analysis of embedded software using implicit path enumeration, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.456-461, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217570]
• 13: D. Mareulescu, "On the Use of Mieroarchitecture-Driven Dynamic Voltage Scaling', Proceedings of ISCA 2000.
• 14: 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]
• 15: Anand Raghunathan , Niraj K. Jha, Behavioral Synthesis for low Power, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.318-322, October 10-12, 1994
• 16: M. Ryan, J. Debuse, G. Smith, and I. Whittley. A hybrid genetic algorithm for the fixed channel assignment problem. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1707-1714, 1999.
• 17: 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]
• 18: Darrell Whitley, The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best, Proceedings of the third international conference on Genetic algorithms, p.116-121, December 1989, George Mason University, United States
• 19: E. Zitzler, J. Teich, and S. S. Bhattacharyya. Optimizing the efficiency of parameterized local search within global search: A preliminary study. In Proceedings of the Congress on Evolutionary Computation, pages 365-372, San Diego, California, July 2000.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Experimentation, Management

Keywords:
dynamic voltage scaling, simulated heating