Energy Optimal Scheduling on Multiprocessors with Migration
Energy Optimal Scheduling on Multiprocessors with Migration
复制标题
具有迁移功能的多处理器上的能量优化调度
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Greenstreet
中科院分区：
文献类型：
--
作者：
B. Bingham;M. Greenstreet
我们表明，在允许工作迁移的多处理器上找到能源最小的时间表以执行一系列作业的问题，具有多项式复杂性。每个作业都由发布时间，截止日期和要执行的工作数量来指定。所有处理器的表格p = phi（s）的凸功率速度相同，其中p是功率，s是速度，而phi是凸。与以前的多处理器调度有关的工作不同，我们对发布时间，截止日期或要完成的工作数量没有任何限制。我们表明，调度问题是凸面，并根据线性编程提供算法。我们证明，对于任何凸电速度权衡功能，最佳时间表都是相同的。
We show that the problem of finding an energy minimal schedule for execution of a collection of jobs on a multiprocessor with job migration allowed has polynomial complexity. Each job is specified by a release time, a deadline, and an amount of work to be performed. All of the processors have the same, convex power-speed trade-off of the form P = phi(s), where P is power, s is speed, and phi is convex. Unlike previous work on multiprocessor scheduling, we place no restriction on the release times, deadlines, or amount of work to be done. We show that the scheduling problem is convex, and give an algorithm based on linear programming. We show that the optimal schedule is the same for any convex power-speed trade-off function.