Optimizing throughput and energy in online deadline scheduling
Optimizing throughput and energy in online deadline scheduling
复制标题
DOI：
10.1145/1644015.1644025
复制
发表时间：
2009-12
期刊：
影响因子：
--
通讯作者：
H. Chan;W. Chan;T. Lam;Lap-Kei Lee;Kin-Sum Mak;Prudence W. H. Wong
中科院分区：
文献类型：
--
作者：
H. Chan;W. Chan;T. Lam;Lap-Kei Lee;Kin-Sum Mak;Prudence W. H. Wong
本文将用于节能截止日期安排的在线算法的研究扩展到了超负荷设置。具体而言，我们考虑一个可以在0和最大速度t之间改变其速度以最大程度减少其能量使用的处理器（速率被认为是速度的立方函数）。由于速度是上限的，因此处理器可能会超载工作，并且没有计划算法可以保证满足所有工作的截止日期。预计最佳时间表将最大化吞吐量，此外，其能量使用应是实现最大吞吐量的所有时间表中最小的。在设计调度算法时，必须面对选择更多工作并在能源使用方面保守的困境。如果我们忽略了能源使用情况，那么最好的在线算法在吞吐量上是4个竞争力[Koren and Shasha 1995]。另一方面，现有的节能计划工作集中在处理器速度无限的环境上，而关注的是最大程度地减少完成所有工作的能量； o（1） - 关于能源用法的竞争性在线算法已知[Yao等。 1995; Bansal等。 2007a; Li等。 2006]。本文介绍了第一种在线算法，用于更现实的设置，在该设置中，处理器速度的限制并且系统可能会超载；该算法在吞吐量和能量使用方面均为O（1）竞争。如果在线调度程序的最大速度在某些> 0时略微放松至（1+）t，我们可以将吞吐量的竞争比率提高到任意接近一个，同时维持o（1）竞争能量的能量。
This article extends the study of online algorithms for energy-efficient deadline scheduling to the overloaded setting. Specifically, we consider a processor that can vary its speed between 0 and a maximum speed T to minimize its energy usage (the rate is believed to be a cubic function of the speed). As the speed is upper bounded, the processor may be overloaded with jobs and no scheduling algorithms can guarantee to meet the deadlines of all jobs. An optimal schedule is expected to maximize the throughput, and furthermore, its energy usage should be the smallest among all schedules that achieve the maximum throughput. In designing a scheduling algorithm, one has to face the dilemma of selecting more jobs and being conservative in energy usage. If we ignore energy usage, the best possible online algorithm is 4-competitive on throughput [Koren and Shasha 1995]. On the other hand, existing work on energy-efficient scheduling focuses on a setting where the processor speed is unbounded and the concern is on minimizing the energy to complete all jobs; O(1)-competitive online algorithms with respect to energy usage have been known [Yao et al. 1995; Bansal et al. 2007a; Li et al. 2006]. This article presents the first online algorithm for the more realistic setting where processor speed is bounded and the system may be overloaded; the algorithm is O(1)-competitive on both throughput and energy usage. If the maximum speed of the online scheduler is relaxed slightly to (1+)T for some > 0, we can improve the competitive ratio on throughput to arbitrarily close to one, while maintaining O(1)-competitiveness on energy usage.