异构机群系统上带返回信息的可分负载多轮调度算法  

A Multi-Round Scheduling Algorithm for Divisible Workloads with Return Messages on Heterogeneous Cluster Computing Systems

作　　者：钟诚[1] 李显宁[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机研究与发展》2008年第z1期99-104,共6页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60563003)

摘　　要：针对处理机具有不同的计算速度、通信能力的异构机群计算环境,以及实际应用中许多问题的求解在处理完任务后向中心处理机节点返回处理结果信息的情形,通过允许计算和通信操作重叠执行,采取FIFO调度策略和多次并行分配计算任务的方法,提出一种带返回结果信息的调度轮数可变的可分负载多轮调度算法.实验结果表明,该算法对于处理具有返回结果信息的应用的调度性能优于UMR可分负载多轮调度算法,并且可以获得近似最优的调度轮数.By implementing the overlapped execution of computation and communication and applying FIFO strategy and the multiple parallel distribution task techniques, a multi-round algorithm with return messages and changeable scheduling rounds for scheduling divisible workloads is presented on the heterogeneous cluster computing systems in which the processors have different computing speeds and communication capabilities. The experiment results on the cluster of personal computers indicate that the presented algorithm not only obtains better scheduling time length than the existing algorithms for scheduling of divisible applications with return messages, but also can achieve an asymptotically optimal number of scheduling rounds.

关 键 词：异构机群系统 任务调度 并行算法 返回信息 可分负载 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构] TP301.6[自动化与计算机技术—计算机科学与技术]