Competitive non-migratory scheduling for flow time and energy
Competitive non-migratory scheduling for flow time and energy
复制标题
流动时间和能量的竞争性非迁移调度
DOI：
10.1145/1378533.1378580
复制
发表时间：
2008
期刊：
影响因子：
1.1
通讯作者：
Prudence W. H. Wong
中科院分区：
文献类型：
--
作者：
T. Lam;Lap;I. K. To;Prudence W. H. Wong
能源使用是最近在线调度研究中的一个重要问题。在本文中，我们扩展流时间和能量之间的权衡的研究从单处理器设置[8，6]到多处理器设置。我们的主要结果是一个简单的非迁移的在线算法称为CRR（分类轮循）在m ≥ 2处理器上的分析，表明它的流动时间和能量是O（1）倍的最佳非迁移离线算法，当允许的最大速度略有放宽。即使与最佳迁移离线算法进行比较，该结果仍然成立（竞争比增加了2.5倍）。作为一种特殊情况，我们的工作也有助于传统的在线流时间调度。具体而言，仅为了最小化流时间，CRR可以在使用足够快的处理器时产生竞争比1或甚至任意小于1。在我们的工作之前，类似的结果只适用于需要迁移的在线算法[21，23]，而最好的非迁移结果可以实现O（1）竞争比[14]。
上述结果源于一个有趣的观察，即总是存在一些最佳迁移调度S，其可以被转换（在离线意义上）为非迁移调度S '，其中流动时间加上能量适度增加。更重要的是，这种非迁移计划始终以与CRR相同的方式分派作业。
Energy usage has been an important concern in recent research on online scheduling. In this paper we extend the study of the tradeoff between flow time and energy from the single-processor setting [8, 6] to the multi-processor setting. Our main result is an analysis of a simple non-migratory online algorithm called CRR (classified round robin) on m ≥ 2 processors, showing that its flow time plus energy is within O(1) times of the optimal non-migratory offline algorithm, when the maximum allowable speed is slightly relaxed. This result still holds even if the comparison is made against the optimal migratory offline algorithm (the competitive ratio increases by a factor of 2.5). As a special case, our work also contributes to the traditional online flow-time scheduling. Specifically, for minimizing flow time only, CRR can yield a competitive ratio one or even arbitrarily smaller than one, when using sufficiently faster processors. Prior to our work, similar result is only known for online algorithms that needs migration [21, 23], while the best non-migratory result can achieve an O(1) competitive ratio [14].
The above result stems from an interesting observation that there always exists some optimal migratory schedule S that can be converted (in an offline sense) to a non-migratory schedule S' with a moderate increase in flow time plus energy. More importantly, this non-migratory schedule always dispatches jobs in the same way as CRR.