网络并行环境下多处理机任务的调度  

Multiprocessor-job Scheduling on Network Parallel System

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

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

出　　处：《小型微型计算机系统》2003年第7期1144-1147,共4页Journal of Chinese Computer Systems

基　　金：国家杰出青年学者自然科学基金资助;长江学者奖励基金资助

摘　　要：随着网络技术的不断发展 ,网络上可供共享的资源越来越丰富 ,集群技术的兴起更是扩展了并行计算的环境 .这种环境下系统中很多任务依赖于多种资源 (或多个处理机 ) ,称这样的任务为多处理机任务 .本文研究基于多处理机任务的调度模型 Pm|fix|Cmax.当 m≥ 3时 ,这类调度问题是强 NP-难的 ,所以只能寻求有好的逼近性能的多项式时间近似算法 .文中给出了当 m =4或 5时线性时间的近似调度算法 ,优于目前已有的最好结果 ,最后我们还讨论了当 k≥Many jobs in parallel systems usually depend on more than one resource or more than one processor. This kind of jobs is called multiprocessor job. In this paper, we study the scheduling model P m|fix|C max based on multiprocessor jobs. When m≥3, the problem is NP hard in the strong sense thus it does not have a fully polynomial time approximation scheme unless P=NP. We develop a linear time approximation algorithm of ratio 3/2 for m=4 and 2 for m=5 of the P m|fix|C max problem, which improves the best previous results (2 and 2.5 respectively) for practical algorithms for the problem. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than five processors. We will also introduce a generalized and more practical scheduling algorithm.

关 键 词：并行系统 多处理机任务 任务调度 近似算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]