（计算机应用技术专业论文）机群系统中通信技术的研究.pdf

北方交通大学硕十学位论文 p 4 7 7 0 8 8 摘要 f 通信性能是影n 向机群系统实际并行处理效率的关键，因此，高性能通 唐系统的研究在整个机群系统中占有非常重要的地位，并且直是近几年 国内外研究的热点。本文在分析影响通信系统性能主要因素基础卜，对机 统地描述，分析了几个常用的通信系统评价模型，在此皋础上，给出了评 阶机群通信系统的一般方法。 二、讨论了影响机群通信性能的主要因素：网络硬件、通信软件、运 ，亍环境和服务质量要求，针对系统设计中的一些关键问题给出解决方法。 分析了机群通信系统的设计策略，给出了在一个高效通信系统巾，互联刚 貉、网络接口和通信软件应该具备的特性。 t 、广泛而深入地研究了一些具有代表性的机群通信系统，分析了这 些系统的设计思想、实现技术以及可借鉴的先进之处，总结并给 ： _ 了开发 亩效机群通信系统的先进经验和技术。 凹、在研究了传统的a c k r e q 应答机制的基础卜，提 n 了一种隐含 立答结合双向组确认机制的通信可靠性保证策略。将确认信息隐含在普通 t 勺消息包中，并辅之以组确认机制，以组为单位应答接收到的消息包，而 1 、是传统的逐包确认。 n 设计了一种新的简单町靠通信协议一s r c p ，它结合了t c p 的可 霏性和u d p 的灵活性、简单性，适用于传统的e t h e m e t 局域网。该卧泌 垣过一层虚拟驱动存用广空间和网络接口之问直接传递数据，将协议处理 是到剧户窄间实现，简化了通信的层次，减少了系统核心的干预。s r c p 是供了一组与基于u d p 协议的s o c k e t s 类似的灵活接口。f i 同之处在于， ；r c p 保证通信的可靠性和有序性，并且支持变长消息。 是键词：机群系统、机群通信、通信协议、用户级通信、应答w 萄 j ! 查奎望盔堂堕主鲎焦丝壅 a b s t r a c t t h ec o m m u n i c a t i o np e r f o r m a n c ei st h ec r i t i c a lf a c t o rw h i c hs i g n i f i c a n t l y a f f e c t st h ea c t u a le m c i e n c yo fp a r a l l e lp r o c e s s i n go nw o r k s t a t i o nc l u s t e r s ， t h e r e f o r eh o wt oa c h i e v eh i g h p e r f o r m a n c ec o m m u n i c a t i o ns y s t e m sp l a y sa n i m p o r t a n tr o l e i nt h er e s e a r c ho fw o r k s t a t i o nc l u s t e r sa n dh a sb e e nah o t r e s e a r c ht o p i ci nr e c e n ty e a r s i nt h i sd i s s e r t a t i o n ，t h em a i nc o m m u n i c a t i o n o v e r h e a d s w h i c hl i m i tt h ep e r f o r m a n c eo fc o m r n u n i c a t i o ns y s t e m s ，a r e a n a l y z e dt h o r o u g h l y t h er e s e a r c hf o c u s e so nt h et o p i co ft h em e t h o do f r e d u c i n gc o m m u n i c a t i o no v e r h e a d ，t h ep r i n c i p l ea n ds t r a t e g yo fd e s i g n i n ga n d i m p l e m e n t i n gah i g h p e r f o r m a n c ec o m m u n i c a t i o ns y s t e m s o nw o r k s t a t i o n c l u s t e r s t h ec o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： 1 1 1 1 ed e v e l o p m e n t ， c o m p o s i t i o n f u n c t i o na n dc h a r a c t e r i s t i co f c o m m u n i c a t i o ns y s t e m so nw o r k s t a t i o nc l u s t e r sa r ei n t r o d u c e ds y s t e m a t i c a l l y a f t e ra n a l y z i n gs e v e r a lm o d e l so fe v a l u a t i n gt h ec o m m u n i c a t i o ns y s t e m s ，a c o m m o nm e t h o dt oe v a l u a t ec o m m u n i c a t i o ns y s t e m si sg i v e n 2 f o u rm a i nf a c t o r s w h i c hl i m i tt h ep e r f o r m a n c eo fc o m m u n i c a c i o n s y s t e m s ，a r ed i s c u s s e d ：h a r d w a r eo fn e t w o r k ，c o m m u n i c a t i o ns o f t w a r e ，r u n n i n g e n v i r o n m e n ta n dr e q u i r e m e n to fs e r v i c eq u a l i t y as o l u t i o nh a sb e e np r o p o s e d t os o l v es o m ek e yp r o b l e m si ns y s t e md e s i g n i n ga n di na d d i t i o ns o m e c h a r a c t e r i s t i c st h a ts h o u l db ep o s s e s s e db yi n t e r c o n n e c t i o nn e t w o r k ，n e t w o r k i n t e r f a c ea n dc o m m u n i c a t i o ns o f t w a r ei nah i g h p e r f o r m a n c ec o m m u n i c a t i o n s y s t e ma r eg i v e n 3 s o m er e p r e s e n t a t i v ec o m m u n i c a t i o ns y s t e m so nw o r k s t a t i o nc l u s t e r sa r e s t u d i e de x t e n s i v e l ya n di n t e n s i v e l y a n do nt h eb a s eo fa n a l y z i n gt h e i r d e s i g n i n gi d e a i m p l e m e n t i n gt e c h n i q u ea n do t h e ra d v a n c e df a c t o r sw h i c hw e c a nu s ef o rr e f e r e n c e ，s o m ea d v a n c e de x p e r i e n c e sa n dt e c h n i q u e sa r ep r o p o s e d t od e v e l o pah i g h - p e r f o r m a n c ec o m m u n i c a t i o ns y s t e m s 4 o nt h eb a s eo fr e s e a r c h i n gt h et r a d i t i o n a la c k r e qs t r a t e g y ，an e w s t r a t e g yi sd e s i g n e dt og u a r a n t e et h er e l i a b i l i t yo fc o m m u n i c a t i o n ，i nw h i c ht h e a c ki n f o i t f l 【a t i o ni se m b e d e di nc o m m o np a c k e t sa n da s s i s t e dw i t ht h eg r o u p a c k n o w l e d g e m e n tm e c h a n i s m t h ew o r dg r o u pm e a n st h a tt h er e c e i v e dp a c k e t s a r ea c k n o w l e d g e db yg r o u pn o tb yi n d i v i d u a ia si nt h et r a d i t i o n a l c o m m u n i c a t i o n 5 an e ws i m p l ea n dr e l i a b l ec o m m u n i c a t i o np r o t o c 0 1 t h a ti ss r c p ，i s d e s i g n e d w h i c hc o m b i n e st h er e l i a b i l i t yo f t c pa n dt h ef l e x i b i l i t yo f u d p t h e n e wo n ec a nw o r kw e l lo nt h ee m e r n e t b a s e dl a n s r c pt r a n s f e r sp a c k e t s d i r e c t l yb e t w e e nu s e rs p a c ea n dt h ei n t e r f a c eo fn e t w o r k ，i m p l e m e n t sp r o t o c o l p r o c e s s i n gi nu s e rs p a c e s r c pp r o v i d e sas e to fc o m m u n i c a t i o nf u n c t i o n s w h i c ha r ea sf l e x i b l ea st h o s eo fu d p b u ts r c ph a sm o r ep o w e r f u lf u n c t i o n s 1 1 北方交通人学硕士学位论文 t h a nu d p f o re x a m p l e ，s r c pg u a r a n t e e st h er e l i a b i l i t yo fc o m m u n i c a t i o na n d c a nt r a n s f e rp a c k e t sw i t hd i f f e r e n ts i z e k e y w o r d s ：w o r k s t a t i o nc l u s t e r ，c o m m u n i c a t i o no nw o r k s t a t i o nc l u s t e r c o m m u n i c a t i o np r o t o c o l ，u s e rl e v e lc o m m u n i c a t i o n ，a c ks t r a t e g y 1 1 1 北方交通大学硕士学位论文 第一章引言 本章介绍了并行处理的发展，机群系统的发展及现状，探讨了通信系 统在机群系统中的重要性，并对本文的目的、主要工作和内容作了简要的 阐述。 1 1 机群系统的发展 1 1 1 并行处理是计算机发展的必然趋势 计算机技术是人类科学技术中发展最快的领域之一，1 9 4 6 年世界上 出现了第一台数字计算机e n i a c ，在此后的短短5 0 多年间，计算机技术 取得了突飞猛进的发展，先后经历了电子管、晶体管、集成电路、超大规 模集成电路四代的演变。在此期间，电子器件制造技术的进步和计算机 体系结构的发展，极大的推动了计算机性能的迅速提高。单机的计算能力 从每秒几万次发展到了每秒几千万次。总结近几年来处理器芯片速度的发 展规律，我们发现，平均每过四至五年，计算机的处理速度就提高一个数 量级。计算机的应用领域，从政府、工业等专用领域发展到了千家万户， 进入了家庭，几乎所有的人类生活领域都受到了计算机发展的影响。近年 来互联网的发展更加快了计算机的普及，使计算机进入到每个人的生活。 随着计算机应用领域的不断扩大，计算机普及率的不断提高，人类对 计算机技术的要求也随之在不断提高。时至今日，单机速度尽管仍在不断 的提高，但人类需求的发展更快，并已经超过了单机速度的发展，此外， 由于物理器件自身的局限性，单机速度是不可能无限制的发展下去的。我 们知道，为了提高处理器的速度、功能，芯片的集成度不断提高，以便可 以在一个微处理器内部集成越来越多，越来越复杂的功能部件。芯片的工 作频率越来越快，以不断提高处理器的速度，但是，芯片的集成度不可能 无限提高，工作频率也必定会有一个上限。现在的处理器芯片已采用0 1 3 微米技术，最快的芯片工作频率已达2 2 g h z 。有人预计c m o s 线宽的工 艺下限是0 1 微米【2 】，量子力学也说明了当导线宽度小到一定程度时，电 子运动会出现波动性，按现有的电路设计方法设计的电子线路将不会按照 我们预期的方式工作。 北方交通大学硕士学位论文 过去所取得的计算机技术的提高主要源于两方面的发展：半导体技术 和体系结构技术的发展。体系结构技术的发展与半导体技术的发展一样， 也给计算机带来了很大的性能提高，采取的措施主要是通过对传统的 冯诺伊曼体系结构进行一系列改进来提高效率：使c p u 与i o 并行工 作来解决c p u 与外设之间的速度不匹配问题：增加专门的处理单元到处 理器中来处理一些耗时的操作：以流水线方式使指令重叠起来执行，从而 将执行效率提高n 倍( n 为流水线的级数) ；通过高速缓存加上适当的预 取算法来解决存储器与处理器之间速度的不匹配。另外，r i s c 技术、超 流水线、超标量和超长指令字等技术也都使单处理机系统的计算速度有了 不同程度的提高。 尽管采用这些有效的做法使单处理器的性能有了几个数量级的提高， 但是，由于芯片技术和制造工艺的固有局限性，这种体系结构的系统难以 再有巨大的性能提高。在目前，虽然个人电脑可以满足绝大多数计算机用 户的要求，但是，当我们将眼光放得远些，看得广一些，就会发现人类 的科学实践对计算能力的需求远远不止于此，在很多领域，单机处理能力 远远不能满足大规模复杂计算的需要，例如：气象模型、人类基因工程、 海洋环流分析、污染扩散、燃烧系统、视觉和识别等等。 要解决这些领域的问题，至少需要1 0 0 0 g 以上的浮点运算能力和 1 0 0 0 g b 的存储容量1 2 j 。面对如此巨大的计算能力需求，单处理机系统显 然是不够的，即使再有相当长时间的发展也难以达到。实践证明，并行处 理是提高计算机系统计算能力的有效途径，采用并行处理系统，系统的计 算能力可以在现有处理器的能力上提高上百倍，甚至上千倍。特别是近几 年来并行处理技术的飞速发展，大大缩小了并行处理系统中的处理器技术 与单机系统中处理器技术的差距，提高了系统的效率，开发了多种可移植 的并行程序编程环境和工具。当然，要使并行系统的能力得以充分的发 挥，需要体系结构、操作系统、应用软件等各方面的密切配合。 1 1 2 并行处理技术的发展和现状 早在6 0 年代，计算机工作者就开始模拟组织人类社会劳动的并行方 式，将并行原理引入计算机体系结构设计中，试图开拓一条设计和制造高 性能计算机的新路。1 9 7 5 年并行计算机系统l l l i a ci v 的研制成功和投入使 用标志着一个并行计算新时代的开始。但整个七十年代，并行处理的研制 北方交通大学硕士学位论文 和使用只限于少数国家的某些部门，还未能得到真正的发展。到了八十年 代并行处理技术才开始蓬勃发展起来并逐渐走向实用。十多年后的今 天，并行处理已成为计算机及其应用领域的研究热点，它的发展大大的加 快了计算机性能提高的速度，并使一些计算复杂度很高或计算量很大的科 学问题得到了较好的解决。目前包括中国在内的许多国家都非常重视并行 处理的研究和发展，并为此投入了大量的人力、物力和财力。 到目前为止，并行处理技术的研究已经走过了相当长的一段时间，也 取得了许多成果，其中最大的成果反映在并行系统的体系结构上。f l y n n 按指令流和数据流为标准将计算机系统分成了s i s d ，s 1 m d ，m i s d 和 m i m d ，其中m 1 s d 由于不符合实际而不曾存在过。从实际应用的情况来 看，得到普遍应用的并行系统分为如下四类：i 叫 1 、并行向量机系统 该类系统是最早出现的并行处理系统，可以称之为第一代并行处理系 统，以c r a y 系列、n e cs x 系列和f u j i t s uv p p 系列为代表，其特点是 采用基于流水线技术的向量硬件，实现向量操作的快速执行。早期的向量 机是以单处理机模式工作的。现代的超级计算机大多支持多处理机模式， 这种向量机又称之为多向量机( m u l t i v e c t o rp r o c e s s o r s ) 。这类系统的技 术已经成熟，尽管它们仍占有定的市场份额，但是已经没有多大发展前 途，对这方面的研究已不常见。 2 、基于共享存储的多处理机系统 基于共享存储的多处理机系统是由一组处理器通过互连网络共享统一 地址空间而构成的，尽管在编译系统、互连网络方面还有新的研究，但是 其技术已基本成熟，相对于其他并行处理系统而言，该类系统的单一地址 空间和共享存储器模型比较容易让用户接受，通用性较好，软件技术也相 对比较成熟，被认为是九十年代并行机的主流产品，在商业上取得了很大 的成功。特别是在企业服务器和i n t e m e t 服务器领域，s m p 系统取得了统 治地位，支持s m p 的操作系统有s u n 公司的s o l a r i s ，a t t 的u n i x s y s t e m v 4 o m p 版本，d g 公司的d g m x 等。但是共享存储多处理器的 总线或互连网络的带宽是有限的，可扩展性较差，要提高它所需付出的代 价很大，因此这类系统的规模不可能做得很大或取得非常高的性能，目前 一般的s m p 服务器最多可以做到1 2 8 个处理器，例如s g io d e n g e2 0 0 0 ， i ! 查窒望查堂堡主堂堡堡墨 s u nu l t r a s p a r c1 0 0 0 0 等，应用得最广泛的是4 1 6 个处理器的基于总线的 s m p 系统。 3 、基于分布存储器的大规模并行处理系统 该类系统由一组带局部存储器的处理单元和互连网络构成，局部存储 器只能由本地的处理器访问，和其他处理器的数据交换通过互连网络使用 消息传递的方式实现。由于采用了分布存储结构，这种系统的处理器数目 可以做得很大，不受统一地址空间的限制。 大规模并行处理系统( m p p ) 能提供很高的性能，但并未取得很大成 功。m p p 并行机早期采用专用的c p u 芯片，后来逐步被常用的工作站芯 片所替代，即便如此，m p p 并行系统中的节点机并没有运用工作站的技 术和产品。m p p 系统中各节点机具有明确的分工：一些节点机专用于i 0 服务，一些节点机专用于完成计算功能。各节点机通过专用的高速网络互 连起来。出于其专用性，为了开发支持软件和互连机制，需要巨大的初期 投资，市场风险太大，所以常常缺乏必要的投资。又因为m p p 系统实现 周期长，其节点机c p u 往往不能采用最新的产品，加之很少有程序员能 拥有m p p 环境，故其支持软件更显缺乏。因此，m p p 系统通常成本高， 缺乏灵活性，升级、维护困难。 4 、机群 机群系统是指利用商用通用网络将一组高性能工作站或高档微机按照 某种结构连接起来，在并行程序设计环境支持下统一调度的并行处理系 统。从结构和结点间的通信方式来看，它属于分布存储系统。这类系统的 计算节点是已有的商用工作站，主要利用消息传递方式实现工作站之间的 通信，由建立在一般操作系统之上的并行程序设计环境完成系统的资源管 理及相互协作，同时也屏蔽掉工作站硬件和网络的异构性。机群系统可以 是同构的，也可以是异构的。相对其他类型的并行处理系统而言，特别是 m p p 系统，工作站机群系统除了研制成本低，可利用原有资源，开发周 期短之外，还具有使用方便，配置灵活，易于扩展等优点。具有代表性的 机群系统有i b m 的s p 2 、m i c r o s o f t 的w o l f p a e k 以及b e r k e l e yn o w 等 等，国家智能计算机研究中心的曙光1 0 0 0 a 以及曙光- 2 0 0 0 1 和曙光2 0 0 0 1 1 也都属于机群系统。目前，机群系统己成为国内外学术界和工业界竞相研 究开发的热点，本文的研究主要着重于机群系统中的通信技术。 北方交通大学硕士学位论文 1 1 3 机群系统是并行处理领域中的一个重要的发展方向 机群系统的出现主要得益于以下三个方面技术的进步：1 、c p u 技 术。r i s c 技术的迅速发展，使得高档芯片构成的工作站和微机的性能越 来越高，现在速度最高的微机芯片已远远超过了过去传统大型机的速度， 而价格却在不断下降，这种性能价格比的不断提高，使得以工作站为主 体的机群系统以1 0 左右的价格实现或接近巨型机的性能成为可能。2 、 高速网络。高速网络技术的进步使得松散耦合系统的带宽得到大幅提高， 带有处理能力的网络接口和系统的通信机制有效的降低了通信开销，一方 面提高了并行效率，另一方面降低了并行系统的处理粒度。3 、并行程序 设计环境的开发。多种可移植并行程序编程环境已进入了实用阶段，如 e x p r e s s ，p v m ，p 4 ，m p i 等一批基于消息传递机制的并行程序编程环境 能够在各种工作站平台上运行，为用户提供统一的接口，屏蔽了底层的通 信细节，这就为应用程序的开发和移植提供了方便。 这些技术进步为工作站机群系统的产生创造了条件，之所以这类系统 得到了人们广泛的注意，其原因在于与其他并行处理系统相比，机群系统 具有以下五方面的特点： 用户投资风险小。传统巨型机或m p p 系统非常的昂贵，用户在购 置以后，若使用效率不高，系统性能发挥不好，相当于搁置或浪 费了大量资金。而机群系统就没有这种担忧，退步讲，即使对 某类应用问题并行效果不好，每台工作站照样可以作为独立的系 统使用，主要的投资不会浪费。 开发周期短。由于系统大多采用市售工作站和通用高带宽网络组 成，无需重新研制计算节点，可以充分利用传统的操作系统和编 译技术。研究工作的重点只是在一些机群系统的特定问题上，这 就节省了大量的研制时间。 系统造价低，升级容易。因为工作站或高档微机以及网卡是大批 量生产，其售价持续下降，而且不断有新的换代产品推出，用户 只需购置新的设备替代原有的即可构成新的升级系统。 扩展性好。从结构上讲，机群系统是基于消息传递方式的多计算 机系统，它的扩展性主要取决于网络的性能，而目前的各种互联 网络一般都具有很好的可扩展性。 i ! 塑奎望查堂堡主堂垡笙苎一 资源利用率高。通常对于个人工作站资源，无论是c p u 资源还是 内存资源，其利用率都是很低的，大部分时间处于空闲状态。这 些工作站构成机群系统后，在空闲时间里可以加载并行计算任 务，就可以充分利用工作站资源。另一方面，由于用户设备更 新，原有的一些性能较低的工作站可能搁置不用，而在机群中则 仍可以发挥作用，使用户的投资获得尽可能大的效益。 1 9 7 7 年，d e c 公司推出了以v a x 为节点机的松散耦合的机群系统， 并成功的将v m s 操作系统移植到该系统上。进入9 0 年代后，随着r i s c 技术的发展运用和高性能网络产品的出现，机群系统在性能，价格比、可 扩展性、可用性等方面都显示出了很强的竞争力，尤其是它在对现有单机 上的软硬件产品的继承和对商用软硬件最新研究成果的快速运用这两方面 表现出传统m p p 无法比拟的优势。目前，机群系统己在许多领域获得应 用。可以预见，随着s m p 产品的大量使用和高性能网络产品的发展完善 以及各种软硬件支持的增加和系统软件、应用软件的丰富，新一代高性能 机群系统必将成为未来高性能计算领域的一种主流平台。 1 1 4 机群系统中研究的主要问题 1 、通信问题 众所周知，通信技术是提高机群系统性能的关键，对系统的并行加速 性能、并行计算效率、可扩展性以及系统的应用范围有十分重要的影响。 减少通信开销，提高通信速度，使系统的时间资源主要用于计算是机群系 统中研究的重要课题，提供低延迟、高带宽的通信支持几乎是所有研究中 的机群系统的共同目标。 2 、负载均衡和调度策略问题 在机群系统中，一个大的任务往往由多个子任务组成。这些子任务被 分配到各个处理节点上并行执行，称之为负载。对于由异构处理节点构成 的机群系统而言，由于各节点的处理能力不同。相同的负载在其上运行的 时间和资源占有率都不同。因此，准确的负载定义应是绝对的负载量与节 点处理能力的比值。当整个系统任务较多时，分配给各节点的负载可能并 不均衡，整个系统的利用率就会降低。有效的将各个子任务均衡的分布到 不同的处理节点进行并行计算，可使各节点的利用率达到最大。 j ! 查銮望奎兰堡主堂垡堡塞 一 从任务分配决策的时机讲，负载均衡技术可分为静态和动态两类方法 1 4 】。静态方法是在编译时针对用户程序中的各种信息以及机群系统本身的 状况对用户程序中的并行任务做出静态分配决策，程序运行时将任务分配 到相应节点。动态方法是通过分析机群系统的实时负载信息，动态的将任 务在各处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。 3 、并行化问题 目前广大应用部门用c ，c 十+ 和f o r t r a n 等语言编制了大量的应用 程序，这些应用程序，如果不用修改，通过并行编译系统就能自动生成能 在并行系统上运行的并行代码，当然是最理想的。但是要自动识别串行程 序中的并行性，并不是一件容易的事。对有些问题，串行程序的结构是清 楚的，可以手工对串行程序作少量的修改，从而实现并行化。综合起来， 并行化问题在机群系统上有这么几条解决途径：预编译技术、并行函数类 库方法和并行化编译技术。 预编译技术是在传统语言编译器之前设计一个预编译器，通过预编 译，将扩展语言的并行成分用传统语言加以实现，再通过传统串行编译器 编译，生成可并行执行的代码。并行函数类库方法无需改变传统语言和编 译器，只是为程序员提供并行程序开发所需的函数库或类库，在编译生成 可执行代码时再将其链接进来，生成并行代码。并行化编译技术在机群系 统中主要是针对应用程序的中、粗粒度的并行性，与传统的向量化方法有 很大不同。 4 、并行调试技术 并行程序的调试要比串行程序的调试复杂得多，主要面临的是并行程 序的不确定性，通信以及复杂的全局状态等问题。对于基于消息传递机制 的机群系统而言，并行程序中会出现消息死锁、消息乱序等错误，调试时 必须费力的在通信语句前后设立断点，从而确定通信的内容，对于有大量 通信和复杂通信模式的应用程序来说，做起来就更为困难。目前，常用的 并行调试技术主要有记录与重放、动态分析和可视化三种【5 】。 5 、并行程序设计环境 广义的说，并行程序设计环境应包括硬件平台、操作系统和并行程序 语言、编译、编程、调试及性能分析工具等，狭义的并行程序设计环境则 仅指系统核心之上的工具软件部分。在这里主要讨论后者的情况，目前在 分布存储多机系统及机群系统上用的最广泛的是p v m 和m p i 。 p v m 的开发最早开始于1 9 8 9 年春天，它的开发队伍包括美国橡树岭 国家实验室( o r n l ) 、t e n n e s s e e 大学、e m o r y 大学以及c m u 等单位。 p v m 是一套并行计算工具软件，支持多种体系结构的计算机，能够在大 多数流行工作站系统、m p p 系统和向量机上运行，这些机器通过网络互 连起来，给用户提供一个功能强大的分布存储计算机系统。p v m 支持 c 、c + + 和f o r t r a n 语言，由于p v m 是免费的，因此使用范围非常广 泛。 m p i 是一个新的消息传递标准，由m p i 讨论组在1 9 9 2 年至1 9 9 4 年举 行的一系列会议上逐渐产生。m p i 能用于大多数m p p 系统和工作站机群 系统，并达到较高的并行效率。m p i 定义统一的编程接口，将通信部分独 立出来，由具体的系统来实现，这样它既具备了公共软件包的通用性，又 具有厂家专用软件包的高效性。 除了上述的两种并行程序设计环境，基于消息传递机制且适合机群系 统的并行程序设计环境还有美国a r g o n n e 国家实验室开发的p 4 ，y a l e 大 学开发的l i n d a 以及p a r a s o f t 公司开发的e x p r e s s 等，这些并行程序设计环 境都各具特点，但是他们没有p v m 和m p i 应用得广泛。 6 、故障恢复与容错 随着机群系统逐渐推广，人们对可靠性、可用性的要求逐渐提高，而 许多并行应用程序的运行时间比较长，且需要在多个节点上同时运行，这 样，一旦某个节点出现故障，往往导致整个机群系统失败，最终结果是应 用程序必须重新执行，导致了大量时间的浪费。 为了避免这种情况，就要求在出错的时候系统能够自动恢复错误，即 系统提供故障恢复和容错功能。目前常采用检查点设置和卷回恢复技术来 实现容错要求，即在程序运行过程中设置检查点，保存进程状态中决定程 序运行正确性的关键内容，当系统出现故障后，程序卷回到最近的检查点 处接着执行，而无须从头开始。这是一种后向恢复技术，通过时间冗余， 使系统从瞬间及间隙故障引起的失败中自动恢复，辅助恢复永久故障，并 实现进程挂起恢复及进程迁移。注意，卷回的各目标检查点所保存的进 程状态必须与当时的通信通道状态组成一致性全局状态，并采用同步卷回 技术以避免活锁。考虑到实际应用效果，必须考虑减少检查点保存所带来 j 匕方交通人学硕十学位论文 的jr 销，包括时问、空i 日j 卜的月：销。 1 2 机群中的通信系统 1 2 1 并行处理系统中通信技术的发展 在并行处理系统中，通信技术是一项十分关键的基础技术，对系统性 能起着决定性的影响，在通信技术有了很大发展的今天，其对于并行处理 系统设计者而占仍然是个难题。尽管随着器件水平的提高和w o r m h o l e 、 c u t t h r o u 2 h 等寻径技术的出现，使得互连网络的交换延迟和网络吞吐量得 到了很大的改善，a c t i v em e s s a g e s 、精简通信协议等新的协议处理机制减 小了通信系统的协议处理开销，但是仍不能满足并行处理系统对通信技术 f 1 益增长的需求。在今后相当长的时间内，通信技术仍将是并行处理系统 研究中的一个十分活跃的领域。 大规模并行处理系统和机群系统都属于分布存储多机并行处理系统， 由一组节点与互连网络组成，互连网络是节点之问通信的桥梁，节点之间 的数据、控制信息通过它来完成交换，这就注定了互连网络的通信性能是 决定系统并行效率的主要因素。随着网络技术的进步，网络的物理带宽有 了很大的提高，从1 0 m b p se t h e m e t ，到1 5 5 6 2 2 m b p s 的a t m ，1 g b p s 的 g i g a b i te t h e r n e t ，1 2 8 g b p s 的m e r i n e t 等，开关的交换延迟每级已不到1 微秒，但是，我们更关心的是应用程序中可以看到的性能，因此通信协议 和并行程序设计环境的通信性能近年来越来越引起人们的重视。根据研究 内容的侧重点不同，对通信技术的研究可分为三个阶段：第一阶段的研究 重点是互连网络的拓扑结构和寻径算法，第二阶段的重点是流控制技术， 第- ! 阶段重点是研究通信协议的处理机制。 第一阶段的主要工作是构造新颖的互连网络拓扑结构及其控制算法， 关注的主要是网络的连接能力，重点是构造在某类条件下的无冲突访问方 案和网络的可重排性，但是，这些拓扑结构和控制算法存在一些共同的问 题：缺乏通用性、速度慢、不易于v l s i 的实现。 第二阶段通信技术的进步主要体现在流控技术上，最主要的是1 9 8 6 年提出的w o r m h o l e 技术，在此基础上发展起来的系统控制方案被认为是 当今最佳的互连技术之一1 6 j 。其显著特点是充分利用现有i c 技术，在简 单的拓扑结构上，采用硬件支持的动态流控制技术和简单的寻径算法，使 北方交通大学硕士学位论文 互连网络在通信延迟和吞吐量方面都得到了很大的进步。在此阶段比较突 出的贡献还有虚通道流控技术【7 i 、虚网络和平面可适应算法1 8 j 等。 第三阶段的研究热点是如何减少系统软件在通信方面的开销，包括研 究新的通信机制和通信协议、精简传统协议的实现，目的是尽量缩小底层 硬件通信性能和上层并行编程环境或应用程序可见通信性能的差距。最为 突出的成就是v o ne i c h e n 等人提出的a c t i v em e s s a g e 机制【9 】。这一阶段研 究的基础是：现在的通信延迟中，硬件的延时只占很小的比例，而协议处 理、数据拷贝、通信管理、同步等软件开销更为突出。a c t i v em e s s a g e 的 主要思想是让消息本身带有处理消息的信息，让消息的传递和节点的计算 能够重叠起来。这种机制在数据传输、同步、出错重传和虚拟网络等四个 方面都有很大的改善，大幅地减少了消息的处理和传输延迟。该阶段研究 的着眼点多是在具有独立协议处理器的智能网络适配器上设计新的协议机 制，以取得低延迟、高带宽的通信性能。 1 2 2 机群系统中通信系统的重要地位 从定义上来理解，并行处理无非是各个处理节点同时并行的处理同一 应用问题的不同部分，因此，对于给定的应用问题，在节点数一定的条件 下，一般有三个方面的因素决定并行处理的速度：一是对应用问题求解算 法的优劣；二是处理节点软硬件的速度；第三，应用问题的不同部分之间 一般存在着定的数据依赖关系，故对于一个实际的并行处理系统来说， 它的各个处理节点之间尚需有一种联系系统，这就是连接各处理节点的互 连网络以及建立于其上的通信软件，他们的速度和效率，也是影响整个并 行处理性能的主要因素之一。由此看来，研究机群系统的机间通信问题， 提高通信的速度和效率，对于提高整个系统的性能具有非常重要的意义。 由于通信系统在机群系统中占据着十分重要的地位，机间通信在近几 年来始终是人们研究的一个热点，我们可以这样认为：通信系统既是推动 机群系统发展到今天的一个主要动力，同时也是其继续发展的一个主要瓶 颈。在机群系统中，尽管单个节点的性能和整个系统中所有节点的累加性 能可能很高，但其运行时所能获得的实际性能却要受到一些因素的制约， 其中，通信系统的效率就是影响整个系统实际性能的一个关键。随着高性 能通信网络和通信软件的出现以及他们在机群通信中的运用，机群系统越 来越成为一种较为理想的并行处理平台并得到了较大的发展。反过来，高 北方交通大学硕士学位论文 性能机群系统的进一步发展又对通信系统提出了更高的要求。从应用软件 的角度来看，实现单一系统映象中的单一文件系统和单一内存映象等都需 要高性能的通信系统。虽然目前对机群通信系统的研究已取得一些成果， 但应用程序对计算机性能的需求总是无止境的，因此，机群中的通信系统 将是未来几年人们研究的一个热点。 1 3 论文的目的、内容和贡献 1 - 3 1 目的 对已有的通信技术进行系统的研究，掌握机群系统中通信系统设计实 现的原则、方法和策略。对目前存在的通信瓶颈进行分析和研究，进行改 进和优化。 1 3 2 论文内容 本文是在广泛了解机群通信技术的基础上，研究了机群高效通信系统 设计实现的原则、方法和策略，特别是在通信软件方面做了深入的研究， 整篇文章共分为六章： 第一章首先回顾了并行处理取得的成就，系统的介绍了机群的发展及 其所面对的主要问题，阐述了机群通信系统的发展状况及其在机群系统中 的重要地位。 第二章对机群通信系统作了整体的概述，对其结构、功能、特点以及 常用的互联网络作了系统地介绍。并对机群通信系统的评价进行了讨论， 包括通信开销对系统的影响、描述通信开销的模型等。 第三章主要介绍了机群通信技术，分析了机群系统的通信开销，探讨 了影响机群通信性能的主要因素，以及通信系统设计中的关键问题及其解 决策略，从全局的角度，讨论了通信系统的设计策略和目前的主流技术， 并给出了几个典型通信系统的介绍和分析。 第四章介绍了一种简单可靠通信协议( s r c p ) 的设计思想，讨论了 该协议的提出理由、设计目标、原理以及协议内容等。 第五章系统地介绍了s r c p 的具体实现，重点讨论了一些关键部分的 实现细节，例如通信接口、同步机制、缓冲区管理和守候进程等，同时概 要的论述了其他一些辅助功能的实现，最后分析了s r c p 的通信开销以及 北方交通人学硕士学位论文 设计实现中的一些不足之处。 第六章对全文进行了总结，提出】，进一步的工作。 1 3 3 论文贡献 、对机群通信系统的发展、组成、功能和特征等各个方面进行了系 统地描述，分析了几个常用的通信系统评价模型，在此基础上，给出了评 价机群通信系统的。般方法。 二、讨论了影响机群通信性能的主要因素，针对系统设计中的一些关 键问题给出解决方法。分析了机群通信系统的设计策略，给出了在一个高 效通信系统中，互联网络、网络接口和通信软件应该具备的特性。 三、广泛而深入地研究了一些具有代表性的机群通信系统，分析了这 些系统的设计思想、实现技术以及可借鉴的先进之处，总结并给出了开发 高效机群通信系统的先进经验和技术。 四、在研究了传统的a c k r e q 应答机制的基础上，提出了种隐含 应答结合双向组确认机制的通信可靠性保证策略。 五、设计了一种新的通信协议，该协议结合了t c p 的可靠性和u d p 的灵活性，适用于传统的e t h e r n e t 局域网，论文给出了它的设计思想以及 具体实现。 ! ! 查奎望查堂堡主兰焦迨茎一 第二章机群通信系统概述 本章概述了机群通信系统的结构、功能和特点，并介绍了机群通信系 统的几个评价模型和评价方法。 2 1 机群通信系统的介绍 2 1 1 通信系统的结构、功能 通信系统是指连接机群各处理节点的通信硬件以及建立于其上的通信 软件，它的主要功能就是在各处理节点上应用程序的进程之间提供高效、 可靠和有序的通信服务。 从硬件上来看，通信系统主要包括高速互连网络和网络接口两个部 分，其中互连网络用于完成各节点之间消息包的传递，一般具有低延迟和 高带宽的特点。网络接口的功能是实现处理节点与互连网络之间的连接。 典型的结构模型是用一块插在工作站y o 总线上的网络接口将主机处理器 和存储系统连接到网络上，互连网络的结构取决于所使用的网络类型，目 前一些机群使用的网络，按传输机制的不同可分为两类：一类是共享介质 网络，最常见的有l o m b p s 、1 0 0 m b p se t h e m e t 。其聚合网络带宽和单一的 网络带宽是一样的，通信性能会随着网络负载的增加而下降。另一类是开 关网络，例如1 5 5 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 g b p s 的带交换机的e t h e r n e t 。与共享介质网络不同的是，开关网络的聚 合网络带宽比单一的网络带宽要高得多，除了开关的交换延迟影响外，性 能不会因网络负载的增加而降低很多。因此，开关网络具有很好的可扩展 性，构成系统的规模可以比共享介质类网络大得多，适当的设置开关连接 结构还可以支持特定通信模式的系统。 从软件上来看，从网络接口硬件到并行应用程序之间，通信系统通常 由从下到上四个层次的软件组成：设备驱动程序、底层通信协议、高层通 信协议和并行程序计算环境。其中，低三层都是在系统空间运行，设备访 问、缓冲管理、多路复用和中断处理直接由操作系统实现。在操作系统之 上的是低层通信协议，一般负责链路包的装配和与网络接口的数据交换 等，例如在e t h e m e t 中的链路层( d l p i ) 和网络层( i p ) ，a t m 的 a a l 5 层，m y r i n e t 的a p i 层。高层协议层主要是处理消息的可靠性、有 北方交通大学硕士学位论文 序性和消息的拆包和组包，比如e t h e r n e t 的传输层( t c p ) ，a t m 和 m y r i n e t 上的传输层仿真。并行程序计算环境除了为并行应用程序提供通 信接u 外，还要完成任务分配、管理、数据表示等其他任务。 2 1 2