Discrete and continuous min-energy schedules for variable voltage processors
Discrete and continuous min-energy schedules for variable voltage processors
复制标题
可变电压处理器的离散和连续最小能量调度
DOI：
10.1073/pnas.0510886103
复制
发表时间：
2006
影响因子：
11.1
通讯作者：
Frances F. Yao
中科院分区：
文献类型：
--
作者：
Minming Li;A. C. Yao;Frances F. Yao
当前的动态电压缩放技术允许动态设置处理器的速度以节省能源消耗，这在微处理器设计中是一个主要问题。十年前首次提出了一种针对最小能量工作计划的理论模型，这表明，对于任何凸能函数，一组n个作业的最小能量时间表具有独特的特征，并且可以在O中进行计算（n（n（n（n））（n（n（n） 3））时间。尽管对该模型进行了许多研究，但该算法仍然是最有效的算法。在这项工作中，我们给出了一种使用运行时间O（n（2）log n）的算法，以查找最小能量时间表。与以前的算法相反，该算法从高到低迭代的最佳速度水平输出，我们的算法基于找到对最佳时间表的连续近似值。近似的核心是通过任何速度阈值将作业设置为高速和低速子集的有效分区，而无需计算确切的速度函数。
Current dynamic voltage scaling techniques allow the speed of processors to be set dynamically to save energy consumption, which is a major concern in microprocessor design. A theoretical model for min-energy job scheduling was first proposed a decade ago, and it was shown that for any convex energy function, the min-energy schedule for a set of n jobs has a unique characterization and is computable in O(n(3)) time. This algorithm has remained as the most efficient known despite many investigations of this model. In this work, we give an algorithm with running time O(n(2) log n) for finding the min-energy schedule. In contrast to the previous algorithm, which outputs optimal speed levels from high to low iteratively, our algorithm is based on finding successive approximations to the optimal schedule. At the core of the approximation is an efficient partitioning of the job set into high and low speed subsets by any speed threshold, without computing the exact speed function.