计算网格中基于时间均衡的并行粗粒度任务调度算法

考虑网格资源异构、自治、动态等特性,讨论本地用户具有强占优先权情况下的任务调度问题,提出了TBBS(Time-Balancing Based Scheduling Algorithm)算法.建立调度优化模型,以期望完成时间最小为目标选择执行任务的最佳资源组合.以时间均衡策略将任务分解并调度到资源上执行,减少了子任务同步时因等待而产生的延时,获得较好的并行计算性能.采用重复调度策略,适应计算网格中资源的特性.

A Dynamic Scheduling Algorithm of Parallel Coarse Grain Tasks in Computational Grid Based on Time-balancing Strategy

The Computational Grid provides a promising platform for the efficient execution of parallel coarse grain tasks over very large sample space. Scheduling such applications is challenging for the heterogeneity, autonomy, dynamic adaptability of grid resources. Assuming resource owners have a preemptive priority, we propose an adaptive algorithm of jobs scheduling based on time balancing strategy, which solves the parallel computing tasks by using the idle resources in Computational Grid. A mathematical model is developed to predict performance, which also considers systems with heterogeneous machine utiliza- tion and heterogeneous service distribution. The model separates the influence of machine utilization, job service rate and parallel task allocation on the completion time. According to the time balancing policy, a task is partitioned into several subtasks and scheduled, and the costs of communication are reduced. The mean of parallel task completion time is predicted with performance model. To get better parallel computing performance, an optimal subset of heterogeneous resources with the shortest parallel executing time of tasks can be selected with the efficient algorithm. Remapping strategy is applied during scheduling, which is more suitable for the dynamic adaptability and domain autonomy in the grid.