（计算机应用技术专业论文）异构机群系统的可分负载调度算法研究.pdf

异构机群系统的可分负载调度算法研究 摘要 异构机群系统利用工作站和个人计算机进行分布式并行处理，以较低的 成本完成大规模、复杂问题的计算处理。相对于单一的并行计算机，异构 机群系统具有较高的性价比，并且非常具有发展前景，但是同时也提出了 许多富有挑战性的问题，任务调度就是其中的一个重要问题。如果任务调 度问题得不到有效解决，那么可能导致异构机群系统效率低下，甚至可能 不如单个计算机，严重的可能导致计算失效。 可分负载调度具有广泛的应用背景，且相对简单和易于分析，近几年得 到了比较广泛的研究与应用。现有的异构机群系统调度算法大多是针对同 构全互连机群系统设计的，很少考虑到处理机具有不同的通信、存储和计 算能力等实际因素。对于处理机具有不同的计算速率、通信速率、通信延 迟和存储能力的异构机群系统，本文研究可分负载调度算法及其性能。 在均匀多轮调度算法u m r 的基础上，本文充分考虑处理机具有不同的 计算速度、通信能力和存储容量的特性，通过允许计算和通信操作重叠执 行，采取多次并行分配计算任务的方法，提出一种可分负载多轮调度算法 u m r l m 。算法分析与实验结果表明，一方面，u m r l m 算法在调度时间 上仍能取得与u m r 算法相当的近似最优的调度时间长度；另一方面，实验 结果表明当负载量较大，使得某一轮调度分配给某个处理机的负载超出了 该处理机的实际可用内存容量时，u m r 算法无法继续执行，而本文提出的 算法由于考虑了实际可用内存的有限性而不受此限制，能够处理更大规模 的应用负载、实用性更强。 针对处理机具有不同的计算速度、通信能力的异构机群计算环境，以及 实际应用中许多问题计算处理完毕后需要向主处理机节点返回大量结果信 息的实际情况，通过允许计算和通信操作重叠执行，采取f i f o 调度策略和 多次并行分配计算任务的方法，提出了一种带返回信息的调度轮数可变的 可分负载多轮调度算法。算法分析与实验结果表明，该算法处理具有返回 结果信息的应用的调度性能明显优于已有的可分负载多轮调度算法u m r ， 并获得近似最优的调度轮数，能够适应更为广泛的应用的调度问题。 关键字：异构机群系统任务调度并行算法可分负载返回信息并 行计算 n s t u d yo np a r a l l e la l g o r i t h mf o rs c h e d u l i n gd i v i s i b l el o a d s o hh e t e r o g e n e o u sc l u s t e rc o m p u t i n gs y s t e m s a b s t r a c t b ya p p l y i n gt h ew o r k s t a t i o nc o m p u t e r sa n dp e r s o n a lc o m p u t e r st oi m p l e m e n tp a r a l l e l d i s t r i b u t e dp r o c e s s i n g , h e t e r o g e n e o u sc l u s t e rs y s t e mc a nc o m p l e t et h el a r g e - s c a l e a n d c o m p l i c a t e dc o m p u t i n gt a s k s h e t e r o g e n e o u sc l u s t e rs y s t e mh a sh i g h e rp e r f o r m a n c e - p r i c e r a t i oa n dg r e a td e v e l o p m e n tp r o s p e c t sw i t hc o m p a r i s o no f t h es i n g l ep a r a l l e lc o m p u t e r t h e r e a r cm a n yc h a l l e n g i n gr e s e a r c hp r o b l e m si nh e t e r o g e n e o u sc l u s t e rc o m p u t i n gs y s t e m s , a n dt h e t a s ks c h e d u l i n gt e c h n i q u ei so n eo ft h ep r o b l e m s i ft h ee f f i c i e n tp a r a l l e lt a s ks c h e d u l i n g t e c h n i q u e i sn o td e v e l o p e d , t h ep e r f o r m a n c eo f h e t e r o g e n e o u sc l u s t e rc o m p u t i n gs y s t e m sm a y b el o w e rt h a nt h a to f as i n g l ec o m p u t e r t h ed i v i s i b l el o a d ss c h e d u l i n gh a sb e e nw i d e l ys t u d i e di nt h el a s tt e ny e a r s i th a s e x t e n s i v e l ya p p l i c a t i o nb a c k g r o u n da n di sr e l a t i v e l ys i m p l ea n de a s yt oa n a l y z e t h ee x i s t i n g a l g o r i t h m sf o rt h ed i v i s i b l el o a ds c h e d u l i n g 0 1 1h e t e r o g e n e o u sc l u s t e rs y s t e ma r ea l m o s t d e s i g n e db a s e d0 1 1h e t e r o g e n e o u sc l u s t e rs y s t e mw i t hh o m o g e n e o u sn e t w o r k , w h i c hd on o t t a k ei n t oa c c o u n tt h er e a l i s t i ch e t e r o g e n e o u sc l u s t e rs y s t e mt h a tp r o c e s s o r sh a v ed i f f e r e n t c o m m u n i c a t i o n c a p a b i l i t i e s a n dm e m o r yc a p a c i t i e s ,a n dd i f f e r e n tc o m p u m f i o n a n d c o m m u n i c a t i o nd e l a y t h i sp a p e rw i l ls t u d yt h ed i v i s i b l el o a ds c h e d u l i n ga l g o r i t h m sf o rt h e h e t e r o g e n e o u sc l u s t e rs y s t e m t h a tp r o c e s s o r sh a v eh e t e r o g e n e o u sc o m m u n i c a t i o na n d c o m p u t i n ga n dm e m o r yc a p a c i t i e s b a s e do nt h eu n i f o r mm u l t i r o u n da l g o r i t h m , am u l t i r o u n da l g o r i t h mf o rs c h e d u l i n g d i v i s i b l ew o r k l o a d si sp r e s e n t e do nt h eh e t e r o g e n e o u sc l u s t e rc o m p u t i n gs y s t e m st h a t p r o c e s s o r sh a v ed i f f e r e n tc o m p u t i n gs p e e d sa n dc o m m u n i c a t i o nc a p a b i l i t i e sa n dm e m o r y c a p a c i t i e sb yi m p l e m e n t i n gt h eo v e r l a pe x e c u t i o no fc o m p u t a t i o na n dc o m m u n i c a t i o na n d a p p l y i n g t h em u l t i p l ep a r a l l e ld i s t r i b u t i o nt a s kt e c h n i q u e s t h ea l g o r i t h ma n a l y s i sa n d e x p e r i m e n tr e s u l t so nt h ec l u s t e ro fp e r s o n a lc o m p u t e r st h a tt h ep r e s e n t e da l g o r i t h mn o to n l y o b t a i n st h ea p p r o x i m a t e l yo p t i m a ls c h e d u l i n gt i m el e n g t hl i k et h eu n i f o r mm u l t i - r o u n d a l g o r i t h m , b u ta l s oc a np r o c e s st h ea p p l i c a t i o n sw i t hm o r el a r g e - s c a l ew o r k l o a d s t n t os o l v et h ea p p l i c a t i o nw i t hr e t u r nm e s s a g e s ，am u l t i - r o u n da l g o r i t h mf o rs c h e d u l i n g d i v i s i b l ew o r k l o a d sw i t hr e t t m lm e s s a g e sa n dc h a n g e a b l es c h e d u l er o u n d si sp r e s e n t e do nt h e h e t e r o g e n e o u sc l u s t e rc o m p u t i n gs y s t e m st h a tt h ep l o c e s s o r sh a v ed i f f e r e n tc o m p u t i n gs p e e d s a n dc o m m u n i c a t i o nc a p a b i l i t i e sb yi m p l e m e n t i n gt h eo v e r l a pe x e c u t i o no fc o m p u t a t i o na n d c o m m u n i c a t i o na n da p p l y i n gf i f os t r a t e g ya n dt h em u l t i p l ep a r a l l e ld i s t r i b u t i o nt a s k t e c h n i q u e s t h ea l g o r i t h ma n a l y s i s a n de x p e r i m e n tr e s u l t so nt h e c l u s t e ro fp e r s o n a l c o m p u t e r s t h a tt h ep r e s e n t e da l g o r i t h mo b t a i n sa na p p r o x i m a t e l yo p t i l l l a ln u m b e ro f s c h e d u l i n gr o u n d sa n di t ss c h e d u l i n gp e r f o r m a n c ei ss u p e r i o rt ot h eu m ra l g o r i t h mf o r s c h e d u l i n gd i v i s i b l ew o r k l o a d s k e yw o r d s ：h e t e r o g e n e o u sc l u s t e rc o m p u t i n gs y s t e m s ；t a s ks c h e d u l i n g ； p a r a l l e la l g o r i t h m s ；d i v i s i b l el o a d s ；r e t u r nm e s s a g e s ；p a r a l l e l c o m p u t i n g i v 异相审u 牛j 0 盹的胃分期l 载调度：算法研究 1 1 引言 第一章绪论 由于对计算能力的需求，近几年并行分布式计算得到了迅速的普及和推广。当前很 多有着深刻影响的关系国民经济、国防科技、商业应用等问题的重大课题对计算能力的 要求都非常高，例如：石油勘测、地震预测、大范围的天气预报、人体基因和遗传工程、 核武系统的研制与模拟等。与此相关的具体应用领域，如求解量子力学、聚合化学、晶 格生长、流体动力学、量子场理论、分子动力学、使用多级牛顿算法求解大规模电路方 程以及进行v l s 上芯片设计等，这些应用对计算能力的需求非常高，单个处理器的计算 机的计算能力远远不能满足它们的要求，均需要由大容量、高速度的高性能计算机系统 来完成。 2 0 世纪7 0 、8 0 年代，相对于家庭和办公用的计算机的处理器而言，超级计算机( 高 性能计算机) 使用的处理器非常昂贵。随着处理器技术的不断发展和进步，现在很多超 级计算机使用与商用或家用个人计算机相似的处理器来构造超级计算机，这种超级计算 机和一般的个人计算机的主要差别在于处理器个数不一样，超级计算机可能由成百上千 个处理器构成。 近几年，随着网络技术的快速发展，很多高性能计算机采用了商用的互联技术。如 2 0 0 6 年的国际t o p 5 0 0 超级计算机中就有近8 0 的系统采用了商用互联网络技术，其中选 择用c r i g a b i t e t h e r n e t ( 千兆以太网) 作为互连的超级计算机占到了2 5 6 个( 5 1 2 ) ，而 在2 0 0 1 年，我们甚至还看不到千兆以太网的身影“。采用商品化的微处理器加上商品化 的互连网络构造的分布存储的并行计算机系统称为机群。由于处理器技术、网络技术等 的快速发展，为计算机机群系统的发展提供了很好的机会。机群系统通过快速网络将工 作站、个人计算机等资源互连起来，作为单一系统向用户提供高可靠的、高可用等高性 能的服务，实现以低廉的成本完成大规模、复杂问题的并行计算处理。随着网络技术和 处理器技术的不断发展，机群系统得到了很快的发展。如2 0 0 6 年的国际t o p 5 0 0 超级计 算机的前1 0 名中，机群系统占了7 个，而t o p 5 0 0 中就有3 6 4 套系统是机群系统( 采用机群 体系结构的高性能计算系统) ，占到了7 2 8 ，而在2 0 0 1 年6 月的t o p 5 0 0 中只有3 2 套高 性能计算系统属于机群系统，数年间增长了十倍之多【l 】。从世界t o p s 0 0 的统计数据来看， 机群已经成为了目前世界高性能计算机的主流结构。 机群系统在软件的支持、管理和维护、可靠性、可扩展性、性价比等方面都要比小 型机和服务器集群等传统的高性能计算机要好。因此，作为普及和推广高性能计算及其 应用而言，机群具有很大的优势且非常具有发展前景。 但是同时也提出了许多富有挑战性的问题，任务调度就是其中的一个基本问题。所 柏事l | 牛j 0 晓的司分直麓调度算鳍开，巴 谓任务调度问题是指，如何把复杂的应用程序的所有任务合理地调度分配到机群系统的 各个处理机上，并追求整个应用程序的最小完成时间。如果任务调度问题得不到有效解 决，那么可能导致机群系统效率低下，甚至可能不如单个计算机，严重的可能导致计算 失败。因此，在机群系统中，要取得好的系统和应用性能，有效地调度任务是一个非常 关键的问题。 1 2 并行任务调度研究进展 并行任务调度问题在各种不同的应用模型上已经得到了广泛的研究，常见的有比较 流行的基于d a g 图理论的任务调度和基于可分负载理论( d l t ) 的独立任务调度即称可 分负载调度。 1 2 1 基于d a g 图并行任务调度研究进展 基于d a g 图的任务调度也称为d a g 任务调度，d a g 任务调度即人们所说的一般的任 务调度问题，基于d a g 图理论，使用节点表示任务，有向边表示任务之间的时序约束( 依 赖) 关系或通信量。d a g 任务调度问题大都是n p - 完全的，只有三种特殊情况例# l , t 2 j 。 第一种情况是当任务图是自由树结构且所有任务节点的权值相同和处理机数目不限时， 对于此种情形文献 3 】提出了一个线性时间复杂度的最优解。第二种情况是当任务图是任 意结构且所有节点权值相同和处理机数目为两个时，文献【4 】给出了此种情形下的时间复 杂度为o ( v 2 ) ( v 为任务节点数) 的最优解；随后，文献【5 】对文献【4 】的算法作了改进，并 得到了差不多是线性复杂度的最优解。第三种情况是当任务图是区间有序的d a g 图且所 有节点权值相同和处理机个数任意时，为此文献f 6 】设计了一个解决该问题的线性时间复 杂度算法。以上三种情况都没有考虑任务节点间的通信。 从算法使用的基本调度技术来看，基于d a g 图的任务调度方法概括起来可以分为表 调度方法、基于聚类的调度方法、基于任务复制的调度方法、有指导的随机搜索调度方 法四类。 在实际的调度算法中，除了单独使用以上的某一种技术外，很多调度算法的设计都 结合了以上两种或三种方法，如表调度和聚类方法、表调度和任务复制方法、表调度和 遗传算法等等。 下面归纳、分析上述四种调度技术在异构计算环境下的一些有代表性的任务调度算 法，其中v 为任务节点数，e 为边数，p 为处理机数目。 ( 1 ) 异构计算环境下的表调度算法 f l b - f ( f a s tl o a db a l a n c i n g ) 算澍7 】：此算法使用一个就绪队列，该就绪队列包 含每一步要调度的所有就绪节点。就绪节点被定义为所有父节点都已经被调度的节点。 每一步都要计算就绪队列中的每一个就绪节点在每一台处理机上的完成时间，并且能最 2 广西，叫煳士孽啦论文 鼻柏和u 牛j 濑的司r 分鱼载调度囊时表研究 小化最早完成时间的处理机节点将被选中。f l b f 算法的时间复杂度是o ( v l o g 到a + e ) 。 f c p ( f a s tc r i t i c a lp a t h ) 算法【刀：该算法是一个静态的表调度算法，在处理机选 择阶段，通过限制目标处理机的选择( 即每一个任务尝试性地调度到每一个处理机上， 所有处理机中最早成为空闲处理机的那两个为候选处理机，然后再从候选处理机中选取 目标处理机) 。这样，处理机选择的时间复杂度得到了明显的减少。算法时间复杂度为 o ( v l 0 9 2 p + e ) 。 h e f t ( h e t e r o g e n e o u s e a r l i e s tf i n i s ht l m e ) 算法【卅：h e f t 属于b n p ( b o u n d e d n u m b e rp r o c e s s o r ) 类，是一个处理机数目有限的全互连的异构处理机系统的调度算法， 该算法包括任务优先数确定阶段和处理机选择阶段。算法在每一步选择具有最高升秩 ( u p w a r dr a n k ) 值的任务并把该任务分配给处理机，通过基于插入的方法最小化任务的 最早完成时间。该算法被认为是异构计算环境下较好的启发式任务调度算法之一8 , 1 0 。 一般情况下，该算法的调度长度要小于f c p 和f l b f 算法，h e f t 算法的时间复杂度为 o ( 矿) 。 c p o p ( c r i t i c a l - p a t h - o n - a - p r o c e s s o r ) 算法网：此算法c p o p 属于b n p 类。它使 用升秩和降秩( d o w n w a r dr a n k ) 值之和来区分任务的优先关系( 即用升秩和降秩值之和 作为任务的优先数) ，在处理机的选择阶段，如果任务是关键任务则调度到能够使得关 键任务的总执行时间最小的关键处理机上，否则把任务分配到能最小化任务最早完成时 间的处理机上。算法的时间复杂度为o ( p 伊) 。 i l s ( i t e r a t i v el i s ts c h e d u l i n g ) 算法 9 1 ：此算法属b n p 类，其主要思想是通过迭 代的办法( 即对前一次迭代产生的结果进行迭代) 来改善调度质量。该算法首先用h e f t 调度算法产生一个初始调度，然后通过迭代改善之。每一次迭代，d a g 图节点和边的 时间加权使用前一次的迭代结果更新，算法保持迭代过程中发现的最好调度并最终返回 它。算法在平均调度长度上要优于h e f t 调度算法，特别是当任务数处理机数的比值比 较大时算法执行得更好，其在最坏情况下的时间复杂度为0 ( 品。( e p ) ) 。当d a g 图为稠密图时，算法时间复杂度为0 ( s 。( j 2 ) ) ，其中岛。为最大迭代次数。 h c p t ( h e t e r o g e n e o u sc r i t i c a lp a r e n tt r e e s ) 算法【1 0 1 ：该算法属b n p 类，是一种 静态的表调度算法。它使用启发式方法来构造调度队列l ，而不是给任务分配优先数。 该启发式方法将任务图划分成一序列u n l i s t - p a r e n t 【树，每棵树的根节点是一个关键节点， 关键节点被定义为具有相同的平均最早开始时间( a e s t ) 和平均最迟开始时间( a l s t ) 的任务节点。队列l 中的每一个任务节点将被分配到允许任务最早完成的处理机上。 h c p t 算法在调度长度比和加速度方面的性能要优于c p o p 算法和f l b f 算法，其时间复 杂度为o ( p ，2 ) 。 ( 2 ) 异构计算环境下基于任务复制的调度算法 h c d b t s ( h i g h l y c o m m u n i c a t i n g a n d d e p e n d a n t b a s e d t a s k s c h e d u l i n g ) 算法i l i j ： 该算法把d a g 任务图调度到网络互连受限的异构处理机上，通信代价高的任务优先数较 高。算法包括确定任务优先数、处理机选择和任务分配三个阶段。h c d b t s 算法在调度 3 广西大曹u 鼻士掌位论文彝构机群j u 晓的胃。分负载调度算嘲 研究 长度和加速度方面的性能优于h e f t 算法，其时间复杂度为o ( v 2 1 0 9 v ) h c p f d ( h e t e r o g e n e o u sc r i t i c a lp a r e n t sw i t hf a s td u p l i c a t o r ) 算法【1 2 l ：此算法工 作在一个有限处理机数目的全互连的异构计算环境下。在任务优先数确定阶段引入了一 个简单的启发式表调度方法，在处理机分配阶段则引入了一个低复杂度的基于复制的机 制。实验表明h c p f d 算法在调度长度比和加速度方面的性能要优于f l b f 、h e f t 、c p o p 算法，算法时间复杂度为o ( p 伊) 。 i - i n p d ( h e t e r o g e n e o u sn p r e d e c e s s o rd u p l i c a t i o n ) 算法【1 3 】：h n p d 算法结合了 基于插入的表调度技术和多任务复制来最小化调度长度。实验表明，h n p d 算法在调度 效率方面优于i - i e f t 和s t d s 算法，算法时间复杂度为o ( p l ，2 ) 。 ( 3 ) 异构计算环境下基于聚类的调度算法 c h p ( c l u s t e r i n gt a s k so n t oh e t e r o g e n e o u sp r o c e s s o r ) 算法1 1 4 1 ：c h p 算法的初始 阶段，虚拟一个由不限数目的慢速处理机构成的同构计算环境，使用聚类算法产生聚类 任务；第二阶段在考虑任务的计算代价和通信链接代价情况下，使用一个基于表调度的 映射算法把前一阶段产生的聚类分配到有限数目的可用异构处理机上。该算法对于细粒 度任务的调度性能明显优于h e f t 和l d b s 算法。 t r i p l e t 算法【1 5 】：该算法对任务和处理机两者都进行聚类操作( 一般的聚类调度 算法只对任务进行聚类操作) 。在大多数情况下，t r i p l e t 算法的性能要优于h e f t 算法， 其时间复杂度为o ( v a m a xl 0 9 2 ( v a m a x ) + p v ) ，其中a m a x 为d a g 任务图节点的最 大度数，对于大多数d a g 任务图a m a x 是一个常数。 ( 4 ) 异构计算环境下基于有指导随机搜索技术的调度算法 t s h g a ( t o p o l o g i c a ls o r tb a s e dh y b r i dg e n e t i ca l g o r i t h m ) 算法【1 6 j ：该算法是一 个异构计算环境下基于拓扑排序的混合遗传调度算法。算法的染色体采用直接编码的方 式，使用拓扑有序的d a g 队列来确保后代的可行性和保证搜索空间是全局的。算法基于 拉马克进化论，使用贪婪策略来改善局部优化能力。模拟试验结果表明该算法在解的质 量和收敛速度方面都是有效的。 h g a ( h y b r i dg e n e t i c a l g o r i t h m ) 算法【1 7 1 ：该算法适用于同构和异构计算系统， 使用遗传算法来进化任务调度的优先队列，g a 的染色体采用间接编码方式，然后使用 一个表调度算法将优先队列解码为一个有效的调度。为了弥补g a 算法在求精能力方面 的弱点，算法基于拉克马进化论，使用区域搜索方法来改善每一代中个体的适应值。模 拟试验表明，h g a 在调度质量上优于h e f t 算法，并具有较好的加速比，但执行速度远 慢于h e f t 算法。 4 鼻q 0 栅，0 晓的胃努负载1 一度算溺，院 1 2 2 可分负载任务并行调度研究进展 1 2 2 1 问题的提出 各种不同的计算资源( 工作站、计算机等) 通过高速网络互连，并作为一个单一系 统向用户提供高性能、高可用服务的系统异构机群系统。这种异构机群系统利用工 作站和个人计算机进行分布式并行处理，以较低的成本完成大规模、复杂问题的计算处 理，如精确的长期天气预报、能源勘测、油藏模拟等。随着个人计算机处理能力的迅速 增强和新的高性能快速网络的不断出现，异构机群系统更显示出其较好的性能和实用价 值。相对于单一的并行计算机，异构机群系统具有很高的性价比，并且非常具有发展前 景，但是同时也提出了许多富有挑战性的问题，任务调度就是其中的一个基本问题。所 谓任务调度问题是指，如何把复杂的应用程序的所有任务合理地调度分配到异构机群系 统的各个处理机上，并追求整个应用程序的最小完成时间。如果任务调度问题得不到有 效解决，那么可能导致异构机群系统效率低下，甚至可能不如单个计算机，严重的可能 导致计算失败。因此，在异构机群系统中，要取得好的性能，有效地调度任务是一个非 常关键的问题。 1 2 2 2 国内外研究现状 任务的数目和大小可以任意选择即任务的粒度可以任意小的一类独立任务调度问题 称为可分负载调度【1 o 】。科学和工程领域有许多应用是由大量细粒度的独立任务构成 的，即这些应用可以划分成为任意数目和任意大小的任务块，因此这些应用易于直接并 行化，特别是在主从模式下，这一类应用也称为可分负载 1 8 - 2 0 。由于可分负载理论广泛 的应用背景及其结果的简单性和易于分析，使得可分负载任务调度问题的研究近年来引 起人们高度的重视并在大规模信号处理、视频和图像处理、数据挖掘、网络存储、v o d 系统、科学计算、密码求解、大规模仿真、组合优化、负载平衡的扩散操作和模式匹配 等领域得到广泛的应用。可分负载理论( d i v i s i b l el o a dt h e o r y , d l t ) 是调度理论一个新 的分支，文献 1 8 - , 2 2 研究了d l t 及其应用的相关问题，并比较系统地介绍了d l t 及其 应用。相对于n p 完全的一般的d a g 任务图任务调度问题来说，可分负载调度在一定 的假设条件下可以得到闭式最优解或近似最优解，非常具有吸引力。 可分负载调度算法主要分为单轮调度算法和多轮调度算法两大类。单轮调度算法就 是将要处理的应用划分成为与从处理机等数目的负载块，然后一次性顺序把所有的负载 块分配给所有相应的从处理机陟五7 1 。单轮调度算法较为简单，研究得相对比较彻底，但 其计算和通信的重叠性比较差，额外的开销相对较大。多轮调度算法是将应用划分成数 目大于从处理机个数的负载块，并采用多次分配的办法把所有的负载块分发到各个从处 理机上。多轮调度算法对应用负载的划分方法主要有：1 ) 将应用划分成为较大的负载 块，每一轮给从处理机分配的负载块逐轮递减；2 ) 将应用划分成为较小的负载块，每 5 舅柏和u 雌j 臼毫的胃分鱼载调度，法研究 一轮给从处理机分配的负载块逐轮递增；3 ) 给各个处理机分配的负载块先逐渐递增， 然后当负载块增大到一定的大小以后再逐渐递减。多轮调度算法具有较好的计算和通信 重叠性，较好地降低了调度的额外开销，但由于比较难于分析等原因，使得对多轮调度 算法的研究成果相对较少，已有的多轮调度算法大多数是同构机群计算环境下的调度算 法。在一定的假设条件下，一些简单的可分负载调度问题存在紧致形式的最优解。但在 处理机具有不同的计算速度、通信能力和存储容量的异构机群计算环境下的可分负载调 度问题是n p 完全问题 7 s - s o l 。 文献 3 1 1 研究了研究了异构总线网络的负载优化调度问题，详细讨论了处理机选择、 任务分配顺序和各处理机分配任务数量。文献【3 2 】研究了星型机群下的可分负载多轮调 度问题以及对周期性多轮调度算法的参数优化问题，并进一步证明了，对于大规模的负 载，任意能够始终保持通信链路不出现空闲的调度算法是近似最优的调度算法。文献 3 3 】 研究了大规模计算中的可分负载调度问题，并利用线性规划得到了同构机群环境下周期 性的多趟调度算法的数学模型。文献 3 4 1 研究了总线型的机群系统下的可分负载调度问 题，分析了启动开销对总线网络下可分负载调度的影响。文献 3 5 】研究了单级树型网络 的异构机群环境下的大规模可分负载的调度问题，机群的处理机节点速度、网络连路通 信速率以及相应的计算通信延迟都可能是不同的，并采用无阻塞的通信模式。文献 3 6 】 提出了一种自适应的策略，使用一种探针技术来估计相关网络参数的值，并使用这些参 数来取得最优的负载划分。文献 3 7 ，3 8 研究了机群环境下可分负载多任务调度问题，其 中【3 7 】研究了星型结构的机群环境下的多任务可分负载调度问题，并证明了多任务可分 负载调度问题是计算难的，只有一些特殊的情况下存在着多项式时间解。文献 3 8 】研究 了总线结构的异构机群系统下的多任务可分负载调度问题。文献 3 9 】研究了内存受限的 异构星型系统下等大小的独立任务的分配调度问题以及可分负载任务的调度问题，并证 明了简单的星型异构机群系统下有关调度的最小化调度长度和最大吞吐率的问题是n p 难问题。 文献【4 0 】对异构计算环境下的静态调度技术进行了研究，并对静态调度方法的局限 性进行了讨论分析。文献 4 1 , - 4 3 研究了有关稳态调度的问题。文献【4 4 】研究了存储受限 的可分负载作业调度问题。文献【4 5 】研究了多轮可分负载调度问题。文献 4 6 - - 4 8 在考虑 处理机实际计算能力和通信延迟不同的情况下，提出了异构机群系统的均匀多轮调度算 法u m r ，并获得近似最优的调度轮数。文献【4 6 】给出了u m r 的详细推导过程和实验结果 分析。文献h 8 的模拟实验表明，任务块的大小在调度过程中保持逐渐增大并不能有效 地抑制额外的开销。文献【4 9 】对文献【4 8 】的u m r 算法做了扩展，提出了一种健壮的均匀 多轮调度算法r u m r ，该算法考虑性能预测误差，对任务块按其大小先从小到大递增然 后再递减的次序进行调度分配，使得算法更加健壮。文献 5 0 】设计了一个由处理机运算 速度不同和异构网络互连的异构机群系统的已知资源的最优负载分布算法r a o l d ( r e s o u r c e - a w a r eo p t i m a ll o a dd i s t r i b u t i o n ) 。文献5 1 ，5 2 考虑了处理机的通信延迟，在异 构机群环境上设计了一个渐近最优的多轮调度算法，该算法易于实现，并在理论上第一 6 j h 勺和u 羊勇i 兢的胃分鱼载调矗l j i 嘲闱 电 次给出了多轮调度算法性能的定量分析。 文献 5 3 ，5 4 ，2 9 ，5 5 ，5 6 1 研究了存储受限的可分负载单论调度问题。文献 2 9 ，5 5 1 研究了 处理机通信延迟不同和存储受限的异构机群环境下可分负载的单轮调度算法。文献 【2 8 ，2 9 的研究分析结果表明，处理机通信延迟不同和存储受限的星型异构机群环境的可 分负载调度问题是n p 完全问题。文献【3 0 】证明了在仿射代价模型下，处理机计算速度和 通信能力不同的星型异构计算平台的可分负载调度问题是n p 完全的。文献【5 6 】研究了处 理机存储受限的单级树型网络的异构机群环境的可分负载调度问题，提出了增量平衡策 略算法i b s ( i n c r e m e n t a lb a l a n c i n gs t r a t e g y ) 。文献 5 7 】在文献 5 6 1 的基础上，研究分析了 处理机通信延迟不同和存储受限的多级树型网络的异构机群环境的可分负载调度问题， 设计了调度算法p p o l d ( p u l l - - p u s ho p t i m a ll o a dd i s t r i b u t i o n ) 。文献 5 6 ，5 7 提出的i b s 和 p p o l d 调度算法在每一次迭代时，都将填满一个处理机节点的内存，然后该处理机节点 将不再参与后面的迭代( 即剩余的任务调度) ，这两种算法都不能处理任务负载总量大 于机群系统总内存容量的情况。 上述提到的可分负载调度算法绝大多数都是针对没有带返回信息的情形下的可分 负载调度的研究。但是，实际应用中存在的一些应用在处理完任务后需要向中心处理机 节点返回处理结果的应用。返回结果信息的量可能比较大，甚至有可能比分配给相应处 理机节点的负载块还大，以至于返回结果信息的通信时间不能忽略，并对调度时间长度 有较大的影响。由于带返回结果信息的应用在现实中的普遍性和重要性，文献 【2 5 ，2 6 ，2 7 ，5 8 ，5 9 对带返回结果信息的可分负载调度问题进行了初步的研究。 相对于n p 完全的一般的d a g 任务图任务调度问题来说，可分负载调度在一定的假 设条件下可以得到闭式最优解或近似最优解，非常具有吸引力。同时可分负载调度也存 在着一些有待解决的问题。目前对于单轮算法研究得比较彻底，由于多轮算法比较难分 析等原因，对多轮算法的研究成果相对比较少，而且已有的算法中大多数是没有考虑计 算和通信延迟的同构环境下的调度算法。如何解决延迟问题、每一轮调度的负载块的大 小应该是多少以及应该调度多少轮的问题是多轮算法的三个有待解决和进一步研究的 问题，其中在考虑延迟情况下如何确定最优的调度轮数是一个关键的问题。 综上所述，异构机群系统下的任务调度问题已经成为调度问题的一个主要研究方向， 但目前国内涉及该领域的研究还不多。对于已有的机群环境下的可分负载调度算法存在 以下不足： ( 1 ) 已有的调度算法大多数是同构机群环境下的调度算法。其中，已有的异构机群 环境下的调度算法主要都是仅考虑异构处理能力，没有考虑到通信链路的异构性、计算 和通信的延迟问题、存储受限等问题。而实际环境中很多异构机群环境是由异构网络、 异构处理机、存储能力异构以及不同数目处理机的结点组成的。因此，研究适用于更加 符合实际的由异构处理机、异构网络、不同存储能力、处理机数目可变的异构机群环境 下的可分负载任务调度算法将更有意义。另外，现有的最好的异构机群系统下的调度算 法都是次优的调度算法，因此对于研究异构机群系统环境下更好的调度算法仍有很大的 7 囊柏审u 牛j ；统的角r 分血斌调度舅坤基研究 空间。 ( 2 ) 现有的调度算法中绝大多数是没有考虑返回结果信息的情形，而实际应用中 存在着许多应用在处理完后需要向中心处理机节点返回结果信息的情形。已有的考虑结 果返回信息通信的可分负载调度算法绝大多数都是同构机群环境下的单论调度算法或 者是调度轮数指定的同构机群环境下的多轮算法。而实际环境中很多异构机群环境是由 异构网络、异构处理机以及不同数目处理机的结点组成的，因此研究符合实际应用的考 虑返回结果信息的异构机群环境下的多轮可分负载调度问题具有非常重要的实际意义。 1 3 论文选题的目的和意义 异构机群系统利用工作站和个人计算机进行分布式并行处理，以较低的成本完成大 规模、复杂问题的计算处理。随着个人计算机处理能力的迅速增强和新的高性能快速网 络的不断出现，异构机群系统更显示出其较好的性能和实用价值。相对于单一的并行计 算机，异构机群系统具有很高的性价比，并且非常具有发展前景，但是同时也提出了许 多富有挑战性的问题，任务调度就是其中的一个基本问题。如果任务调度问题得不到有 效解决，那么可能导致异构机群系统效率低下，甚至可能不如单个计算机，严重的可能 导致计算失败。已有的异构机群系统下的调度算法大多是针对同构全互联的异构机群系 统，没有考虑到通信异构、存储异构以及计算和通信延迟等实际因素，因此研究考虑异构 网络、异构处理机、异构存储能力、不同处理机数目以及考虑计算和通信延迟情况的异 构机群系统的任务调度算法将更加有意义。 1 4 论文的主要研究内容 正如1 1 节所述，任务调度问题是机群系统应用中的一个很关键的问题，任务调度的 研究具有重要的理论意义和广泛的应用价值，这是吸引我们学习和研究它的根本动机也 是我们的兴趣所在。很多有着深刻影响的关系国民经济、国防科技等问题的重大课题对 计算能力的要求都非常高，解决这些问题需要有很高的计算能力的高性能计算机系统， 而从近年t o p 5 0 0 的高性能计算机系统可以了解到，目前的主流的高性能计算机系统是 机群系统。而实际应用中很多的机群系统具有异构网络、异构处理器和异构存储能力的 特性。另外，科学和工程领域中许多应用是由大量细粒度的独立任务构成的，即这些应 用可以划分成为任意数目和任意大小的任务块，因此这些应用易于直接并行化，特别是 在主从模式下，这一类应用也称为可分负载。因此异构机群系统上的可分负载调度算法 的研究将具有非常重要的意义。但是，如1 3 节所提到的，异构机群环境下的可分负载调 度问题是n p 完全问题，这向人们提出了设计更优的异构计算环境下的可分负载调度算法 的挑战。1 3 节的对有关可分负载任务调度的研究成果的总结和分析表明：现有的最好的 异构机群系统下的调度算法都是次优的调度算法，因此对于研究异构机群系统环境下更 8 广冒r ，“# 习n b 掣啦铽”乞 累韵事u 羊膏| 躐的胃臂负载调度算嗣a f 究 好的调度算法仍有很大的空间，如果我们继续努力研究和探索异构机群环境下的可分负 载调度问题，那么改进某些已有的结果或者获得一些新的结果仍然是有可能的。 结合1 3 节的分析，我们将研究以下问题： ( 1 ) 异构机群环境下存储受限的可分负载多轮调度问题 任务调度问题是机群系统中的一个基本的问题，也是一个非常关键的问题，如果解 决不好调度问题，将可能导致机群系统效率低下，甚至可能不如单个计算机，严重的可 能导致计算失败。已有的异构环境下的可分负载多轮调度算法绝大多数都是同构的调度 算法，y a n gy a n g 等人提出的u m r 异构环境下的多轮调度算法、0 。b e a u m o m - 等人提出的 近似最优的周期性的多轮调度算法都没有考虑到实际机群的各个处理机节点的内存是 有限的这一实际情况。为此，我们将研究由异构处理器、异构网络构成的具