（计算机应用技术专业论文）网格计算环境中的动态任务分配和调度算法的研究.pdf

中文摘要 v 6 5 7 4 8 5 中文摘要 网格的出现是在近些年计算机科学技术的长足发展与网络技术的广 泛应用的背景下出现的，怎样利用现有资源解决大规模复杂计算问题成 为计算机领域的研究重点，而网格技术就是解决这个问题的一种技术。 二十世纪九十年代，围绕网格的相关研究和项目开始展开。这一技术结 合并行与分布式处理技术，通过高速网络连接并集成广域网上丰富的计 算机资源，利用分布、异构的各种高性能计算机、大型数据库系统、科 学仪器和各种软件系统等，实现跨地域的、并行分布式联合计算，共同 完成重大科学领域的大规模计算问题。 网格计算环境是一种异构计算环境，在此环境下的任务调度的决策 直接影响应用程序的运行性能。而并行任务调度的一个主要目标是达到 负载平衡，在执行过程中充分利用并行系统的资源。在网格环境中，并 行系统本身非对称带来的复杂性、多用户环境以及并行任务粒度较粗等 因素给负载平衡问题的解决带来了新的困难。本文围绕如何在网格环境 中平衡负载这一目标，对进程级并行任务的动态调度问题进行了的研究， 设计并实现了一个基于p v m 的动态负载平衡调度系统。该系统采用了静 态程序分析、自适应数据采集与交换算法，以及多用户共享等技术，改 善应用程序在网格环境中的执行性能，该系统具有较高的透明性、较好 的可扩展性和移植性等特点。 关键词：网格，调度，负载平衡 外文摘要 a b s t r a c t g ow i m r a p i dd e v e l o p m e n to fc o m p u t i n gs c i e n c ea n db r o a da p p l i c a t i o n o fn e t w o r k t e c h n o l o g y , g r i da p p e a r si nt h el a s tf e wy e a r s h o w t os o l v et h e l a r g es c a l ea n dc o m p l e xc o m p u t i n gp r o b l e m su t i l i z i n gr e s o u r c e si ne x i s t e n c e b e c a m eah o tt o p i ci nc o m p u t i n gf i e l d ，g r i d j u s ti sat e c h n o l o g y t os o l v et h i s p r o b l e m i nt w e n t yc e n t u r y9 0 s ，as e r i e so f r e s e a r c ha n dw o r k ss p r e a d t h e g r i dc o m b i n e sp a r a l l e la n dd i s t r i b u t e dp r o c e e d i n gt e c h n o l o g y , a n dc o n n e c t s w i t ha n di n t e g r a t e st h ea b u n d a n tr e s o u r c ei nw a np a s s i n gt h r o u g ht h e h i g h - s p e e dn e t w o r k t h eg r i du t i l i z e sk i n d so f d i s t r i b u t e da n d h e t e r o g e n e o u s c o m p u t e r s ，l a r g es c a l ed a t a b a s e s ，s c i e n t i f i ci n s t r u m e n t sa n d s o f t w a r es y s t e m s ， a n di tr e a l i z e sd i s t r i b u t e d ，p a r a l l e la n da l l i a n c ec o m p u t i n g ，a c h i e v i n gl a r g e s c a l ec o m p u t i n g p r o b l e m s i ns c i e n c ef i e l d t h eg r i dc o m p u t i n ge n v i r o n m e n ti sak i n do fh e t e r o g e n e o u sc o m p u t i n g e n v i r o n m e n t ，t h ed i s p a t c h f o rt a s k si nt h ee n v i r o n m e n tc a ns t r a i g h t l y i n f l u e n c ep e r f o r m a n c eo f a p p l i c a t i o n s ap r i m a r y a i mt op a r a l l e ld i s p a t c hf o r t a s k si st or e a c hl o a db a l a n c e ，a n dt a k ef u l la d v a n t a g eo f t h ep a r a l l e ls y s t e m s r e s o u r c ei n r u n n i n g ，i ng r i de n v i r o n m e n t ，t h ep a r a l l e ls y s t e m s i n h e r e n t c o m p l e x i t y , t h em u l t u s e re n v i r o n m e n ta n dt h el a r g eg r a n u l a r i t yo fp a r a l l e l t a s k sa n ds oo n ，b r i n gn e w d i f f i c u l t yt ol o a db a l a n c e t h i sa r t i c l ei sa b s o r b e d i nt h ea i mh o wt ob a l a n c el o a di ng r i de n v i r o n m e n ta n de x p l o r et h ed y n a m i c d i s p a t c h t ot h ep a r a l l e lt a s k si nt h ep r o c e s sl e v e l ，a tl a s td e s i g n sa n dr e a l i z e sa d y n a m i cd i s p a t c hs y s t e mw i t hp v m t ol o a db a l a n c e t h j ss y s t e ma d o p t s q u i e s c e n tp r o g r a ma n a l y s i s ，s e l f - a d a p t i v e d a t ag a t h e r i n ga n de x c h a n g i n g a l g o r i t h m a n dm u l t - u s e r ss h a r i n ga n ds oo nt e c h n o l o g i e s 1 1 1 i ss y s t e mc a n i m p r o v e t h ep e r f o r m a n c eo f a p p l i c a t i o n sr t m n i n g i ng r i de n v i r o n m e n t ，i th a v e ab e t t e rt r a n s p a r e n c y , e x p a n s i b i l i t ya n d p o r t a b i l i t ya n d o t h e rw i s ef e a t u r e s k e yw o r d s ：g r i d ，d i s p a t c h ，l o a db a l a n c e 1 i - 第1 章引言 第1 章引言 1 1 网格计算环境 很久以来，人类就懂得并行处理的优越性。一些术语如调度、流水 线等在计算机远没有出现之前就被使用了。现代意义上的并行计算始于 二十世纪六十年代。其间，并行处理系统无论从硬件体系结构还是软件 开发环境来说，都有了长足的进步，并且已经成为现代计算机发展的主 流。其中，m i m d 计算机模型由于其可扩展性好，通用性强，以及能够 丌发小至单个作业，大至多个作业的并行性而受到研究人员以及厂商的 普遍重视 1 1 。m i m d 计算机包括两大类；基于共享存贮的m u l t i p r o c e s s o r 基于消息传递的m u l t i c o m p u t e r 。 工作站机群系统，是指用局域网连接的独立工作站组成的并行计 算机系统。它的特点是各结点独立运行自己的操作系统，灵活性高：结 点处理能力强，资源为多用户共享。工作站机群系统之所以越来越受到 重视，最初有两方面的原因。一方面，交换开关网络与快速以太网的发 展从带宽上保证了系统的扩展性，同时提供了基于低开销通信协议的快 速通信。而且，单个工作站的性能在迅速提高，其性价比以每年8 0 的 比例增长( 与此同时，s u p e r c o m p u t e r 的增长速度仅为2 0 到3 0 ) 旺i 。 这样就给用户提供了个用廉价的n o w t ；l 而不是m a i n f r a m e 或 s u p e r c o m p u t e r 来完成大规模计算的机会【4 1 。另一方面，各个实验室、公 共机房以及公司现有的用传统的l a n ( l o c a la r e an e t w o r k ) 技术如 e t h e m e t 连接起来的各类工作站和p c 的资源也可以被充分地利用起来。 目前，随着因特网的迅速发展以及分布式处理技术的进一步成熟，工作 站机群系统逐渐被应用到诸如数据库、w e b 服务器等更广+ 泛的领域，成 为当前并行处理的个重要方面。 黑龙江大学硕士学位论文 近些年随着计算机技术的发展，特别是随着i n t e m e t i n t r a n e t 技术的 兴起和广泛应用，网络应用已经遍布了整个世界。与此同时许多大规模 科学计算和复杂的应用系统也正向高性能、多功能和多样化发展，这不 仅需要一台或凡台超高性能的计算机，更需要由多种计算机组成、多个 系统合作、多个科学奠器设备相连的网络虚拟超级计算扰。这就要求将 地理上分布、异构的多种计算机资源通过高速网络连接起来，共同完成 重大科学领域的大规模计算问题和其它复杂的任务等，而网格( 鲥d ) 就 是解决这一问题的技术。网格产生与二十世纪九十年代，其间有一系列 的相关项目开展。这一技术结合并行与分布式处理技术，通过高速网络 连接并集成广域网上丰富的计算机资源，利用分布、异构的各种高性能 计算机、大型数据库系统、科学仪器和各种软件系统等，实现跨地域的、 并行分布式联合计算，共同完成重大科学领域的大规模计算问题。网格 的出现和进一步发展，将对各种大规模复杂计算，i n t c m e t 等产生巨大的 推动的作用。 网格是一个计算环境。现有的资源，诸如网络、超级计算机、服务 器、操作系统、数据库、文件系统等都是网格计算的底层设施，而应用 程序通过网格计算调用、共享网上资源来完成任务。而对并行任务的任 务管理、任务调度和资源管理是网格计算中的基本功能也是研究的难点 和重点，这是由于网格的底层设备的分布和异构性所造成的。现有的国 内外对此环境下的任务分配和调度算法的研究，还有待深入。 1 2 负载平衡 并行的根本目的就是为了加速。人们期望r 1 个结点的并行系统比单 台计算机快n 倍。这在现实情况下往往是达不到的，甚至相差甚远。很 明显，用于并行计算的各个结点不能充分发挥它们的处理能力。这种情 况当应用程序结构比较复杂时表现得更为严重。因此，在并行处理系统 第1 耄引言 中，如何提高各个结点的利用率，是影响运算性能的关键。实践中常常 出现这样的情况：当一些结点忙于计算的时候，另外的一些结点却处于 空闲状态。这当然大大降低了结点的利用率。这样，负载平衡就成为改 善并行性能的一个重要手段。 负载平衡的基本目标是通过任务调度，使运算均衡地分布在各个结 点上，从而提高系统资源( 主要是c p u ) 的利用率。另外，不同的应用 场合对负载平衡有着不同的特殊要求，如：在实时系统中，必须满足对 响应时间的严格限制：在多用户的系统中，必须保证在线用户对自己的 工作站的使用优先权等等。同时，影响负载平衡的因素也很多：应用程 序的并行模式、并行系统结点的数量以及网络的结构甚至用户的数量都 与之有关。负载平衡的复杂性与重要性使得它的研究工作受到了广泛的 重视，大量基于各种不同条件的负载平衡方法被提出。总的来说，这些 方法按照任务调度的时机来划分，可以分为静态与动态两类；按照调度 的控制策略来分，可分为集中式与分布式；按照调度的发起策略来分， 可分为发送者发起与接受者发起：而按照是否被抢先来划分，又可分为 抢先式与非抢先式等等。 机群系统是一类具有其自身特性的并行系统。机群系统下的负载平 衡，要达到的目的主要有以下两个方面： 1 、资源共享。观察表明，许多公司和科研单位的工作站在大部分时 间早基本处于空闲状态。即使是在利用率较高的时间段，也有相当数量 的机器空闲。采用负载平衡技术，将作业分配到空闲工作站上运行，既 能缩短作业的平均响应时间，又能显著提高了工作站的利用率。目前， 这方面的研究已经进入实用的商品比阶段。比较著名的产品有：i b m 公 司的l l ( l o a d l e v e l e r ) 1 6 1 ，p l a t f o r m 公司的l s f ( l o a ds h a r i n g f a c i l i t y ) m m 等。这一类负载平衡系统的设计中必须解决的重要问题有：如何测量 黑龙江大学硕士学位论文 与评价工作站的空闲情况；如何保证前台用户对工作站的优先作用权； 如何迁移作业；如何在发生故障的情况下恢复作业的运行；如何提供对 用户完全透明的使用界面等。 2 、提高并行性能。此类负载平衡面向的是计算密集型的并行程序， 目的只有一个：即缩短程序的运行时间。由于并行模式的多样性，这方 面的研究工作也相应地比较多，如：c a l y p s o t 9 j ，c a r m i t l 0 】( 1 1 1 ，c o n d o f 3 1 等。 系统设计中的主要问题包括：如何预测并行程序的执行状况；如何测量 与评价工作站的空闲情况；采用何种任务调度方式；是否以及采用何种 方式进行任务迁移：如何容错等。是否以及采用何种方式进行任务迁移； 如何容错等。 下面对以上提到的负载平衡需要解决的问题作一个简要的叙述： 负载状况评测。能够直接获取的负载信息有：c p u 利用率、就绪队 列长度、内存利用率等。一个好的负载指标应当具有如下特点； 1 ) 能够准确反映当前负载状况。 2 ) 可以预测短期未来的负载。 3 ) 相对稳定，不频繁波动。 4 ) 与结点的当前性能有简单的转换关系。 通常，必须对直接获得的负载数据进行必要的转换，以得到符合标 准的负载指标。例如，f e r r a r i 和z h o u 根据实践经验，指出平滑的平均资 源队列长度是一个较好的转公式小】： q i = q i l ( 1 一e ) t + - t ，i 1 ；q o = o 其中q 为当前资源队列长度，q 为指数平滑平均队列长度，t 为时 间间隔。资源可以是任何可用资源，如c p u 资源，也可是综合资源。需 要注意的是，负载与可用资源的关系是反作用的。资源越少，负载越重。 此外，考虑到异构机群系统的各个结点处理能力并不一样，在评价负 第1 章引言 载状况时，必须引入能够表示异构性的参数。 任务调度方式。任务调度有静态调度与动态调度两大方式。静态算 法对于应用程序中的各种信息( 如并行任务大小，前趋关系，任务问通 信量等) 以及并行系统的情况( 网络拓朴结构，各处理结点计算能力等) ， 在程序运行前就已得到，并以之为依据完成任务分配方案，程序运行时 完全按该方案执行。静态算法能给出较优的调度方案，但要求有完整的 任务关系图。然而在机群系统中，特别是在多用户方式下，各结点的负 载具有动态性，很难作出准确的预测。动态调度是在并行程序运行时通 过分析系统的实时负载信息，动态地将任务在各结点之间进行分配和调 整，以适应实时多机系统中负载分布的不均匀性。由于各结点上的任务 是动态到达的，因此在程序执行期间，某个结点上的负载就可能突发性 地增加或减少。这时，重载的处理机应及时地把多余的任务分配到轻载 的处理机上去( 或者轻载的处理机及时地向重载的处理机申请任务) 。动 态负载平衡的优点是算法简单，实时控制。缺点是增加了额外的调度开 销。 任务迁移。对于动态调度来说，由于负载变化的不确定性，任务的 分配不能保证准确。因此当负载失衡的情况下，需要对已做出的调度进 行某种程度的修正。任务迁移主要有两种形式：操作系统进程级迁移和 用户级迁移。进程级迁移可以将执行过程中的进程转移到其它结点继续 执行，这不仅需要传递许多与进程相关的数据，还要维持通信的完整性， 而且很难在异构结点之间实现啡1 ：用户级迁移将用户定义上下文数据结 构进行转移，对这些数据的管理引入了额外的开销，但能够实现异构结 点间的迁移f ，日。 另外，机群系统性能评价、并行处理模式、应用问题特征分析等也 是负载平衡研究中十分重要的课题。 黑龙江大学硕士学位论文 1 3 论文组织及贡献 论文组织如下： 第一章概述了并行处理和机群系统的发展现状，以及当前网格计算 的发展概况。讨论了负载平衡的重要性以及相关的课题，并对论文结构 与主要工作进行介绍。 第二章对相关工作进行综述，分别阐述了目前负载平衡算法，相关概 念和系统的研究状况，讨论了机群系统并行环境下负载平衡具有的特点， 并对典型的负载平衡系统进行了介绍和比较。 第三章讨论了非抢先动态调度的特点，提出并实现了基于p v m 环境 的非抢先负载平衡调度系统。该系统针对机群系统任务调度中存在的准 确性差、额外开销大等缺陷，采用了静态分析、自适应采样间隔、负载 信息一致性算法等优化策略，实现了一个低开销、高性能、使用灵活的 运行时调度系统，明显地改善了动态p v m 程序的性能。 结论中对论文进行总结并展望进一步的工作。 论文的主要贡献：设计并实现了基于p v m 的动态负载平衡调度系 统。该系统针对机群系统调度存在的任务分配准确性差、开销大等缺点， 采用了静态程序分析、自适应数据采集与交换算法，以及多用户共享等 技术，改善应用程序的执行性能。此外，它还具有较高的透明性、较好 的可扩展性和移植性等特点。用户无需对应用程序和p v m 系统做任何改 动即可在需要时加载该系统，而在不需要时将其卸载。 第2 章负载平衡技术 第2 章负载平衡技术 由于负载平衡对并行性能的重要影响，这一领域的研究工作十分广 泛，而且，许多技术已经应用于实际系统。下面首先对负载平衡进行分 类综述，然后重点分析静态与动态调度算法，以及实现负载平衡系统的 具体技术，提到了负载平衡度的概念。最后讨论机群系统的特点，并对 一些典型的负载平衡系统的实现和性能特点进行了比较。 2 1 负载平衡方法的分类 负载平衡方法按照不同的应用场合可以有多种分类方法，下面就分 别按照实时与非实时、抢先与非抢先、静态与动态三个角度对各种负载 平衡方法进行讨论。 实时与非实时 在实时系统中，任务调度的最主要目的是保证任务在限定时间内完 成，其次才考虑性能问题，负载平衡算法必须服从实时f 生要求【】7 1 【”】。时间 限制有绝对和相对两种。绝对时间限制要求任务必须在一个特定的绝对 时间点之前结束：相对时间限制则提出相对时间要求，例如在任务就绪 后一定时间内结束。 实时系统中的负载平衡算法主要有：基于时间调度，静态基于优先 级调度，动态基于优先级调度，和时间间隔受限调度。 在非实时系统中，调度的主要目的是提高性能，因此，负载平衡是 重要的指标。这时，负载平衡方法又可以按抢先与非抢先，静态与动态 来进一步划分。 抢先与非抢先 在并行程序运行过程中允许一个业已分配的任务中断执行，并重 新对其进行调度，从而达到负载平衡的方法被称为抢先方式；任务一旦 黑龙江大学硕士学位论文 被分配到某个处理机，就不再改变该分配决定，被称为非抢先方式。 抢先的负载平衡方法的优点：允许系统在出现负载不均衡时对已有 的调度决定进行修正，这在程序行为不可预测的情况下或者运行环境动 态变化时能够及时调整分配方案。然而，抢先方法在实现上有其复杂性： 首先，任务被抢先调度后的进程迁移工作开销较大：其次，并行任务之 间的同步与通信使得维护迁移之后程序的正确性变得困难而且效率低 下；再次，在异构处理之间进行操作系统级的进程迁移是难以实现的。 任务抢先调度除了在操作系统的进程和线程级实现之外，还可以在 用户层次加以实现。这需要调度系统对并行任务的全面管理。这种用户 层次的实现还用利于完成异构系统之间的任务迁移。 在非抢先的负载平衡方法中，无论是在运行前还是在运行时作出调 度决策，任务一旦被分配至0 某个处理机，就必须在该处理机上执行直到 结束。非抢先的方法只考虑任务的分配，不涉及任务的再分配和迁移， 因此其实现较为简单，开销也较小，同时灵活性较大，比较适合相对简 单的应用程序，以及异构的软硬件环境和多用户系统。对于较复杂的程 序，非抢先调度则不容易达到理想的性能指标。表2 - i 列出了抢先与非 抢先调度的主要特点和区别。 表2 - 1 抢先与非抢先负载平衡方法对比 抢先非抢先 系统复杂程度复杂，开销大简单，开销小 适用范围复杂的软硬件环境，同行为简单的程序， 构异构 达到负载平衡的基本能达到有时达不到 程度 包括对任务的分配，迁包括对任务的分 实现技术移；对系统当前状况的配；对系统的监测 监测 第2 章负载平衡技术 静态与动态 从调度决策的时机来划分，负载平衡算法可分为静态算法和动态算 法。对静态算法来说，应用程序中的各种信息( 如任务大小、前趋关系， 任务间通信量等) 以及并行系统的情况( 网络拓扑结构，各处理结点计 算能力等) ，在程序运行前就已得到，并做好任务分配，然后再开始运行 程序。静态算法要求有完整的整的任务关系图，但在高度并行的多计算 机领域，特别是在多用户方式下，各处理机上的负载是动态地到来的， 不可能作出准确的预测。静态算法又分为求最优解和次优解两类。最优 解问题是n p c o m p l e t e 问题，只有在一些特殊的情况下才存在复杂度为 多项式的解法。求次优解又分为两类：近似法就是对系统模型施加一定 的限制条件，从而降价算法的复杂度；启发式方法则利用一些启发函数 进行试探求解。动态负载平衡通过分析系统的实时负载信息，动态地将 任务在各处理机之间进行分配和调整，以适应实时多机系统中负载分布 的不均匀性。由于各处理机上的任务是动态到达的，因此在程序执行期 间，某个处理器上的负载就可能突发性地增加或减少。这时，重载的处 理机及时地把多余的任务分配到轻载的处理机上去( 或者轻载的处理机 及时地向重载的处理机申请任务) 。动态负载平衡的优点是算法简单，实 时控制。缺点是增加了系统的调度开销。动态调度可分为集中式和非集 中式”。非集中式( 分布式) 调度由各结点分别进行，它又可分为合作 型 z o 】c 2 1 1 ，即调度基于整个系统状况，以及非合作型，即调度基于局部信 息两类。 2 2 静态调度算法 静态最优调度算法 静态算法中的最优解算法有四种：图论法、数学法、解空间计数搜 索法和队列法。其中图论法是有代表意义的。以下简单说明图论法的常 黑龙江大学硕士学位论文 用算法。在图论法中，两种模型分别用来表示系统和任务，即系统图和 表2 2 静态与动态负载平衡分类 次优启发式 静态近似 最优 集中式 负载平衡 最优 动态分布式合作 次优l堑型 l启发 非合作 任务图，见图2 1 。 系统图中的结点表示处理机，结点旁的数字表示其计算能力，结点 间的连线表示网络的物理连接。我们可以看到，系统图所表示的是一种 简化的异构系统模型。它可以提供影响系统性能的主要参数信息。任务 图中的结点表示任务，横线上的数字为任务编号，横线下的数字表示任 务粒度。连线表示执行的偏序关系( 即a b 表示a 执行后b 才可执行) ， 连线上的数字表示通讯量。 系统图任务图 图2 1 系统图与任务图 g a n t t 表格可以用来表示任务在处理机上的分配与运行。图2 2 是一 个g a n t t 示例图。其中并行任务t l 、t 4 和t 2 、t 3 分别在处理器p 1 和p 2 第2 章负载平衡技术 上执行。图中空白部分表示c p u 空闲时间。这种空闲可能是任务间的通 信或同步造成的。 处理器 p 1 p 2 时间 图2 2g a n t t 示例图 调度问题是n p c o m p l e r e 问题。要想使任务的完成时间最短，任务 在处理机上的分配算法是指数复杂度型的。当忽略通信开销时，只有满 足以下三个条件中的一个，才可得到多项式时间复杂度算法1 2 2 】： ( 1 ) 树型任务图； ( 2 ) 只有两个处理机； ( 3 ) 间隔顺序任务图。 从以上介绍可以看出，最优算法实际上只能解决几类特殊情况的问 题，因此，其用途主要是作为理论工具，而很少能用于实际系统。 静态次优算法 静态启发式方法 这类方法可以快速、有效地得到次优调度。针对预先知道的信息( 包 括任务粒度，任务间通讯量，任务执行偏序关系以及系统限制) ，采用非 解析的、近似的、逐步逼近的试探方法寻找近似最优解，是此类方法的 共同特点。，u 和s w e e t i n g 提出的静态启发式任务分配算法l ，比较有 代表性，适用于大粒度并行任务和基于消息传递的系统。该算法中信息 表示如下所列： ( 1 ) 任务开销矩阵c ；( 。) m m c i ：表示i 执行时间，( i = 1 2 ，m ) 。 。u ：当任务i 和任务j 不在同一台处理积上时i 向j 发送数据的 黑龙江大学硕士学位论文 通讯时间，( i j ) 。 m ：任务总数。 ( 2 ) 己分配任务集p j ： i i 任务i 被分配到处理机j ) ，( j = 1 2 n ) 。 n ：处理机数。 ( 3 ) 处理机负载( 包括通讯开销) = c 。+ p 吱+ + ，( ，= 1 ，2 ，) k e p jk 8 p ik e p l j t p | e c k ：表示任务k 与相关外设的通讯时间。 ( 4 ) 负载平衡函数： p k 一“= r a i n m a x p l 。 分配算法就是要找到个m 个任务对n 台处理机的映象a ，使得 既达到负载均衡，且总负载最小。 负载平衡的任务分配算法分为两步，第一步称为任务簇算法( t c a ) ， 可描述为： 1 、取n 个任务，分别分配到n 个处理机。 2 、找到负载最轻的处理机k 。 3 、从未分配的任务中，找出使处理机k 的负载增加量最少的任务s 。 4 、将s 分配给处理机k ，修改k 的负载值p l k 。 5 、如果任务分配完毕，转第二步：否则转2 。 第二步称为任务分配算法，它是为了调整t c a 之后仍然存在负载不 均问题，描述如下： 1 、对n 个处理机按负载排序，使m 1 p l 2 p l n 。 2 、找出这样的任务s e 删和处理机v ，满足当s 重分配至uv 上之 后n 和v 的负载最小。 ：、若s 的重分配使得负载情况比重力、配之；j 还重，则算法结束； 第2 章负载平衡技术 否则，将s 重分配到v ，转1 。 需要注意的是最初n 个任务的选择将影响最终结果的好坏，因此该 算法要求最先选取的n 个任务必须是开销最大的n 个任务。 从上述算法可以看到，启发式方法可以在限定时间内求次优解，但 它受初始值的影响比较大，因此有可能找不到较好的解。 静态遗传算法 遗传算法的基本过程是f “，： ( 1 ) 初始化：将问题的解定义为基因串，随机产生第一代基固。 ( 2 ) 计算适应函数值。 ( 3 ) 遗传操作：根据适应函数值使用遗传算子产生下一代基因。 ( 4 ) 重复( 2 ) 和( 3 ) 直到算法收敛。 总的来看，虽然静态调度算法没有考虑系统的不可确定因素，但由 于在编译时可以完成调度，对于大型应用程序的性能提高起着重要作用。 在实际应用中，如果能与动态算法结合使用，则可能取得更好的效果。 2 3 动态调度算法 1 集中式控制与分布式控制算法 集中式负载平衡控制一般通过m a s t e r s l a v e 的方式来实现，最典型 的是任务池( p o o lo ft a s k s ) 方法由m a s t e r 创建和维护任务池( 一般组 织成队列形式) ，并向空闲的s l a v e 处理机分派任务。如果每个任务粒度 不同，则粒度较大的任务一般处于队列头部。m a s t e r 以贪心分配的原则 管理各s l a v e 。p v m 环境下的应用程序很多采用此类负载平衡方法是换 维平衡法，该方法是一种全局控制的、完全同步的策略。它首先将n 个 处理机组织成l o g 维，然后每次在某一维的处理机集合中进行负载平衡。 通过更换不同的维的处理机集合，利用维与维之间处理机的重叠特性， 达到全局负载平衡的效果。集中式负载平衡在并行处理系统规模较大时 黑龙江大学硕士学位论文 i 可能会出现瓶颈现象。 在分布式负载平衡控制中，所有的处理机均进行调度，其依据既可 以是整个系统的信息，又可以只是局部信息。要想获得精确的控制，系 统必须掌握足够多的实时信息，而这又意味着要以沉重的通信开销作为 代价。因此，常用的几种分布式动态负载平衡策略往往就在这两者之间 取得折衷方案。分布调度主要分为两类：发送方发起方式( s d 和接收 方发起方式( i u ) ，另外还有分层负载平衡方法和梯度模型 2 5 1 。 s i 方式 s i 策略利用处理机邻域的负载信息，由重载处理机主动发起负载平 衡，将过多的负载送到邻域中的轻载处理机上因此它是一种高度分布的 方案。在s i 系统中，全局负载平衡通过重载区域向轻载区域扩散负载来 实现。这里有两个主要问题：如何确定一个处理机负载己达到阈值或如 何选择任务要送到的结点。s i 方式在系统平均负载轻轻的情况下更有效。 r i 方式 i u 方式又称为选拔法，在r j 系统中，负载平衡由轻载处理机主动 发起申请，邻域中的重载处理机在收到该申请后，将适量的负载传递给 轻载处理机。由于轻载处理机承担了绝大部分负载平衡的开销，因此r j 方法在系统平均负载较重的情况下性能较好。i u 方式采用重叠域思想， 是目前分布式负载控制技术中，特别适合于支持大规模并行系统解决各 种应用问题的优选方法。其原理可简单描述如下： 1 、系统中任一处理机i 的负载量低于某一阈值后，即启动该处理机 所在区域d ( i ) 的负载平衡进程： 2 、区域d ( i ) 中的处理机p 在接到处理机i 的负载申请时，最多只把 自身负载的一半给处理机i 。 下面给出形式化描述：设 第2 章负载平衡技术 厶。，厶。为两个预置可调的阈值： d ( i ) 为处理机i 所在的局部区域，其中i d ( ，) l 表示该区域的连接度， 即与i 相邻的处理机个数； 上( p ) 为处理机p 的负载量； 厶为区域d 的平均负载量； h t ( p ) 为处理机i 获知的关于处理机p 的超载量； r t ( p ) 为轻载处理机i 向重载处理机p 的申请的负载量； l i ( p ) 为处理机i 获知的关于处理机p 的负载量，一般通过定期的负 载信息刷新来获得： g ，( p ) 为p 实际传递给i 的负载量： 存l i 2 南，磊，以力 h a p ) ：p _ 厶j 鹦( p ) 0 ，0 t h e r w i s e 令q = 岛一( p ) ，则当处理机i 的负载量l ( i ) 低于乓。时，i 计 胆d ( ，) 算其所需的负载量d ，= i 一三( ，) ；如果d ，超过阈值k 。，则处理机i 即 向区域d ( i ) 内的其他处理机p 申请负载_ ( p ) ，砌d ( ，) ，其中 咖) = d i 半 根据策略，有： _ ( p ) ，( p ) 上( p ) g ，( p ) = 三( p ) ，o t h e r w i s e 2 ，分层负载平衡方法 黑龙江大学硕士学位论文 分层负载平衡方法是一种异步控制的、全局性的方法。它将系统组 织成一个层次式的控制结构，负载平衡由最底层的处理机发起，逐渐向 高层传递。每一层的负载实行集中控制，最高层控制全局的负载平衡。 3 梯度模型 该方法基本思想是首先由轻载处理机向其它处理机报告它们的负载 状态，重载处理机根据系统维护的负载梯度表。向离它最近的轻载处理 机派送部分负载。 在负载平衡系统的实现中，为适应系统的复杂性和负载的变化性， 往往采取具有可适应性的综合方法。如i u 和s i 相结合的分布式负载平 衡系统，是在系统平均负载超过某个阈值时，启动i 己i 算法：反之，使用 s i 算法；采用网络划分，目的是在处理机数量很大或系统分布在地理上 不匀衡情况下有效地进行负载平衡，有组内调度，组间调度，交换成员， 共享成员等不同策略；还有动态与静态相结合的方法等。 2 4 实现负载平衡所需的工作 负载平衡的实现其涉及面较广，相关的技术包括毗下几个主要方面； 1 、调度算法 在大多数情况下，调度算法承担了负载平衡实现中最主要的工作。 调度算法具有很强的针对性，由于应用程序和并行环境不同所导致的性 能差异较大。 2 、负载评价 负载评价分为两种：对并行任务的负载量的计算，和对当前并行系 统的负载量的计算。如何判断负载平衡的程度，直接影响到调度算法的 决策。 3 、运行时系统 对于动态负载平衡和某些静态实现来说，运行时的支持是必须的。 第2 章负载平衡技术 在动态系统中，无论是抢先还是非抢先调度，都需要在运行时监视并行 系统的负载变化，作出分配决策或任务迁移决策。 4 、反馈与修正 在抢先调度中，根据当前状态对现有的调度方案进行修正是保证负 载平衡的重要环节。这种修正称为任务再调度或再分配。 2 5 网格环境中的并行调度与负载平衡 工作站机群系统是随着网络技术的迅速发展而出现的一种网络并行 计算系统。它的主要特征包括： 机群系统中各工作站相对独立。它们运行各自的操作系统，有独立 的内存和硬盘，能够单独运行应用程序，拥有与用户进行交互的能力。 工作站间通过网络连接。工作站能够通过网络进行通信。没有专门 的机制对通信进行统一管理，操作系统也不提供额外的消息一致性保证。 组成机群系统的工作站可以是异构的。异构包括硬件异构和操作系 统软件异构。异构的工作站在指令、程序代码、数据表示以及处理性能 上都可以有所不同。 工作站机群系统在并行处理中既可以是分时的又可以是分区的。机 群系统在运行多个并行程序对可以有很大的灵活性，这完全取决于用户 对并行程序的管理方式。 多用户共享。机群系统既可以按照独享方式，又可以按照共享方式 来运行并行程序或串行程序。 下面分别从几个方面讨论机群系统负载平衡的相关问题。 1 异构性与多用户 一个异构的机群系统( h e c ，h e t e r o g e n e o u sc l u s t e r ) 可以抽象为一个 连接图h c ( m ；c ) 。其中，m = m l ，m 2 ，r n = m m 为异构工作站结点集 合，其中每个结点的处理能力取决于它的c p u 数据、c p u 计算能力、内 黑龙江大学硕士学位论文 存容量、i 0 和内存访问速度，以及操作系统等。c 代表工作站的互联网 络，通常为e t h e m e t 或a t m 等。由于系统可能由一些子网互联组成，结 点到结点间的网络带宽和冲突的可能性因而不尽相同，为简化起见，可 以采用m x m 的通信带宽矩阵来表示结点间的相互通信能力的大小： c =，该矩阵是对称阵。 基于以上定义，当组成机群系统的各个结点在硬件和操作系统上保 持一致，且任意结点对之间的通信带宽相同，则异构机群系统蜕化成为 同构机群系统。 另外，异构机群系统还可按照用户情况分为两类：独享系统和共享 系统。在前者中各个结点只为同一个并行程序服务，而在后者中结点为 多用户的多个并行或串行程序所共享。 异构机群系统的性能 设a ( i ) 为一个规模为i 的并行应用程序，简记为a ，工作站结点 m i 运行a 时的速度为置( 锄。我们定义w 为m 运行a 时的处理能力系 数： 形( a ) = s ( 4 ) 蚂( a ) ) d = l ， e n 相对于最快结占的处理速霞。w ( a ) 1 w 如果设t ( a ， t ) 为结点m 。执行程序a 的时间，则处理能力系数还可 表示为： 彤( 一) = 卿n r ( 爿，m ) t ( a ，m ) i = 1 ，m ， q2q o 吨 第2 章负载平衡技术 对于程序a ，独享异构机群系统h e c 的固定负载加速比定义为： m i 罂 t ( a ，m ) s ( 4 、= 2 ：= 一 一t ( a ，h c ) 显然，对于是处理能力系数相差很大的机群系统来说，加速比不会 太好。 同样，我们可以定义异构机群系统的并行效率。在同构环境下，并 行效率被定义为e 阶a 警= 蒜，其嘲研吲跚别为单 结点和m 结点运行程序a 的完成时间。异构情况下，我们将处理能力系 数引入定义： e ( 爿) ：半m i n l t ( 一a m j ) ：掣 + t ( a ，h c ) 2 多用户环境 由于机群系统往往是共享的，多用户环境是常见的环境。在单个用 户或多个用户的多个串行或并行程序( 称为作业) 同时在机群系统上运 行，即所谓的多道程序环境下，要保证各作业占用资源的公平性和优先 级( 如主控台用户的交互式作业响应时间要短) 。通过合理调度，保证整 个系统的并行利用率。 3 通信与负载平衡 机群系统一般由局域网或多个局域网互联组成。常用的局域网络技 术有两类。一类是共享介质网络，在这种网络中，理论上的聚合网络频 带与单独的链路频带是一样的，其性能随网络负载的增加而下降。另一 类是开关网络，这类网络理论上的聚合网络频带比单独的链路频带要高 不少，其性能也不会随网络负载的增加而下降很多。对于共事介质网络， 结点之间点到点通信要占用整个传输介质。而实现广播的开销则与点到 黑龙江大学硕士学位论文 点相同。 总之，由于机群系统的结点间通信开销比较大，因此为了提高并行 效率，相互通信的并行任务应当在调度中尽可能地分配到同一结点上去。 这种策略称之为本地化。本地化与负载平衡是两种目的性不同的调度原 则m ，常常发生冲突。如果是动态调度，在任务的负载量和通信量都无 法预测的情况下，必须通过协调机制解决。 4 并行计算模式对负载平衡的影响 并行程序的基本模式，按照并行任务的类型，可分为s p m d 和m p m d 两类：按照任务间通信的类型，又可分为共享存储和消息传递两类。 s p m d 与m p m d s p m d 模式的并行程序，其各个并行任务的执行代码都是相同的， 所不同的只是处理的数据，因此又称为数据并行。典型的s p m 9 程序有矩 阵乘等。图2 3 为s p m d 程序的示例图： - 任务执行的先后依赖 p 任务间的通信方向 图2 - 3s p m d 程序任务示例图 从图中可以看到，程序在初始化( b ) 之后，派生出n 个相同的任 务( p l ，p 2 ，p n ) ，分别处理不同的数据，在程序的最后阶段，经过 数据的汇总和同步，程序结束( e ) 。若这n 个任务之间存在数据交换， 显然为必须保证它们同时被机群系统的各个结点执行，即采用 第2 章负载平衡技术 c o s c h e d u l i n g 和g a n gs c h e d u l i n g 的调度方式，才能获得较好的性能； 即使任务间不存在通信，也只有在m 整除n 时，并行效率才可能较高。 m p m d 程序又称为功能并行。其并行任务不一定相同，依赖关系可 以较复杂，典型的例子包括一些使用分治法则的算法。一般的m p m d 程 序往往存在动态行为，即在运行前无法预测其运行时的任务派生和通信 等情况，因此需要动态调度。 s m 与m p 机群系统的硬件通信机制是网络通信，即消息传递方式。但通过软 件支持，在并行程序的开发中既可以采用共享存储的模式也可以采用消 息传递的模式。目前广泛使用的消息传递模式并行程序开发和运行环境 有p v m f 2 7 j ，e x p r e s s ，m p f ：州z 9 1 等，其中p v m 比较典型。它是一个在异构 型网络环境中模拟一个通用的分布式存储多处理机的软件系统，为用户 提供一个基于消息传递的、对网络通信透明的并行编程运转环境。共享 存储的环境包括c a l y p s o 等，它是通过向用户提供一个共享存储原语库 和一个运行时系统来实现的。从可编程来说，s m 优于m p ，从性能来看， 则s m 模式一般比m p 模式要差。 4 并行层次对负载平衡的影响 并行层次通常可以用粒度来划分，不同的并行粒度具有不同的并行 度和不同的通信开销以及调度开销。图2 - 4 给出了一般性的并行层次的 定义，以及与并行度和通信的关系。 机群系统上能够完成的并行层次范围很广，包括较细粒度的线程级 并行，中等粒度的进程级并行，及粗粒度的作业级并行，覆盖了级l 到 级5 。由于机群系统本身的特点，对于这几种并行层次，相应的调度算 法和负载平衡的判定也有所不同 3 0 l 。 作业并行 黑龙江大学硕士学位论文 作业并行即对由一个用户或多个用户提交的多个作业进行调度，其 目的一般是为了充分利用机群系统的资源。采用的调度策略是根据需要，