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

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 an 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 beating. In this paper, we explore various hybrid search management strategies for power optimization under the framework of simulated heating. We demonstrate that cartful search management leads to significant power consumption improvement over add-hoc global search / local starch integration, and explore alternative approaches to performing hybrid search management for dynamic voltage scaling.