用爬山法实现无中心式网格调度

Implementation of de-centralized grid scheduling using hill climbing

为方便网格资源的扩展,网格调度应当是无中心的。为在尽可能多的计算资源中为单地点作业优化资源选择,这里采用了爬山算法。当一个网格调度器收到一个单地点作业,爬山法被激活,根据网格调度器之间的相邻关系为作业找出最适合的计算系统,这里每个计算系统的适合度用预测的作业响应时间表示。实验模拟了无中心式网格调度与计算系统之间的性能差别,每个计算系统的本地调度采用保守式装填法,网格工作负荷由模型得到,并用一段工作负荷的平均响应时间衡量调度性能。实验结果表明,即使在作业提交点分布不均匀且运行时间估计不准确情况下,爬山法仍可有效改善单地点作业的调度。

To facilitate the expansion of grid resources, grid scheduling is de-centralized. To optimize the resource selection of each single-site job in as many resources as possible, hill climbing is applied. When a grid scheduler receives a single-site job, hill climbing is triggered to find the most appropriate computing system for the job based on the neighbor relations between grid schedulers, where the appropriateness degree of one computing system for the job is represented by the predicted job response time on the computing system. In experiments, the de-centralized grid scheduling and performance differences of computing systems are simulated respectively, and conservative backfilling is used as the local scheduling strategy on each computing system. The grid workload is obtained by modeling, while the average job response time of one segment of workload is used to represent scheduling performance. Results show hill climbing is efficient to improve the schedules of single-site jobs, even when the distribution ofjob submittal location is non-uniform or the runtime estimates are inaccurate.