A comparison among grid scheduling algorithms for independent coarse-grained tasks
A comparison among grid scheduling algorithms for independent coarse-grained tasks
复制标题
DOI：
10.1109/saintw.2004.1268711
复制
发表时间：
2004-01
期刊：
影响因子：
--
通讯作者：
N. Fujimoto;K. Hagihara
中科院分区：
文献类型：
--
作者：
N. Fujimoto;K. Hagihara
任务调度问题最常见的目标函数是完工时间。然而，在计算网格上，第二最佳完工时间可能比最佳完工时间长得多，因为网格的计算能力随时间变化。因此，如果性能指标是完工时间，则一般不存在用于调度到网格上的近似算法。相比之下，最近作者提出了调度所消耗的计算能力作为调度的标准，并为该标准给出了(1+m(log/sub e/(m - 1) + 1)/n)-近似算法RR，用于将n个具有相同长度的独立粗粒度任务调度到具有m个处理器的网格上。 RR 不使用底层资源的任何预测信息。 RR是第一个近似的网格调度算法。然而，到目前为止，尚未给出相关启发式算法之间的任何性能比较。本文展示了 RR 与五种相关算法的调度消耗计算能力比较的实验结果。事实证明，RR 仅次于需要处理器速度和任务长度预测信息的最佳算法，尽管 RR 不需要此类信息。
The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the computing power of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid. In contrast, recently the authors proposed the computing power consumed by a schedule as a criterion of the schedule and, for the criterion, gave (1+m(log/sub e/(m - 1) + 1)/n)-approximation algorithm RR for scheduling n independent coarse-grained tasks with the same length onto a grid with m processors. RR does not use any prediction information on the underlying resources. RR is the first approximation algorithm for grid scheduling. However, so far any performance comparison among related heuristic algorithms is not given. This paper shows experimental results on the comparison of the consumed computing power of a schedule among RR and five related algorithms. It turns out that RR is next to the best of algorithms that need the prediction information on processor speeds and task lengths though RR does not require such information.