（计算机软件与理论专业论文）基于smp结点的多重通信协议研究与设计.pdf

海大学坝j 学位论文摘要集群系统以其结构可扩展性好，具有高效的计算性能等特性已成为并行处理发展的主流；实现系统内消息的快速传递，提高进程间通信的性能是集群式高性能计算领域的个重要研究方向。传统的通信协议对数据的处理通过协议栈来完成的，其一次的消息传递需要进行多次数据复制工作，并且要求系统切换于用户状态和核心状态之间。这些操作将严重影响到集群计算机的通信性能。如果绕开操作系统实现用户层的通信机制，采用高效的通信结构和精简的通信协议( 前提是网络硬件本身的容错性能足够好) ，就可以真正做到减少通信延迟，提高网络带宽的利用率。基于单c p u 结点的集群通信协议已发展得较为成熟，而基于s m p 结点的集群系统以其较高的性能价格比和较好的容错能力成为当前研究的一个热点。研究机内与机间通信问题，提高通信的速度和效率，对于提高整个系统的性能具有非常重要的意义。本文主要从提高集群计算机通信效率的角度出发，针对s m p 结点集群的物理特性结构，基于共享内存通信和用户层通信协议，对于集群计算机多重通信协议进行了研究探索，并在此的理论基础上进行了协议的设计、实现、形式化描述与验证、以及相应的协议点对点通信延迟性能测试。实验结果表明，多重通信协议有效的利用了s m p 结点的特性，有效地减少通信关键路径上的开销，从而降低消息传递的延迟，提高了通信效率。关键词：集群系统，共享内存，用户层通信，通信协议，形式化描述i ：海大学硕士学位论文a b s t r a c tc i u s t e rs y s t e m sa r ep o p u l a re n v i r o n m e n t sf o re x e c u t i n gp a r a l l e la p p l i c a t i o n sd u et ot h e i re x t e n s i b i l i t ya n dh i g hp e r f o r m a n c e p r i c er a t i 0i nr e c e n ty e a r s t oa c h i e v ef a s t e rt r a n s f e ro fm e s s a g ei n s i d ec l u s t e rs y s t e ma n dt oi m p r o v et h ep e r f o r m a n c eo fc o m m u n i c a t i o nb e t w e e np r o c e s s e sa r et w ov e r yi m p o r t a n tp r o b l e m si nt h ec l u s t e rb a s e dh i g hp e r f o r m a n c ec o m p u t i n gf i e l d s t h et r a d i t i o n a lc o m m u n i c a t i o np r o t o c o l st r a n s a c td a t ab yp r o t o e 0 1s t a c ka n dh a v em a n yt i m e so p e r a t i o n so fd a t ac o p yd u r i n go n em e s s a g ei n t e r c h a n g e a n ds y s t e mc h a n g i n gb e t w e e nu s e rs t a t ea n dk e r n e ls t a t ea r er e q u i r e d t h e s eo p e r a t i o n sw i i li n t e r f e r et h ep e r f o r m a n c eo fac l u s t e r s i n c eu s e ri e v e lc o m m u n i c a t i o nm e c h a n is mi n t r o d u c e dh i g he f f i c i e n c yc o m m u n i c a t i o ns t r u c t u r e sa n dc o m m u n i c a t i o np r o t o c 0 1 s ( b o t hb a s e do nag o o de n o u g hp e r f o r m a n c eo fn e t w o r kh a r d w a r e ) ，i tc a nr e a l l yr e d u c et h ed e l a va n di m p r o v et h eu s i n gr a t i 0o fn e t w o r kb a n d w i d t h t h ec o r i l m o n i c a t i o np r o t o c o lb a s e do nc l u s t e r so fs i n g l ep r o c e s si sv e r ym a t u r e d s i r i c ec l u s t e ro fs m p s ( c l u m p s ) h a sh i g hr a t i 0o fp e r f o r m a n c ea n dc o s ta n dg o o df a u l tt o l e r a n c ea b i l i t y ，i tb e c o m e sah o tp o i n ti nc u r r e n tr e s e a r c hf i e l d s i th a sv e r yi m p o r t a n ts i g n i f i c a n e et or e s e a r c ht h ep r o b l e mo fc o m m u n i e a t i o ni n t e r n o d e sa n di n s i d et h es a m en o d ea n dt oi m p r o v et h ec o m m o n i c a t i o ns p e e da n de f f i c i e n c y b e c a u s ec o m m u n i c a t i o ni st h ek e yo fp e r f o r m a n c eo ft h ew h 0 1ec l u s t e rs y s t e m am u l t i p r o t o c o lm e c h a n i s mi sp r e s e n t e di nt h i st h e s i s w h i c hc o n s i s t so fas h a r e dm e m o r yb a s e dp r o t o c o la n dau s e r l e v e lp r o t o c 0 1 h o wt h ep r o t o c o li sd e s i g n e d ，i m p l e m e n t e d ，t e s t e da n di t sf o r m a l l yd e s c r i p t i o na r ei n t r o d u c e di nt h i sa r t i c l e w ee n c a p s u l a ei n t e r p r o c e s sc o m m u n i c a t i o no nac l u m pt h r o u g hau n i f o r mm e s s a g ep a s s i n gi n t e r f a c et h a te x p o s e st h ep e r f o r m a n c eo ft h eu n d e r l y i n gh a r d w a r e a tl a s t ，o u rm u l t i p r o t o c o lw a st e s t e db y eo u rc l u s t e ro f “z i q i a n g2 0 0 0 ”i ns h a n g h a iu n i v e r s i t y t h et e s t ss h o w e dg o o dp e r f o r m a n c ea n ds c a a b i l i t yo ft h ep r o t o c 0 1 k e yw o d s ：c l u s t e r ，s h a r em e m o r y ，u s e rl e v e lc o m m u n i c a t i o n ，c o m m u n i c a t i o np r o t o c o l ，f o r m a l l yd e s c r i p t i o nv原创性声明本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：越垒垦塑日期工2 ：尘：三厂本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。( 保密的论文在解密后应遵守此规定)日期：二乙! 竺：第一章绪论1 1 计算机系统结构的发展从一九四六年世界上第一台数字计算机e n i a c 出现到现在的五十多年中，电子器件制造技术的进步和计算机体系结构的发展极大地推动了计算机性能的提高。在计算机从电子管发展到v l s i 的四个阶段中，器件的性能的提高使得计算机的处理能力飞速增长。目前，器件的性能虽仍在不断发展，但已难以满足计算的需求。研究并行可扩展的计算机体系结构成为提高计算机系统性能的一个重要途径。按照用指令流和数据流进行分类的f l y r m 方法，计算机系统可分为四大类：单指令流单数据流系统( s i s d ) 、单指令流多数据流系统( s i m d ) 、多指令流单数据流系统( m i s d ) 、多指令流多数据流系统( m i n d ) 。s i s d 系统是指传统的顺序处理计算机。后三类从广义上来说均属于并行处理系统，其中，s i m d 系统是多个处理单元在同一控制器下工作的计算机系统，系统中各处理单元执行相同的指令流，但作用于不同的数据流上，如向量计算机和阵列计算机均属此类。由于系统在同一控制器的控制下进行工作，各计算部件必须执行相同的指令，就限制了这类系统的应用范围。m i s d 系统在概念上说来可以存在，但这种在指令级并行、数据级串行的系统目前尚无实例。1 2 集群计算随着科学技术的飞速发展以及计算机应用领域的日益扩大，对计算机系统的处理能力，计算速度提出了更高更新的要求。为了大幅度提高计算机并行处理能力，在计算机系统结构技术上必须有所突破，寻求有利于开发高度并行功能的计算模型和相应的现代计算机系统结构。无论是p v p 、m p p 、n c c n u m a 、c c - n u m a 还是s m p ，其共性是：需要从底层到顶层实现整个计算机系统。由于它们的开发是芯片级的，技术难度大，硬件研制周期很长；另外，由于缺乏通用的商业软件的支持，需要重写系统软件，软件研制周期也很长。这些因素除了增加了研制成本外，还降低了高性自e - + t 算机的竞争力，因为在研制开始时所使用的很先进的芯片和技术，在研制结束时却会因为周期太长而失去了领先性。相比之下，集群( c l u s t e r ) 计算机系统能够以较短的研制周期、集成最新技术、汇集多台计算机的力量，达到了较高的性能价格比，其技术发展在国际上受到重视。它通过高速互连网络把通用的计算机( 如高档计算机、工作站或p c 机) 连接起来，采用消息传递机制( m p i 、p v m 等) ，向最终用户提供单一并行编程环境和计算资源，因此它通常也被称作“计算集群”，“工作站群”，“工作站网络”，“网络并行计算”等。集群计算机技术是在九十年代中期才开始发展的，但其发展速度非常迅猛，我们从国外高性能计算机权威网站公布的“全球5 0 0 强( t o p 5 0 0 ) ”排行榜可以比较清楚地看到它的发展趋势。1 9 9 7 年6 月时只有1 台c l u s t e r 进入了t o p 5 0 0排行榜，而到2 0 0 0 年1 1 月已有2 8 台。无论其数量、所使用的处理器数目、峰值速度，还是l i n p a c k 指标，都呈现指数增长，如图1 1 所示。l 海大学坝i 学位论文一图】- it o p s o o 中高性能计算机发展趋势最初，集群计算机系统的使用效率只有3 0 左右，严重影响着它的发展。随着高速通信、体系结构、并行算法等方面研究的不断取得进展，集群计算机系统的使用效率已经取得了比较满意的结果，已达6 2 以上，逐步接近m p p的效率，如图1 2 所示。图i - 2t o p s 0 0 中c l u s t e r 的数量和性能不过，也应清楚地认识到，虽然集群计算机取得了很大进展，所占的份额在不断提于i ，但其无法完全替代m p p 。虽然m p p 的研制成本高，研制周期长，但要建立关系到国家利益的峰值速度极高的高性能计算机时，还是以采用m p p为主。集群计算机可以从狭义和广义的角度进行划分。狭义地讲，根据构成结点的不同，可以分为p cc l u s t e r 和工作站c l u s t e r 。根据研制理念的不同，可以分为n o w 类型c l u s t e r ( 追求高速通信，进行全局资源管理，采用时钟周期“窃取”技术来利用空闲计算机的资源) 和b e o w u l f 类型c l u s t e r ( 尽可能使用现成的硬件、免费系统软件、基于t c p i p 建立通信库、不考虑“窃取”时钟周期) 。广义地讲，由c l u s t e r 本身作为构成结点的c l u s t e r ( 称为h y p e r c l u s t e r ) 、由s m p结点构成的c l u s t e r ( 称为c l u m p s 。】或c o n s t e l l a t i o n s ) 、a s c i 机以及元计算网格，都可以称作c l u s t e r 。美国最有影响的集群计算机系统是b e r k e l e y1 9 9 7 年推出的n o w 系统。它由1 0 0 个s u n 工作站用速度为1 6 0 m b s 的m y r i n e t 联结而成。它的峰值速度为每秒3 3 0 亿次浮点运算。集群计算机系统的应用面非常广，除了作科学计算外，还可以作事务处理，如作w e b 服务器、网络文件服务器、超级m a i l 服务器以及海量廉价存储系统等。我国在研制高性能计算机方面，已经取得很多成就。这些高性能计算机主要可以划为三大类：1 、p v p 向量型超级计算机，如国防科技大学研制的银河i ( 1 亿次秒) 、银河1 1 ( 1 0 亿次秒) 。2 、m p p 大规模并行处理超级计算机，如国防科技大学研制的银河i i i( 1 3 0 亿次秒) 、中国科学院计算机技术研究所研制的曙光1 0 0 0 ( 2 5 亿次秒) 、中国江南计算机技术研究所研制的神威i ( 3 8 4 0 亿次秒) 。海大学硕上学位论文3 、集群计算机，如中国科学院计算机技术研究所研制的曙光2 0 0 0 i i( 1 1 0 0 亿次秒) 、曙光3 0 0 0 ( 4 0 3 0 亿次秒) 、清华大学研制的t h n p s c 一1( 3 2 0 亿次秒) 、上海大学研制的自强2 0 0 0 ( 4 5 0 0 亿次秒) 以及正在研制的自强3 0 0 0 ( 预计2 万亿次秒) 等。当前，s m p 结点逐渐成为组成集群系统的主流设备。无论是在高端的服务器中，还是在低端的p c 集群上，采用s m p 结点能够提供更高的性能价格比。越来越多的研究都集中在基于s m p 的集群系统( c l u m p s ) 。c l u m p s 是近十年来高性能计算机体系结构发展的一个潮流。不论是超级计算机、大型机还是个人微机系统，其体系结构的发展都逐渐汇集到c l u m p s 结构。图1 3给出了这样一个发展的趋势。在初始的阶段，不同体系结构的系统按其各自的发展趋势向多处理器结构发展。大型机逐渐发展为基于s m p 的服务器；向量机逐渐发展为m p p 结构，进而发展为c c n u m a 结构的服务器和超级计算机；微机也向多处理器协同工作( 处理器池) 的方向发展，逐渐演变为n o w 结构。随着处理器的性能的不断提高，系统的整体性能也随之提高。i 一( j 【j r 0 “e s s f ) r1 ) 1s e dsl 】p e l - c o n l l u t ( m l 1 s )m o osserh t l 5 【、d 湖v t - toll 】sto r s ( ( 、1 u m p s )lim fc 1 ( t ) t ( ) c t 。h+m l c r ( o m 1 ，c l u s to r s ( n o w s )图1 3 计算机体系结构发展趋向s m p卜舸人学坝卜学位论文之后，器件的发展不再能满足系统性能提高的要求，大规模的处理器池或处理器阵列的扩展性和效率也制约着其性能的提高。因此，n o w 、s m p 服务器和c c n u m a 系统逐渐汇集到c l u m p s 结构。c l u m p s 优于s m p 服务器和c c - n u m a 结构之处在于s m p 服务器与c c n u m a 结构的单一系统结构能够高效地支持应用，但是同时也会出现单一故障点的问题。虽然一些机器提供了系统分区( p a r t i t i o n ) 的功能，但是c a c h e 致性的共享内存使得系统中的故障会影响整个系统的运行。而c l u m p s 则能较好地解决这一问题。c l u m p s能够以较低的价格提供一个较优的性能和较好的容错能力。对比n o w 结构，山于采用具有多处理器s m p 结点，c l u m p s 能够以较少的结点数提供较高的性能。这能够有效地降低系统的管理开销。同时，采用s m p 结点也能提高s m p结点内部处理器间的通信性能，从而使整个系统的性能提高。1 3 影响集群通信效率的因素对于集群式计算机来说，微处理器和网络技术的进步是性能提高的基础，应用和通信的中间件的开发才是集群应用的关键。一般来说并行应用程序不外乎计算和通信这两个部分。对于结点间数据交换占据很大比重的通信密集型问题，由于数掘交换频繁，运算部分常常因为等待结果而被阻塞缩短数据传输的时间，提高系统的通信效率就很可能极大地改善并行程序的性能。影响通信子系统性能的主要因素有：通信的硬件( 包括结点存储器、f 0 结构、网络接口和网络本身) 、通信软件( 包括通信协议的结构和算法) 和提供的通信服务机制( 包括消息传递、流量控制、拥塞控制和出错处理等) 。在集群系统中软件开销通常占据了主要的通信时间，如果没有高效的通信软件，即使是采用了高速的网络和网络接口设备，通信效率也难以取得明显改善。另外，如果通信软件的处理中包含大量复杂的服务也将会明显的延长数据发送和接收的海大学坝】j 学位论文时间。所以，要在现有的硬件条件上取得最佳的通信性能，最有效的方法就是改进集群系统的通信软件。通信软件的开销主要来源于( 1 ) 要遍历多个协议层，消息传递时要完成多个存储器之间的数据拷贝：( 2 ) 通信软件要完成边界保护、操作系统在用户层和核心态之间切换；( 3 ) 特殊通信服务的处理时间。一次通信过程包括发送和接收两个部分。发送时用户程序向系统请求发送，系统建立连接( 以面向连接的数据传输t c p i p 为例) 并且对要发送数据进行封装，最后发送到网卡的缓冲区；接收时系统处理接收到的包并且把它恢复成用户程序需要的数据。在i s o o s i 的7 层通信模型中，只有物理层( p h y s i c a ll a y e r )是关于网络接口硬件的协议，其他6 层都由系统软件以及用户程序来实现。数据传输可以直接从网络层和传输层开始。在t c p i p 协议中，连接建立之后数据的发送i 寸 l 电口f ：( 1 )接受用户数据到系统缓冲区的s k b u f f e r( 2 ) 在系统缓冲区为数据构造口包头，并产生c r c 校验和( 3 ) 调用驱动程序传输数据到网络接口卡，数据在此被拷贝构成完整的数据包：( 4 )网络接口卡发送数据。f ：海大学硼十“学位论文可见，数据要经过至少三次拷贝和一次c r c 校验和的计算才能传到网络接口卡的缓冲区发送。从上述分析可以看出，通信软件的主要开销包括了如下因素：数据拷贝：在传统的通信结构中，应用程序具有各自的消息缓冲区，同时系统还维护一个统一的系统缓冲区，应用缓冲区的消息数据都必须经过系统缓冲区进出网络接口。从用户层到系统核心需要进行一次报文复制，从系统协议栈到网卡发送缓冲区也需要数据复制，另外，在协议处理过程中，协议层之间也会出现数据在内存中的复制。状态切换：在多进程的操作系统中，产生系统调用后，系统会由用户态切换到核心态运行。为了实现对应用程序工作环境的保护，系统会对应用程序的现场进行断点备份，这包括对各个工作状态寄存器、进程上下文等的保存。在系统调用结束后，系统还要恢复应用程序的环境并切换回用户层状态。传输过程中，频繁的系统状态切换会消耗大量的c p u 周期进行现场保护和恢复。数据封装：为了实现网络传输协议，数据在传输之前需要打包，添加包头、包尾信息和冗余校验信息；数据包接收后还要对封包数据进行拆解，提出协议的信息，取出真正的数据。差错控制：数据在发送前要计算至少一次的c r c 校验和，在接收后被校验一次。一旦出现数据传输错误，系统还要采用延时重发的技术为数据包重发，耗费更多的时间。另外，传输层的流量控制等服务都将作为软件开销的一部分而占用系统c p u 资源的传输时间。通过上述分析可以知道，由于传统的通信协议对数据的处理通过协议栈来i 二海入学坝卜学位论义完成的，所以一次的消息传递需要进行多次数据复制工作，并且要求系统切换于用户状态和核心状态之间，这些操作将严重影响到集群计算机的通信性能。这些复杂的协议处理对于不可靠的网络连接确实必不可少，但是如果在硬件可靠性高同时又具有简单路由的集群系统中，很多工作都是不必要的。为了提高集群的通信性能会很自然的想到去修改通信协议，但是如果只是精简协议，最多只能减少协议栈中的处理耗时但却不能从根本上避免数据的多次复制和核心调用的延迟，所以很难利用高速网络潜在的通信性能。如果绕开操作系统实现用户层的通信机制，采用高效的通信结构和精简的通信协议( 前提是网络硬件本身的容错性能足够好) ，就可以真正做到减少通信延迟，提高网络带宽的利用率。降低通信部分的开销，提高数据发送接收效率，开发真正适合于高性能计算的通信系统在高性能计算领域具有深远的现实意义。1 4 集群通信协议国内外研究概况随着高性能通信网络和通信软件的出现以及它们在集群中的运用，集群系统才真正成为一种较为理想的并行处理平台并得到了较大的发展。集群系统的高效通信子系统是十分重要的，因为集群系统有更高的结点复杂性，结点之间物理线路很长，导致互连网络延迟很长。同时，也带来了线路的可靠性、安全性等问题。它们都需要由通信协议及其实现的通信软件和网络服务来解决。分布式应用程序所需的通信是多样化的，从点到点通信到多播通信，且能支持成批数据传输、流数据、组数据等等。传统的集群通信是建立在普通低速的局域互连网和t c p i p 协议的基础上。其通信性能低下，只适用于运行串行程序和通信量不大的粗粒度并行程序。但是在现代集群计算机中，它的通信软件使用专用网络的集群计算机通信协议，提供了快速而可靠的结点间以及与外界数据通信的手段。它往往使用通过绕开完成的，所以次的消息传递需要进行多次数据复制工作，并且要求系统切换于用户状态和核心状态之间，这些操作将严覃影响到集群计算机的通信件能，这些复杂的协议处理对于不口j 靠的网络连接确实必不可少，但是如果在硬件可靠一卜高同叫又具有简单路由的集群系统中，很多工作都是不必要的。为了提高集群的通信性能会很自然的想到去修改通信协议，但是如果只是精简协议，最多只能减少协议栈中的处理耗时但却不能从根本上避免数据的多次复制和核心调用的延迟，所以j 艮难利用高速网络潜在的通信性能。如果绕开操作系统实现用户层的通信机制，采月高效的通信结构和精简的通信协议( 前提是网络硬件本身的容错性能足够好) ，就口j 以真正做到减少通信延迟，提高网络带宽的利用率。降低通信部分的开销，提高数据发送接收效率，开发真正适台于高性能计算的通信系统在高性能计算领域具有深远的现实意义。1 4 集群通信协议国内外研究概况随着高性统才真正成为高教通信子系物理线路很长能通信网络和通信软件的出现以及它们在集群中的运用，集群系种较为理想的并行处理平台并得到了较大的发展。集群系统的统是十分重要的，因为集群系统有更高的结点复杂性，结点之问，导致互连网络延迟很长。同时，也带来了线路的可靠性、安全性等问题。它们都需要由通信协议及其实现的通信软件和网络服务来解决。分布式应用程序所需的通信是多样化的，从点到点通信到多播通信，且能支持成批数据传输、流数据、组数据等等。传统的集群通信是建立在普通低速的局域互连网和t c p i p 协议的基础上。其通信性能低下，只适用于运行串行程序和通信量不大的粗粒度并行程序。但是在现代集群计算机中，它的通信软件使用专用网络的集群计算机通信协议，提供了快速而可靠的结点间以及与外界数据通信的手段。它往往使用通过绕开提供了快速而可靠的结点问以及与外界数据通信的手段。它往往使用通过绕开9l ：海人学颅卜学位论文操作系统的轻量级通信协议，来消除操作系统对系统性能影响很大的额外通信开销。集群计算机的通信服务调用提供了集群计算机传输和管理用户数据所需的基本机制，并且保证如延迟、带宽、可靠性、容错等服务质量，提供对用户接口的直接用户层访问。如通常集群计算机采用相对低层的应用程序接口a p i( a p p l i c a t i o n p r o g r a m i n t e r f a c e ) 来支持更大范围的高层通信函数库和协议。其中经典的通信系统有v m m c 、u n e t 、a c t i v em e s s a g e s 、f a s ts o c k e t s 、s p 2m p l以及最近的g m 、b i p 、p m 等。最初设计的通信系统相互之间差异较大，各个系统为了提高性能，在软、硬件方面都进行了改进。例如：美国p r i n c e t o n 大学计算机系的k a il i 教授等设计的s h r i m p 系统为了消除传统通信机制和网络接口对通信性能的制约，使用了v m m c z 通信机制，并为支持该通信机制的实现研制了专用的网络接口。同时，它的实现对操作系统有较大的依赖。这一时期的研究主要集中于对协议结构的设计上。随着对集群通信系统研究的深入，各个通信系统的协议都集中于基于消息传递的模式之上。其中较有代表性的是美国c o m e l l 大学计算机科学系的e i c k e n 等人在1 9 9 5 年设计的u n e t ”的通信系统。u n e t 的主要设计目标就是在不削弱保护机制的前提下，通过允许多个用户进程对网络接口硬件的直接访问，取得较小的通信延时和较大的通信带宽，并增加在其上实现高层通信协议的灵活性。之后的g m 、b c l 等系统，都在一定程度上采用了这种模式。美国c a l i f o r n i a 大学b e r k e l e y 分校的e i c k e n 等人在1 9 9 2 年提出的a c t i v e m e s s a g e s l 4 1 也是一种有代表性的系统。它可以看成是一种轻量的远程过程调用( r p c ) ，其基本设计思想就是让消息的发送方预先指定好接收方用于处理该消息的函数( h a n d l e r ) ，消息到达接收方时，这个预先指定的消息处理函数被调上海大学颧+ 学位论文用以处理到达的消息。与传统的s e n d r e c e i v 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 在消息接收方无须缓存。传统的消息传递软件中通信启动开销通常很大，为了降低通信的平均升销，往往采用大消息包，以便启动一次通信能传送尽可能多的数据。但对于a c t i v em e s s a g e 来说，通信的启动软件开销要小得多，通常可以采用比较小的消息包。因此对于消息发送方，通信硬件提供的缓存对a c t i v e m e s s a g e 的小消息包来说就己经足够了，无须再由软件来提供缓存。a c t i v e m e s s a g e 非常自然地避免了传统通信机制存在的由于复杂的缓冲区管理、慢速的内存数据拷贝和流量控制造成的大量软件开销，并且也没有程序运行时消息发送操作和接收操作时间上的不匹配问题。目前在集群通信协议的研究方面出现了许多基于m y r i n e t 网络设备硬件的系统，其中较有代表性的有m y r i c o m 公司自己推出的g m 协议、法国的l h p c 实验室研究的b l i p 协议和中科院研制的b c l 1 8 1 协议。g m 5 1 是一个商品化的通信协议，它与u n e t 类似，采用基于端口( p o r t ) 的消息传递方式。它提供了阻塞式和非阻塞式两类消息传递机制，并为上层实现t c p i p 协议提供了特殊支持。b i p 6 】是一种精简的低层次通信协议，其目标是提供一个高效的硬件访问方式和零存储拷贝通信。由于b i p 只支持很简单的通信功能，因此它不能直接提供给最终用户程序员使用，b i p 仅为高层的通信软件( 如m p i 等) 提供一个具有较好功能性能比的开发环境。b i p 的a p i 是一个经典的消息传递界面。它同时提供阻塞式和非阻塞式通信接口：其通信的可靠性由网络硬件保证：提供有海大学砸l 学位论文序的消息传递；提供错误检测功能，但不提供错误恢复功能。v i a l 7 ( v i r t u a li n t e r f a c ea r c h i t e c t u r e ) 是i n t e l 、c o m p a q 和m i c r o s o f t 三家公司共同推出的一个用户级通信界面，它力图为集群上的用户进程提供一个高性能的、从内存到内存的网络传输标准，目前已经得到超过一百三十家业界领先公司的支持。v i a 大量借鉴了a i v l 、u n e t 、f m 和v m m c 等用户级通信技术的思想，并在设计中使之更加完善。当集群系统逐渐发展到以s m p 结点作为主要计算设备时，仅考虑机问通信的通信协议己不再适应当前的系统配置。为此，a c t i v em e s s a g e s 、b i p 和b c l相继展开了相关的研究。a c t i v em e s s a g e s 推出a v l i i 8 1 ，b p 推出b i p s m p 9 ，b c l 推出b c l 一3 。上海大学计算机学院在上海市科委、教委的支持下，也对集群高效通信子系统展开了研究。由上海大学计算机学院主持进进行的项目并行通信机制p g m 的研究与实现早在2 0 0 2 年就通过了上海市科委组织的专家鉴定。本文在该项目研究成果的基础上，结合s m p 结点的特性，对多重通信协议进行了研究和实现。1 5 小结综上所述，基于单c p u 结点的集群通信协议已发展得较为成熟，目前常见的几种协议结构都较为类似。v i a 的提出又更进步统一了这类集群通信协议的结构。随着s m p 结点的出现，基于s m p 结点的集群通信协议成为高效通信系统研究的一个热点。研究机内与机间通信问题，提高通信的速度和效率，对于提高整个系统的性能具有非常重要的意义。本文主要从提高集群计算机通信效率的角度出发，基于s m p 结点集群的物理特性结构，对于集群计算机及多重通信协议进行了研究探索，并在此的理论基础上进行了协议的设计、实现、形式化描述与验证、以及相应的点对点通信延迟性能测试。第二章基于s m p 结点的多重通信协议2 1 集群系统通信结构2 1 1 集群系统通信结构概述传统的集群结构如图2 1 所示。每个结点有一个处理器，结点间通过高速互联网络连接起来。由于结点上只有一个处理器，一般情况下所运行的应用程序在每个结点上也只加载一个进程。这样，集群通信系统主要需考虑结点间的通信。集群各结点间通过高速互联网络连接在一起，结点间的通信开销相同( 有的互联网络问的通信开销不尽相同，但在同一数量级上) 。这样，应用程序的各个进程之问从软件的角度上可以看作是对称的。进程在进行通信时，无需考虑进程所处的结点。上海大学硕上学位论文翔速j i i ：连删帑当使用s m p 结点组成集群时( 如图2 - 2 所示) ，高速互联网络可以看作一个对称的结构，即结点间的通信开销对称。由于每一个s m p 结点中包含了多个处理器，应用程序可以在每个结点上加载多个进程，这样，应用程序中各个进程之问不再对称，即每个进程在与其它进程进行通信时需要考虑所处的物理位置。不同结点间通信需要通过互联网络，同一结点内部不同处理器间的通信可以直接通过共享内存进行。这样，结点内部的通信开销比结点间的通信开销小。在早期的通信协议中，虽然支持同一结点内多进程的通信模式，但列于结点内通信与结点间通信没有进行区分。所有进程间的通信，不区分其拓扑结构统一通过互联网络进行。这样没计的优点在于保证了整个协议接v i 的一致性，为集群系统提供了一致的通信界面。但是，采用这种方式无疑降低了系统的效率无法充分利用系统所提供的性能。图2 - 3 多重通信协议结构为了能够充分利用系统的硬件性能，我们可以根据处理器间的互连性能将集群系统看作一个层次结构。同s m p 结点内部看作一个高速互连的结构；不同结点间看作是一个相对低速的互连结构。在设计集群通信协议时采用多重通信协议( m u l t i p r o t o c o l l a y e r ) 结构。如图2 3 中所示，同一结点内的进程间传递消息通过基于共享内存的通信协议，不同结点间的进程间传递消息通过基于互连网络的用户层通信协议。通过采用这样一个二层结构，可以有效地描述基于s m p 结点的集群通信系统的结构。多重通信协议的不同协议层采用相同的应用程序接口，对上层软件提供统一的界面。程序员将通信协议层看作一个黑盒子，开发应用程序时无须考虑通信进程间相对的位置关系。在进行通信时，通信协议层自动地将不同相对位置间所需传递的消息分发给不同的协议完成。这样，集群物理上的拓扑结构对应用程序员透明。j ”坶大学蛳1 学位论文2 2 多重通信协议模型在基于s m p 的集群系统中，针对机内通信与机间通信的不同，需要采用多重通信协议。多重网络协议上层接口基丁= 共享内存用户层通信的通信协议协议图2 - 4 多重通信协议结构图2 4 给出了多重通信协议的结构。图中左半部分表示通过基于共享内存的通信协议层进行同一s m p 结点内部不同进程间的消息传递，右半部分表示通过用户级通信协议层使用高速互连网络进行结点间的消息传递。通信协议消息传递过程分为三个阶段：消息的发送、消息在网络上的传输和消息的接收。其中，消息发送是指消息由用户空间( u s e rs p a c e ) 传入网络接1 5 上的输出消息队；o ( o f i v o ) 的过程。消息在网络上的传输是指消息由网络接口上的输出消息队列( o f i f o ) k 由网络传至接收结点网络接口上的输入消息队列( 皿i f o ) 的过程。消息的接收指接收方将消息由网络接口上的输入消息队列( 正o ) 传入用户空间( u s e r s p a c e ) ( 过程。多重通信协议在s m p 结点间的通信( 远程消息) 由消息的发送方将消息发送请求写入网络接口卡( n e t w o r ki n t e r f a c ec a r d ，n i c ) ，由n i c发送消息。在s m p 结点内部的通信( 本地消息) 实现中扩展了原有的协议，采用了基于共享内存的通信方式。本地消息不再通过n i c 传递，而直接由消息的发送方将消息写入共享内存中，然后由消息的接收方读出。在消息的接收方，采用相同的应用程序接口来接收消息。接收消息时将查询从网络和共享内存中传递的消息。多重通信协议中通信的基本单位是端1 5 ( p o r t ) 。每个参与通信的进程首先需上海大学烦士学位论文要注册个通信端口，端口号与进程所在结点( n o d e ) 号在通信过程中唯一标识该进程。所有的消息通信都需要消息的发起方( 消息发送进程) 指出消息的接收方的结点号与端口号。多重通信协议研究的关键在于如何设计实现高效的多重通信协议的各协议层，以及多重通信协议中不同协议间相互组合的问题。本文中的多重通信协议山基于共享内存的s m p 结点内通信协议和用户级结点间通信协议组成。基于共享内存的通信协议是针对s m p 结点而设计的结点内通信协议。在设计中需要考虑如何提高通信性能，如何处理多进程同时访问临界资源，如何降低数掘拷贝造成的影响等问题。用户级通信协议基于u n e t ”1 ( 由c o r c e l l 大学为并行计算专门没讨 的部分设计思想。在设计中需要考虑数据包格式、通信函数库、网络驱动程序等关键问题。2 3 共享内存协议模型采用共享内存协议实现s m p 结点内部通信时，可以采用不同的通信机制。第一种是采用进程间共享内存的方法，如图2 - 5 所示。消息发送方( 进程a ) 将待发送的消息送到共享内存中，并通过同步机制通知接收方( 进程b )接收消息。进程b 发现消息到达以后从共享内存中取出相应的消息。1i1进程a操作系统内核进程b圈2 - 6 批享内存模掣2第二种方法如图2 - 6 所示，是采用直接在不同进程的发送和接收缓冲区间进行共享拷贝，这样，进程间的通信只需要消息发送方( 进程a ) 将消息数据送入消息接收方( 进程b ) 的进程空间，无需进程b 做任何操作。同时，采用这种方法还可以减少一次数据的拷贝。但是，这种方法有一个极大的缺点就是它具有较低的安全性与可靠性。第三种方法采用实时系统共享内存1 9 1 的方法。修改操作系统初始化代码，从系统内存中预留出一部分内存空间，留作进程问共享通信用。这种方法与前两种方法相比较，前两种方法的共享内存区域是动态申请的，这种方法却是静态的，共享内存区域的大小不可变，并发访问时通信效率会受到影响。通过对这三种方法进行分析比较我们知道，方法二是采用直接在不同进程的发送和接收缓冲区间进行共享拷贝，这样，进程间的通信只需要消息发送方将消息数据送入消息接收方的进程空间，无需接收方做任何操作。同时，采用这种方法还可以减少一次数据的拷贝。但是，这种方法有一个极大的缺点就是它具有较低的安全性与可靠性。我们可以通过采用自旋锁或者较好的算法( 比如l o c k f r e e 算法) 控制临界区操作的方法来改进。在此，我们采用方法二来设计共享内存通信协议。i 一海人学硕i j 学位论文2 4 用户层通信协议模型传统的通信协议，如t c p i p ，采用核心级协议通信。核心级协议通信( 如图2 7 所示) 需要通信双方在通信过程中进入操作系统核心空间。其通信协议主要在核心中实现，对网络接口卡( n i c ) 的访问只能在核心中进行，n i c 与主机问l i 的传递主要通过中断来实现。核心级通信结构在通信关键路径上引入了掰次进出核心和中断处理的丌销，对通信延迟有较大的影响。图2 - 1 专统的通信协议模型用户空间o sl 硬件层- 用户空间讳硬件层图2 - 8j _ j 户层通信协议模型用户空间o s硬件层v用户级通信( 如图2 - 8 所示) ，通信双方无需进入系统核心空间。他们在用户层空间中直接访问n i c ，通信的触发多采用查询方式而非采用中断方式。这样，用户层通信消除了通信关键路径上的大量开销，降低了通信延迟。由于能提高通信性能，因此近年来在集群系统中主要采用用户级通信实现高效的机间通信协议。e 海大学硕士学位论文第三章多重通信协议的设计与实现多重通信协议由基于共享内存的s m p 结点内通信协议和基于互连网络的用户级通信协议组成。两种协议支持了不同互连结构的通信硬件。为了能够对上层提供一致的接口，这两种协议采用了类似的通信机制和相同的应用程序接口n3 1 多重协议设计在多重通信协议中，进行通信的基本单元是端口( p o r t ) ，每一个进程可以创建一个端口同其他进程进行通信。进程由所在结点号( n o d e ) 和通信端口唯一标识。每一个端口有一个消息发送请求队# 1 ( s e n d i n gr e q u e s tq u e u e ) 、一个消息接收缓冲 池( r e c e i v i n gb u f f e rp 0 0 1 ) 和相应的完成事件队列、消息发送完成队歹o ( s e n d i n ge v e n tc o m p l e t eq u e u e ) # 1 f 自息到达事件i j ) k y l j ( a r r i v e de v e n tq u e u e ) 。消息接收缓冲池由一组消息通道组成。当一个进程发送一个消息给另外一个进程时，消息发送进程首先需要建立一个消息发送请求。消息发送请求中包含了待发送消息的数据或其缓冲区地址以及消息接收进程的标识( 结点号与端口号偶对) 。然后，消息发送进程将该消息发送请求插入消息发送请求队列中。在实施正式的消息传递前，消息接收进程需要准备好其相应的接收缓冲区( 接收通道) 。当消息接收完成后，系统将会产生一个消息接收完成事件，并插入消息完成事件队列，以通知消息接收进程。同样，在消息发送方当消息发送完成后，系统也将产生一个消息发送完成事件通知相应的进程。消息的传递是按照r e n d e z v o u s 3 】语义进行。这个消息接收缓冲区需要在每次使用该通道进行消息