Abstract: According to the autonomy, heterogeneity, and distributed nature of grid computing system, the paper proposes a new grid scheduling algorithm to reduce average task response time with dynamic prediction and task flow shaping. The algorithm uses history data and the recent task request time, task completion time, and network communication delay, to predict the future task response time at each computing node. Based on the prediction result, tasks will be assigned to compute nodes which are predicted to have less work load and better performance in the near future. The resource utilization can be improved by both the dynamic adaptation algorithm and the task flow shaping algorithm. Experimental results show that approach outperforms existing scheduling algorithms(e.g., random scheduling) in terms of task response time and throughput.

Key words: prediction, response time, task flow shaping, load balance

摘要： 针对网格环境下计算节点的自治性、异构性、分布性等特征，提出一种基于任务响应时间的动态修正预测和任务流整形的网格调度算法，该调度方法依据历史数据和最近访问过计算节点的任务请求提交时间、任务完成时间、网络通信延迟等信息，预测计算节点的将来任务响应时间，将任务提交给预测的轻负载或性能较优的计算节点完成。通过使用动态修正算法和任务流整形算法降低预测误差，提高资源利用率。实验结果表明，该方法在任务响应时间、任务的吞吐率等方面优于随机调度等传统算法，具有较好的综合性能。

关键词: 预测, 响应时间, 任务流整形, 负载均衡

CLC Number: 

• TP393