（计算机应用技术专业论文）基于接收者驱动的动态负载平衡系统的设计与实现.pdf

i ! 查窒望查堂堡主兰堡燕苎 摘要 胖, 4 7 7 0 7 8 机群系统中负载平衡的基本目标是通过任务调度，将运算均衡的分布 到各个结点，从而提高系统资源的利用率。负载平衡策略直接影响到系统 的并行性能。本文针对机群系统下的负载平衡问题进行了研究，设计并实 现了基于接收者驱动的动态负载平衡系统r i l b s 。论文的主要工作和成果 表现在以下几个方面： 1 大部分集中式控制的负载平衡系统都采用周期性收集负载信息的 方法来获取负载的变化以做出相应的调整。、恒是周期性的负载查询增加了 通信开销。并且，在各结点负载保持稳定的情况下，周期性的负载信息查 询实际是不必要的。r i l b s 采用全局调度和局部调度相结合的方法取代了 周期性的负载信息查询。当服务器接收到一组任务时立即开始全局调度。 而当本地并行子任务全部运行结束并且负载轻时，由结点主动提出调度申 请，服务器接收到申请后开始局部调度。局部调度用单位时间内已完成任 务数和未完成任务数等静态信息来计算应分配任务数，而无需动态查询各 结点的负载信息，从而减少了通信开销。全局调度算法不但考虑了各结点 的负载状况，同时也考虑了结点原有未完威任务对系统响应时间的影响， 在某种程度上可以克服以往分配的误差。7 2 对于计算型应用，c p u 利用率是主要的负载指标。由于c p u 利用 率是动态变化的信息，瞬时的c p u 利用率无法准确反映负载状况。为了避 免负载参数的颠簸，r i l b s 系统利用前k 次收集的瞬时c p u 利用率作加权 平均得出综合c p u 利用率作为负载参数，较好的反映了近期内的负载状况。 而对于由于运行并行计算子任务而使c p u 利用率达到1 0 0 的情况，c p u 利 用率已不足以反映本地的忙闲程度。此时，用进程数乘以平均进程占用c p u 利用率来反映系统的负载量。y 3 r i l b s 采取系统自动调节和人工干预相结合的方法来保证本地任 务的优先。系统在监视本地负载状况的过程中，如果发现连续两次的综合 负载量高于设定的临界值，则认为本地忙，暂停调度下一个任务，使本地 任务可以优先执行。用户也可以根据需要强制暂停并行子任务的执行而专 心运行本地任务，直到本地任务运行结束再解除暂停并恢复并行子任务的 运行。 关键词：机群系统负载平衡任务调度接收者驱动 ! ! 查窒壁叁堂堕主鲎焦堡苎 一一 a b s t r a c t i nc l u s t e ro fw o r k s t a t i o n s ( c o w ) ，t h ep r i n c i p a lp u r p o s e o fl o a d b a l a n c i n gs y s t e mi s t oa l l o c a t et h ew o r k l o a da m o n ga l lt h ep r o c e s s o r sb y s c h e d u l i n gp o l i c yi no r d e rt ou t i l i z et h er e s o u r c e so ft h ec o w - e s p e c i a l l yc p u a b i l i t y e f f e c t i v e l y t h es c h e d u l i n gp o l i c y a f f e c t st h ep a r a l l e lp e r f o r m a n c e d i r e c t l y t h i st h e s i sf o c u s e so nt h es t u d yo fl o a db a l a n c i n gp o l i c ya n dd e s i g n s t h er i l b s ，t h a ti s r e c e i v e r i n i t i a t e dd y n a m i cl o a db a l a n c i n gs y s t e m t h e d e t a i l sa r ea sf o l l o w s ： 1 ，m o s to fc e n t r a l i z e d c o n t r o l l e d1 0 a db a l a n c i n gs y t e m sc o l l e c tt h el o a d i n f o r m a t i o np e r i o d i c a l l ya n dm a k ec o r r e s p o n d i n ga d j u s t m e n ta c c o r d i n gt ot h e c h a n g eo fl o a ds t a t u s h o w e v e r ，c o l l e c t i n gt h el o a di n f o r m a t i o np e r i o d i c a l l y g i v e sr i s e t oc o m m u n i c a t i o nc o s ta n di s u n n e c e s s a r y i nt h ec a s eo f u n c h a n g e a b l el o a ds t a t u s r i l b sc o m b i n e st h eg l o b a ls c h e d u l i n gw i t hl o c a l s c h e d u l i n g t o r e p l a c et h ep e r i o d i c a lc o l l e c t i o n t h eg l o b a ls c h e d u l i n gi s i n i t i a t e db vt h es e r v e rw h e nt h es e r v e rr e c e i v e sag r o u po ft a s k s a n dt h ec l i e n t i n i t i a t e st h el o c a ls h e d u l i n gw h e ni th a sf i n i s h e da l li t st a s k sa n dh a sl i t t l el o a d t h eg l o b a ls c h e d u l i n gp o l i c yt a k e si n t oa c c o u n tn o to n l yt h ec u r r e n t1 0 a ds t a t u s b u ta l s ou n c o m p l e t e dt a s k s i tc a nc o r r e c tt h ed i s e q u i l i b r i u mc a u s e db yp a s t s c h e d u l i n g t h el o c a ls c h e d u l i n gm o v e st h et a s k sf r o mb u s yc o m p u t e rt ot h e r e q u e s t i n g f r e e c o m p u t e r i n p r o p o r t i o n t ot h e i r c o m p l e t e d t a s k sa n d u n c o m p l e t e dt a s k s 2 f o rc o m p u t a t i o nt a s k s ，t h eu s a g eo fc p ui st h em a i nf a c t o rt oj u d g et h e l o a ds t a t u s h o w e v e r ，t h ei n s t a n t a n e o u su s a g eo fc p uc a n n o tr e f l e c tt h el o a d s t a t u sp r e c i s e l yb e c a u s ei to f t e nc h a n g e ss h a r p l y i no r d e rt oa v o i do f u n s t a b l e n e s s ，r i l b su s e st h ew e i g h t e da v e r a g ev a l u eo ft e ns u c c e s s i v e i n s t a n t a n e o u sv a l u eo fc p uu s a g et or e f l e c tt h el o a ds t a t u s i nt h ec a s et h a tt h e c p ui sf u l l yo c c u p i e dw h e nt h ec l i e n tc o m p u t e ri sr u n n i n gp a r a l l e lt a s k ， r i l b su s e st h en u m b e ro fp r o c e s s e sm u l t i p l i e dw i t ht h ea v e r a g ec p u u s a g eo f p r o c e s st or e f l e c tt h el o c a ll o a ds t a t u s 3 r i l b su s e sb o t ha u t o m a t i ca d j u s t m e n ta n dm a n u a lo p e r a t i o nt oa s s u r e t h ep r i o r i t yo fi o c a lt a s k s r 1 l b sk e e p st r a c eo fl o c a ll o a ds t a t u s i ft h el o a d k e e p sh e a v yf o rt w ot i m e s w a t c h ，t h es y s t e ms t o p ss c h e d u l i n gn e x tt a s k t h e s y s t e mw a i t su a t i jt h el o c a ll o a db e c o m e sl i g h t t h eo w n e ro fc l i e n tc o m p u t e r l i 北方交通大学硕士学位论文 c a na l s os t o ps c h e d u l i n gb yf o r c et oa s s u r et h a tl o c a lt a s k sc a nm a k ef u l lu s eo f l o c a lr e s o u r c e s k e y w o r d s ： c l u s t e ro fw o r k s t a t i o n s ，l o a db a l a n c i n g ，s c h e d u l e ，r e c e i v e r - i n i t i a t e d i i i i ! 空窒望查堂堕主兰丝堡苎 一一 1 1 研究动机 1 1 1 并行计算 第一章引言 随着计算机的飞速发展，人们对计算能力的要求与期望也越来越高， 些对人类生存至关重要的问题，也是当今科学技术最前沿的问题，如气 象模型、流体的动力学、污染扩散、量子染色体学等，需要极商处理能力 的计算机。基于网络的高性能计算因此应运而生。这类技术被冠以许多名 字，如机群计算( c l u s t e r i n gc o m p u t i n g ) ，工作站网络( n e t w o r ko f w o r k s t a t i o n ) ，可扩展的计算( s c a l a b l ec o m p u t i n g ) ，元计算 ( m e t a c o m p u t i n g ) ，全球计算( g l o b e lc o m p u t i n g ) 或网格计算( g r id c o m p u t i n g ) 等。虽然形式不同，但其基本思想是一致的，都是由网络互联 组机群或利用已有的网上计算资源形成强大的计算能力。由于其在计算 机领域中的重要地位，各国计算机都把它作为具有战略意义的研究课题。 推动网络高性能计算发展的主要原因包括效率、容错和资源共享等因 素，这些也是网络高性能计算的主要目标。 单处理器体系结构的提高已经非常有限 在过去的一段时间里，单计算机性能不断增强，大约四、五年提高一 个数量级。这些增长主要来源于两个原因：硅芯片制造技术的提高和体系 结构技术的发展。 利用硅芯片制造技术，提高集成电路的线路密度和加快其时钟周期可 以加快计算机的速度。但是，单个c p l 3 的速度受到物理极限的制约，不可 能无限提高。例如信息传输速度不可能超过光速，元器件的物理尺寸受氢 原子直径d h 的限制不可能无限变小和器件发热等问题。据估计单机的极 限速度约为1 0 9 1 0 浮点运算。由于目前的集成电路的线路密度和时钟周 北方交通大学硕士学位论文 期都已接近芯片制造技术的极限，所以人们寄希望于依靠体系结构技术来 进一步提高计算机的性能。 现有的计算机大多是基于传统的v o nn e u m a n n 模型：单c p u 和相应的 存储器及i 0 设备。c p u 从存储器读一条指令，执行指令，然后再读下一 条指令。这种计算机称为串行的。由于i o 速度太慢，引入了d m a 等技术 使计算与i 0 并行。浮点操作比相应的整数操作更耗时一些，引入了浮点 协处理器，用以并行的与c p u 协同完成计算。向量处理器更进一步推广了 浮点协处理器的概念，它可以分别对矩阵中不同的数据同时处理。但为使 向量处理器得到充分的应用，编译过程中需要增加很多工作。流水线和高 速缓存的引入，进一步提高了处理器的处理能力。 现有的单处理器基本上已经采用了这些做法。单处理器体系结构技术 的发展曾给计算机带来了很大的性能提高，但是由于单处理器本身的局限 性，仅依靠单处理器体系结构技术无法满足用户不断增长的需求。因此必 须寻找其它的出路。分布式并行处理成为提高计算能力的一个很自然的选 择。已有的实践和研究结果表明，分布式并行处理【lj 2 i 是提高计算能力的 有效途径。 网络强大的资源共享能力 以网络技术为基础的资源共享真j 下突破了单机的局限性。随着 i n t e r n e t 的迅猛发展，网上已有数千万的各类计算机。但是实际的网络资 源利用率是很低的，据有关统计，系统平均使用率仅为3 0 左右，有的空 闲率竟达9 1 ，这些计算机如果能被组织加以协调工作，将会形成有巨大 潜力的并行计算环境。而且，通信带宽在增长，延迟在降低。t b p s 级传 输速率和l o 1 2 比特以下的传输差错率将成为现实，网络的带宽局限将得到 极大缓解，安全性大大增加，网络的瓶颈将从“低速传输”转移到“高速 传输、低速管理软件”上。网络高性能计算可扩展性强，计算资源几乎可 方便地任意扩展；可靠性高，已存在大量成熟的网络技术和开发工具，许 多公用程序已逐渐标准化。所有这些都为发展分布式并行计算提供了有利 的条件。 容错 当某计算结点出现问题时，采用分布式控制，可将任务转移到可靠结 点。对可靠性要求高的系统还可进行多机表决。 ! ! 查銮望查堂堡主兰堡丝塞 一 1 1 2 负载平衡 在并行处理系统中。往往将一个大的任务拆分成多个子任务，并将这 些子任务分配到各个处理结点上执行。这些子任务即称之为负载p 1 。由于 各个结点的处理能力不同，相同的负载在其上运行的时间和资源占有率都 不同。因此，准确的负载定义应是绝对的负载量与结点处理能力的比值。 机群系统h 1 是一个整体的并行系统，它的特点是各结点独立运行自己 的操作系统，灵活性高，结点处理能力强，资源为多用户共享。对于由n 个结点组成的机群系统，理想的加速比应达到n 。然而在现实情况下这往 往是达不到的。在实际应用中，往往出现这样的情况：当某些结点忙于计 算的时候，另外的一些结点却处于空闲状态，即出现负载不均衡现象。显 然，负载的不均衡大大降低了整个系统的资源利用率直接影响到并行性 能f 5 】。因此，负载平衡扣堤并行处理中的一个重要问题。 为了充分利用高度并行的系统资源，提高整个系统的吞吐率，需要采 取适当的负载平衡技术。负载平衡技术的核心是调度算法，即将各个任务 比较均衡的分布到不同的处理结点上执行，从而使各结点的利用率达到最 大。调度的依据是机群系统下各个结点的计算能力和动态负载的关系i _ ”。 负载平衡算法按照任务调度的时机来划分，可以分为静态与动态两类；按 照调度的控制策略来分，可分为集中式与分布式：按照调度的发起策略来 分，可分为发送者发起与接收者发起：而按照是否支持进程迁移来分，又 可分为剥夺式与非剥夺式。 负载平衡的一般评价标准 8 l 包括： ( 1 ) 吞吐率：并行系统上运行的应用程序的响应时间或平均完成时问。 这是负载平衡系统最主要的衡量尺度。 ( 2 ) 可扩展性：系统规模增大或总负载大小变化时系统的适应能力。 ( 3 ) 容错性：发生处理机故障后任务恢复运行的能力。 负载平衡系统需要解决的问题主要包括： 负载状况评测如何通过直接获取的负载信息( c p u 利用率，内存利用 率，活动进程数等) 判断负载状况，对负载量化并做出预测。 任务调度方式根据预测的负载量，按照怎样的算法将任务分配到各结 点。任务调度1 9 1 有静态调度和动态调度两大类。对于静态调度来说，应用 北方交通大学硕士学位论文 程序中的各种信息( 如任务大小、前趋关系、任务问通信量等) 以及并行 系统的情况( 网络拓扑结构、各处理机结点计算能力等) ，在程序运行前就 需得到，并以之为依据完成任务分配方案。静态算法能给出较优的调度方 案，但要求有完整的任务关系图。然而在机群系统中，各处理机上的负载 具有动态性，很难做出准确的预测，这势必影响到并行的效率。动态调度 通过分析系统的实时负载信息，动态的将任务在各处理机之问进行分配和 调整，重载的处理机及时的把多余的任务分配到轻载的处理机上，或者轻 载的处理机及时的向重载的处理机申请任务。动态调度的优点是显而易见 的，它可以对由于任务动态到来造成处理机负载的突发性的增加或减少的 情况做出及时的响应。但缺点是增加了系统的调度开销。 保证本地任务优先并行计算利用的是网络的空闲资源，因此，当本地 用户需要使用本地资源时，应及时撤走并行任务，保证本地用户任务的优 先权。 容错处理对于并行任务运行异常或结点机发生故障的情况，负载平衡 系统应能及时的检测到，通过任务的重新分配使得故障对系统的吞吐率的 影响尽可能小。 此外，任务迁移，机群系统性能评价，并行处理模式，应用问题特征 分析等也是负载平衡系统研究中十分重要的问题。 1 2 论文组织及贡献 1 2 1 论文组织 第一章概述了并行处理技术的发展以及负载平衡的重要性。同时，对 论文工作的主要内容和主要贡献进行了阐述。 第二章介绍了机群系统的基本特点以及机群系统的关键研究领域。 第三章详细讨论了负载平衡的各种技术，并研究了并行计算模式对负 载平衡算法的影响，最后介绍了目前已有的一些负载平衡系统。 第四章详细阐述了基于接收者驱动的动态负载平衡系统r i l b s 的设 计与实现。r i l b s 系统采用全局调度与局部调度相结合的方法，较好的实 ! ! 查奎望丕堂堡主堂垡堡苎 一 现了负载的均衡分布。实验结果表明，r i l b s 对粒度较大的计算型应用有 较理想的加速比。 第五章对论文进行总结并展望进一步的工作。 1 2 2 论文的主要贡献 1 大部分集中式控制的负载平衡系统都采用周期性收集负载信息的方 法来获取负载的变化以做出相应的调整。但是周期性的负载查询增加了通 信开销。并且，在各结点负载保持稳定的情况下，周期性的负载信息查询 实际是不必要的。r i l b s 采用全局调度和局部调度相结合的策略取代了周 期性的负载信息查询。当服务器接收到一组任务时立即开始全局调度。而 当本地并行任务全部运行结束并且本地负载轻时，由结点主动提出调度申 请，即r j ，服务器接收到申请后开始局部调度。由于r i l b s 采用集中控 制，每个子任务的分配和完成都经由服务器，根据服务器所掌握的各个结 点机上子任务的运行情况可以推测出在该段时间内各结点机上的负载状 况，因此可以用静态信息代替动态查询以减少通信开销。局部调度正是利 用已完成任务数，未完成任务数的静态信息来实现任务的分配。r i l b s 的 全局调度既考虑了结点的当前负载量，也考虑到结点的等待队列对能接受 的任务的影响。调度的目的是使得结点上原有的任务和新来的任务都完成 的预计时间差尽可能小。结点的等待任务越多，相应新分配的任务应越少， 因此，全局调度算法在某种程度上可以纠正以往的分配误差。 2 对于计算型应用，c p u 利用率是主要的负载指标。由于c p l 3 利用率 是动态变化的信息，相邻时刻的c p u 利用率可能差别很大。为了避免负载 参数的颠簸，r i l b s 系统利用前k 次收集的瞬时c p u 利用率作加权平均得 出综合c p u 利用率作为负载参数，较好的反映了近期内的负载状况，并以 此作为未来短期内负载状况的预测。而对于c p u 利用率达到1 0 0 的情况， c p u 利用率已不足以反映系统的忙闲程度。此时，用进程数乘以平均进程 占用c p u 利用率来反映系统的负载状况。 3 r i l b s 采取系统自动调节和人工干预相结合的方法来保证本地任务 的优先。系统在监视本地负载状况的过程中，如果发现连续1 1 次的综合负 载量高于设定的临界值，则认为本地忙，暂停调度下一个任务，使本地任 北方交通大学硕士学位论文 务可以优先执行。直到监视到本地负载量降到临界值以下才恢复子任务的 运行。用户也可以根据需要强制暂停并行子任务的执行而专心运行本地任 务，直到本地任务运行结束再解除暂停并恢复并行子任务的运行。 j ! 查銮塑奎兰堡主堂堡垒塞一 第二章机群系统 2 1 机群系统的基本体系结构 机群系统是互相连接的多个独立计算机的集合，这些计算机可以是单 机或多处理器系统( p c ，工作站或s m p ) ，每个结点都有自己的存储器， i o 设备和操作系统。机群对用户和应用来讲是一个单一的系统，这样的 系统可以提供低价高效的高性能环境来提供快速可靠的服务，其一般结构 如图2 1 。 图2 1机群系统一般体系结构 2 2 机群系统的特点 机群系统之所以能够从技术可能发展到实际应用主要是它与传统的并 行处理系统相比有以下几个明显的特点【3 】： 1 系统开发周期短。由于机群系统大多采用商用工作站和通用l a n 网络，使结点主机及系统管理相对容易，可靠性高。开发的重点在通信和 并行编程环境上，一般不用重新研制计算结点，也不用重新设计操作系统 北方交通大学硕士学位论文 和编译系统，这就节省了大量的研制时间。 2 用户投资风险小。用户在购置传统巨型机或m p p 系统时很不放心， 担心使用效率不高，系统性能发挥不好，从而浪费大量资金。而机群系统 不仅是一个并行处理系统，它的每个结点同时也是台独立的工作站，即 使整个系统对某些应用问题并行效率不高，它的结点仍然可以作为单个工 作站使用。 3 系统价格低。由于生产批量小，传统巨型机或m p p 的价格都比较 昂贵，往往要几百万到上千万美元。工作站或高档p c 机由于是批量生产 出来的，因而售价较低。由近十台或几十台工作站组成的机群系统可以满 足多数应用的要求，而价格却比较低。 4 节约系统资源。由于机群系统的结构比较灵活，可以将不同体系结 构、不同性能的工作站连在一起，这样可以充分利用现有设备。单从使用 效率上看，机群系统的资源利用率也比单机系统要高的多。u cb e r k e l e y 计算机系1 0 0 多台工作站的使用情况调查表明，一般单机系统的使用率不 到1 0 ，而机群系统中的资源利用率可达到8 0 左右。另一方面，即使用 户设备更新，原有的一些性能较低或型号较旧的机器在机群系统中仍可发 挥作用。 5 系统扩展性好。从规模上说，机群系统大多使用通用网络，系统扩 展容易；从性能上说，对大多数中、租粒度的并行应用都有较高的效率。 清华大学计算机系研制的可扩展机群系统上测试的结果表明8 台工作站的 加速比可以达到5 8 3 7 9 ，并行处理的效率为7 2 8 8 一9 9 。 6 用户编程方便。机群系统中，程序的并行化只是在原有的c 、c + 十 或f o r t r a n 串行程序中，插入相应的通信原语。用户使用的仍然是熟悉的编 程环境，不用适应新的环境，这样就可以继承原有软件财富，对串行程序 做并不很多的修改。 韭壅窒望盔堂堡主兰垡丝苎 一一 2 3 机群系统的分类 2 3 1 机群系统的分类 机群系统可以按应用或结构进行分类： 1 按应用目标可分为面向科学计算的高性能机群( h i g hp e r f o r m a n c e c l u s t e r ) s 1 面向关键任务应用的高可用性机群( h i g ha v a i l a b i l i t yc l u s t e r ) 。 2 按组成机群的处理机类型可分为p c 机群、工作站机群和s m p ( 对 称多处理器) 机群。 3 按处理机操作系统可分为l i n u x 机群( 如b e o w u l f ) 、s 0 1 i s 机群( 如 b e r k e l e yn o w ) 、n t 机群( 如h p v m ) 、a i x 机群( 如i b ms p 2 ) 、数字 v m s ( 虚拟存储机) 机群、h p u x 机群、微软w o l f p a c k 机群等。 4 按处理机的配置可分为同构型机群f 所有结点拥有近似的构造和相 同的操作系统) 和非同构型机群( 所有结点拥有不同的构造和不同的操作系 统) 。 5 按处理机的位置和数量可分为组机群( 结点数量2 9 9 ，通过s a n s 系统级网络如m y r i n e t ，机群事实上装入个机箱中或存在一个范围之内) 、 部门机群( 结点数量几十或几百) 、企业机群( 结点数量几百) 。 6 按构筑机群的方式可分为专用机群和非专用机群。 2 3 2 专用机群 专用机群一般由一组同构的处理机组成( 有时也有异构情况) ，通常安 装在一个机房内；或者将主板等安装在一个机柜的各机箱内( 商业机群常 用这种方式) ：或简单地把p c 机堆砌在机架上( p i l e so f p c ) ，这种机群中 每个处理机都是专用的、无属主的，由系统管理员统一管理，用户可通过 前端机进行访问，用户无需知道机群的详情就像使用m p p 机一样，这种 机群易于配置，易于管理。不受外界干扰，通讯可靠延迟小，适合于面向 加速比的并行任务和面向吞吐量批处理作业。专用机群具有相对结构和管 理简单，易于扩展等特点，并且拥有极高的性能，价格比用途极广。 j ! 查銮堡查兰堡圭堂垡笙壅一 专用机群的互联结构通常有i 0 方式和共享存储器方式两类： ( 1 ) 1 0 方式包括用l a n 、f d d i 、a t m 等网络连接的普通方式和共享磁盘 连接方式。 ( 2 ) 共享存储器方式包括全局共享存储器方式和分布式共享存储器方 式，分布式存储器指没有一个集中的存储器，由各处理机内一部分存储机 制形成。 1 9 9 4 年夏，美国人建成了第一个b e o w u i f 机群，它出1 6 个d x 4 处理 机组成。1 9 9 7 年又推出1 6 个基于p i i 的机群，只用5 万美元却具有每秒 】0 亿次的浮点运算能力，而相同能力的并行机需投资数十倍计。 b e r k e l e y 的n o w 系统也是较早的工作站机群，由上百个s u n 叭t r a 工 作站组成，集成到1 9 英寸机箱中，可使用m y r i n e t 、a t m 和终端集中器等 多种互联手段，每个结点自带5 】2 k 缓存，1 2 8 m 内存2 个2 3 g 硬盘。 此外，各大公司推出的商业专用机群有很多，如d e c 的v m s 机群、 t r u c l u s t e r ，惠普的a p o l l o9 0 0 0 机群，i b m 的s y s p l e x ，s u n 的s o l a r ism c 等等。 在国内，曙光公司最新推出了基于n t 的天潮系列机群产品，采用分布 式存储的可扩展机群体系。结点处理器为i n t e rp i i 和p n i ，通过干兆以 太网互联，扩展性好，结点可以根据应用不同，动态的分为多个结点池， 如可用二个结点作服务器，四个结点运行数据库，其它结点作计算等，结 点数量可灵活配置，应用范围包括： 科学计算：支持p v m 和m p i ，使用优化的b l a s 库 事务处理：在线事务处理( o l t p ) ，如电子商务、证券交易等和 在线分析处理( 0 l a p ) 。 并行数据库：支持o r a c l e 、d b 2 等分布式数据库应用 网络服务器：运行各种i n t e m e t j 艮务。 2 3 3 非专用机群 非专用机群主要思想是由分散互联的处理机或在网上寻找的空闲处理 机组成的机群，这些处理机可能分属于不同的个人、组织或单位。据资料 统计，一般计算机系统平均使用率仅为3 0 左右，有的空闲率竟达9 1 ， j ! 查銮望奎堂堡主兰垡丝苎一一 而许多桌面网络工作站和微机的c p u 利用率都小于1 0 ，因此，自然想 到要利用这些闲散的c p u 处理能力，这也称之为c p u 周期窃取a 通常，网络上计算单元都有其拥有者各自孤立地使用其拥有的计算单 元，一般完成下列类典型的工作： 正处于空闲或等待状态，如夜问。 文档编辑工作，包括接、发e m a i l ，阅读文档和信息等 开发工作，包括编辑、编程、编译，调试等 完成某种定时、守候服务和功能 运行计算型的程序 所谓窃取c p u 周期就是要窃取上述前四类处理机的c p u 周期给最后一 类程序用，显然，被窃取c p u 周期的处理机包括空闲的处理机和c p u 负载 较轻的处理机两类。 非专用机群地理上分布于不同的所有者，由异构系统组成，大部分是 通过以太网连接，适用于企业级局域网范围，技术难度要高于专用机群， 工作站主人和需要工作站运行程序的远程用户之间存在矛盾，前者希望和 工作站快速交互，而后者只关心能否利用所有共享c p u 来快速运行程序， 所有者必须具有参加机群的动机，这意味着参加者相信贡献他们的资源是 有意义的。但是，这些所有者不希望在他们工作时，或他们的系统过于饱 和时，受到其它于扰，一个策路是允许所有者退出机群，国际上正在形成 一种计算资源的买卖市场，以刺激资源拥有者加入网上机群。此外，由于 当前网络通讯速度和质量瓶颈及由通讯竞争造成的网络不确定性的存在， 对非专用机群技术有更高的要求，如对进程迁移、负载平衡等技术的需求。 但此类系统最为贴近普通用户，可以充分利用网上无穷无尽的资源，而组 建投资几乎可忽略不计，可以预见，随着网络瓶颈问题的缓解，非专用机 群必然是极有前途的一种计算形式。 2 4 机群系统的关键技术及研究方向 机群系统的设计涉及到的技术非常广泛，主要有以下几个研究方向 北方交通大学硕士学位论文 2 4 1 体系结构 由于现有操作系统都是在单机系统中发展而来，而分布式和网络操作 系统大多数是在原单机操作系统上扩充改造的，因此，其体系结构不能够 对分布式计算的所有特点提供足够的支持。现有的机群系统绝大多数都在 现有的体系结构上构筑起来的，因此，在现有网络基础上，怎样在匿名自 主用户机器之间构筑分布式计算环境并实现任务并行的透明管理是一个重 要研究方向。 2 4 2 负载平衡和调度策略 在机群系统中，一个大的任务往往是由多个子任务组成。这些子任务 被分配到各个处理结点上并行执行，称之为负载。对于由异构处理结点构 成的机群系统而言，由于各结点的处理能力不同，相同的负载在其上运行 的时间和资源占有率都不同。因此，准确的负载定义应当是绝对的负载量 与结点处理能力的比值。当整个系统任务较多对，分配给各结点的负载可 能并不均衡，整个系统的利用率就会降低。因此，有效的将各个子任务均 衡的分布到不同的处理结点进行并行计算，使各结点的利用率达到最大。 从任务分配决策的时机来看，负载平衡策略可分为静态和动态两类方法。 静态方法是在编译时针对用户程序中的各种信息( 如各个任务的计算 量大小、依赖关系和通信关系等) 以及机群系统本身的状况( 如网络结构、 处理结点的计算能力等) 对用户程序中的并行任务做出静态分配决策，程 序运行时将任务分配到相应结点。理论证明，静态算法求最优调度方案属 于n p c o m p l e t e 问题，因此在实践中往往采用求次优解的算法。静态算法 要求获得完整的任务依赖关系信息，但在高度并行的多计算机领域，特别 是在多用户方式下，各处理机上的任务负载是动态产生的，不可能做出准 确的预测。 动态方法是通过分析机群系统的实时负载信息，动态的将任务在各处 理机之间进行分配和调度，以消除系统中负载分布的不均匀性。动态负载 平衡的特点是算法简单，实时调度，但同时也增加了系统的额外开销。 目前在机群系统上比较成功的几个负载平衡系统有 ! ! 銮銮擅杰兰堡主堂垡堡苎 w i s c o n s i n m a d i s o n 大学的c o n d o r ，p l a t f o r m 公司的l s f 等。关于负载 平衡的讨论是本篇论文的重点，在第三章中也将详细论述负载平衡的各种 策略以及相关问题。 2 4 3 通讯协议 机群系统一般使用通用局域网连接。目前常用的局域网技术大体可以 分为两类，一类是共享介质网络，最常见的是1 0 m b p s 或1 0 0 m b p s 的 e t h e r n e t ；另类是开关网络，比如1 5 5 m b p s 6 2 2 m b p s 的a t m ， 6 4 0 m b p s 1 2 8 g b p s 的m y r i n e t 和1 0 0 m b p s 的交换式e t h e m e t 。对于共享介 质网络，由于其聚合网络频带与单独链路频带是一样的，其性能会随网络 负载的增加而下降，特别是对于某些负载比较集中的应用程序，这种影响 会更明显，但是售价便宜，组成系统也相对容易，是组成中低档机群系统 的_ 一种较好的选择。而开关网络则相反，其聚合网络频带比单独的链路频 带要高的多，理论上讲是n 倍；除开关的交换延迟影响外，性能不会随网 络负载的增加而降低很多，开关网络的另一个优点是其可扩展性较好，由 于w o r m h o l e c u t t h r o u g h 等交换技术的发展，交换延迟已经很低，与发送 接收端的歼销相对要小的多。比如，m y r i n e t 开关的一次交换延迟小于l l i s ， 一个中等规模的机群系统( 1 6 3 2 台) 的点点的往返延迟仅有几十微秒。 但是交换开关及相应接口卡的售价要高的多，组成机群系统的价格也相对 比较高，对系统的普及会有一定的影响，参见表2 1 。 类型 速度 t c p i p 往返 集线器接口价格实现 ( m b p s ) 延迟( u s )交换机( 千元)灵活性 ( 千元) e t h e r n e t1 01 4 3 8 电1 差 f a s t1 0 01 3 4 7 1 5 8 5 1 5 差 e t h e r n e t a t m1 5 5 6 2 21 2 8 5- ，2 1 01 5 一般 m y r i n e t 6 4 0 1 2 8 0 1 5 0 6 一，2 0 1 2 好 表2 1 几种常用局域网的性能，价格情况 在不考虑网络负载的情况下，般使用点点的应用程序可见带宽和往 返延迟来衡量通信系统的性能。应用程序可见带宽说明了网络的长消息包 ! ! 查銮堂查堂堕主兰垡丝苎 一一一 的传输性能，虽然由于网络技术的飞速发展，网络的物理链路越来越快， 但是应用程序的可见带宽比起链路速度来要小的多，主要原因有网卡接口 的硬件限制，协议处理开销和操作系统开销。例如，m y r i n e t 的物理链路是 双向的6 4 0 m b p s ，而在t c p i p 协议上点点的应用程序可见带宽只有 3 8 m b p s 。往返延迟是1 字节或0 字节数据消息包的往返传输时间，它说明 了网络短消息包的传输性能。新的网络技术大幅度的提高了传输速度，但 往返延迟没有太大变化。从表2 i 中可以看出，快速以太网、a t m 和m y r i n e t 在t c p i p 上的往返延迟与1 0 m b p s 的延迟相差不多。 现有的底层通讯协议和机制是面向单接收者和单发送者之间的可靠比 特流通讯，但分布式计算的环境对通讯协议和机制要求更多的支持： 简化各通讯协议层，使之更高数以缓解通讯瓶颈； 通讯透明性：无论用户进程移动到何结点，都要求能透明的寻求到 最佳路由； 良好的组通讯提供对分布式共享存储器等的支持； 应对网络安全性提供一定的支持； 提供对网络管理的支持，可自动进行网络配置和维护。 目前，通信系统的研究方向主要在减小往返延迟和提高链路带宽的利 用率上。实现方法主要有： 1 ) 用新型高速网络，提高网络带宽 2 ) 设计新的通信协议，降低通信延迟。包括： i 在用户空间实现通信协议。 为了减少操作系统的额外开销，一个重要的方法是在用户空间实现一 个用户念的协议层，使得此协议层能够旁路操作系统的影响，直接对网络 硬件设备进行操作，这样就可减少数据拷贝次数，提高通信效率；把协议 实现放在用户空间的另优点是可以减少操作系统调用的时间开销，而且 通讯协议能够与用户的实际应用密切结合，可减少协议不必要的冗余，同 时也不会有损它的灵活性。不过，把通信协议放在用户空间实现，必须解 决好两个问题：一个是多进程复用网络的问题；另一个是在没用核心参与 的情况下，如何管理有限网络资源的问题。只有这样，用户态通信协议才 能得以有效的实现。 i i 精简通信协议。 通信的开销很大程度上是由于协议层次多，数据拷贝频繁引起的，另 外，通用的网络接口和协议为满足各种用户的需求，增加了很多与数据传 输无关的服务，这些服务也带来了额外的开销。而在并行机群系统中，有 些功能是不必要的，完全可以进行精简，以降低通信开销。所谓精简包括 两部分内容：一部分是功能的精简，就是删除不必要和冗余的功能；另 部分是协议层次的精简，合并各层的功能，使得通信协议变为一层，以达 到减少数据拷贝次数的目的。比如，在操作系统s o l a r i s2 4 中，通信协议 由网络驱动程序、数据链路层( d l p i ) 、i p 层、t c p 层和s o c k e t 接口组成， 由于数据链路层d l p i 已经提供了不保证数据包无差错传送的基本数据通 信功能，因此可以在它基础上实现一个保证数据可靠传送的模块以取代复 杂的t c p i p 协议层和s o c k e t 接口。这样新的通信协议不论从结构上看， 还是从功能上分析，都比原来的协议要简单的多。 i i i a c t i v em e s s a g e 通信机制 通信协议的用户态实现以及协议的精简这两种方法都是针对传统通信 协议在实现方法上所做的改进，而a c t i v em e s s a g e 则是一种全新的通信机 制。在a c t i v em e s s a g e 通信方式下，消息的数据结构除了包含通常的数据 项外，还增加了两项内容：消息处理程序指针h a n d l e r 和参数。当消息到 达目的结点后系统立即产生中断调用，并由中断处理机制启动消息处理程 序。消息处理程序的功能是从网卡上取出消息并给发送方发送一个应答消 息，然后返回原来被中断的程序。a c t i v em e s s a g e 通信机制是一种消息驱 动的异步通信方式。异步通信最大的优点是能够实现通信与计算的重叠。 与传统的异步通信方式相比，这种方式具有更大的优越性。其原因首先足 消息驱动能使c p u 获得较高的利用率；第二个关键原因是接收方收到的数 据是由消息处理程序h a n d l e r 提交给应用程序的，提交过程能由网卡上的 处理器来完成，这样，c p u 的计算与数据提交能够同时进行。 a m o e b a 系统中采用的f l i p 协议代替i p 协议1 3 】，是一个典型的分布式 系统协议，但这方面还有待进一步的大力研究，设计兼容性好的分布式网 络协议。 些塑窒塑查堂堡主堂堡笙苎 一 2 4 4 并行程序设计环境 随着m p p 和机群系统等分布存储结构并行系统的发展，开发出了 p v m 、m p i 、e x p r e s s 、p 4 等基于m e s s a g ep a s s i n g 方式的并行程序设计环 境，它为并行程序的设计和运行提供一个整体系统和各种辅助工具。功能 包括提供统一的虚拟机、定义和描述通信原语、管理系统资源、提供可移 植的用户编程接口和多种编程语言的支持。目前研制的机群系统大多支持 p v m 和m p i ，除了能适应广泛的硬件平台和编程方便等特点之外，它们都 是免费软件，可以方便的进行再开发，有利于系统的推广与应用。正是由 于它们都是免费软件，所以在支持语言、容错及工具等方面都不完善，许 多研究机构和大学正在做这方面的研究。 开发并行应用程序要比串行程序困难的多，它要涉及多个处理器之间 的数据交换与同步，要解决数据划分、任务分配、程序调试和性能评测等 问题，需要相应支持工具，比如并行调试器、性能评测工具、并行化辅助 工具，他们对程序的开发效率与运行效率都有重要作用。目前，提供工具 较完善的系统有f a u s t 、e x p r e s s 、t o p s y s 、v