The Bell Is Ringing in Speed-Scaled Multiprocessor Scheduling
The Bell Is Ringing in Speed-Scaled Multiprocessor Scheduling
复制标题
速度扩展的多处理器调度的钟声已经敲响
DOI：
10.1007/s00224-013-9477-9
复制
发表时间：
2014
影响因子：
0.5
通讯作者：
A. Souza
中科院分区：
文献类型：
--
作者：
G. Greiner;T. Nonner;A. Souza
本文研究了在不迁移的情况下在多个速度扩展的处理器上调度作业的问题，即我们有常数 α > 1，这样以速度运行处理器会导致每时间单位的能耗#945。我们考虑一般情况，即每项工作都有一个单调递增的成本函数，该函数会惩罚延迟。这包括迄今为止考虑的截止日期和流程时间的情况。对于任何类型的延迟成本函数，我们得到以下结果：单处理器的任何 β 近似算法都会产生多处理器的随机 βBα 近似算法，其中 Bα 是第 α 个 Bell 数，即一组大小为 α 的分区数。类似地，我们表明，任何单处理器的 β 竞争在线算法都会产生多处理器的 βBα 竞争在线算法。最后，我们表明，任何带有迁移的多处理器的 β 近似算法都会为没有迁移的多处理器产生确定性的 βBα 近似算法。这些事实改进了几个近似比率并产生了新的结果。例如，我们获得了多处理器的第一个常数因子在线和离线近似算法，无需迁移任意发布时间、截止日期和作业大小。所有算法都基于一个令人惊讶的事实，即我们可以通过预期的 Bα 放大来消除迁移。
This paper investigates the problem of scheduling jobs on multiple speed-scaled processors without migration, i.e., we have constant α > 1 such that running a processor at speedsresults in energy consumptions#945;per time unit. We consider the general case where each job has a monotonously increasing cost function that penalizes delay. This includes the so far considered cases of deadlines and flow time. For any type of delay cost functions, we obtain the following results: Any β-approximation algorithm for a single processor yields a randomized βBα-approximation algorithm for multiple processors, whereBαis the αth Bell number, that is, the number of partitions of a set of size α. Analogously, we show that any β-competitive online algorithm for a single processor yields a βBα-competitive online algorithm for multiple processors. Finally, we show that any β-approximation algorithm for multiple processors with migration yields a deterministic βBα-approximation algorithm for multiple processors without migration. These facts improve several approximation ratios and lead to new results. For instance, we obtain the first constant factor online and offline approximation algorithm for multiple processors without migration for arbitrary release times, deadlines, and job sizes. All algorithms are based on the surprising fact that we can remove migration with a blowup ofBαin expectation.
登录
查看更多内容
流量和能量的非透视速度缩放
影响因子：
1.1
作者：
H. Chan;J. Edmonds;T. Lam;Lap;A. Marchetti;K. Pruhs
通讯作者：
K. Pruhs
流动时间和能量的竞争性非迁移调度
影响因子：
1.1
作者：
T. Lam;Lap;I. K. To;Prudence W. H. Wong
通讯作者：
Prudence W. H. Wong
任意幂函数下的最佳速度缩放
DOI：
10.1145/1639562.1639576
发表时间：
2009
期刊：
ACM SIGMETRICS Performance Evaluation Review
影响因子：
--
作者：
L. Andrew;A. Wierman;A. Tang
通讯作者：
A. Tang
为您的设备获得最佳响应
DOI：
10.1145/1367064.1367078
发表时间：
2004
期刊：
--
影响因子：
--
作者：
K. Pruhs;Patchrawat Uthaisombut;G. Woeginger
通讯作者：
G. Woeginger
基于活动作业计数的流程时间调度的速度缩放功能
影响因子：
4.6
作者：
T. Lam;Lap;I. K. To;Prudence W. H. Wong
通讯作者：
Prudence W. H. Wong