网络集群计算系统中的并行任务调度  

Parallel-job Scheduling on Cluster Computing Systems

作　　者：黄金贵[1] 陈建二[1] 陈松乔[1] 

机构地区：[1]中南大学信息科学与工程学院计算机理论与软件研究所,长沙410083

出　　处：《计算机学报》2004年第6期765-771,共7页Chinese Journal of Computers

基　　金：国家杰出青年自然科学基金 ( 6992 80 1);国家自然科学基金 ( 90 10 40 2 8);长江学者奖励计划基金资助

摘　　要：基于多处理机并行任务调度模型 ,探讨网络集群计算系统中的并行任务调度问题 .首先证明了一般网络集群计算系统中调度算法的可近似性难度 ,然后提出了三种不同的启发式算法 :最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法 ;然后根据大量的模拟实验对这些算法以及文献中已提出的调度算法进行了比较分析 ,结果表明该文的启发式算法比文献中的算法在性能上效果更好 .Cluster computing system has attracted much attention recently as a new parallel computing model. Because of its heterogeneous, jobs in a cluster computing system may have alternative execution modes and may require parallel execution of multiple resources in the system. This new job execution mode on cluster computing systems has proposed new challenging research projects for system job scheduling and resource management. Based on our previous theoretical research and new investigation on the parallel job scheduling problem, this paper is focused on the study of parallel job scheduling problem on cluster computing systems. We first prove that in a cluster computing system with a large number of processors, it is impossible to develop parallel job scheduling algorithms even with very loose quality requirements. Three new heuristic algorithms LLF (Largest Length First), LWF (Largest Width First) and LAF (Largest Area First) are proposed. The extensive experimental results show that our new algorithms improve significantly over the previous algorithms proposed in the literature. Consequently, these algorithms are more effective in practice for the job scheduling and resource management for cluster computing systems.

关 键 词：网络集群计算系统 并行任务调度 多处理机 调度算法 启发式算法 近似算法 

分 类 号：TP393.0[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]