（通信与信息系统专业论文）机群通信系统互连接入技术研究.pdf

机群通信系统互连接入技术研究 摘要 在超级计算机体系结构研究中，机群系统已成为一种主流结构，而基于 对称多处理器( s m p ) 结点的机群系统以其良好的可扩展性、可用性、可靠 性和较高的性能价格比占据着高性能计算机的主导地位。随着机群系统结点 性能的不断提高，要求其互连网络的接入性能也必须相应提高，否则会成为 制约整个系统性能的瓶颈。机群通信系统互连接入技术的研究是高性能计算 机体系结构研究的重要课题。 本文首先全面分析了机群体系结构和机群互连网络的发展现状，并介绍 了一些相关的研究。然后，从机群通信系统构成角度将结点的互连接入技术 定义为一种层次化结构，并基于这种层次化结构首先提出了网络接口卡 ( n i c ) 的网络接口( n i ) 部件基于内存总线的设计方案。该方案不但能有 效地提高n i c 对n i 的访存性能，而且更为重要的是它开创了内存总线的一 种全新的应用模式，即将内存总线扩展为面向系统外部设备互连的局部总线， 其显著作用是为计算机系统，无论是通用系统还是嵌入式系统，增加了一个 高效的i 0 总线。同时，本文还对内存总线的这种应用模式的实现进行研究， 给出了内存目标接口( m t i ) 的详细设计，在功能和逻辑上实现了内存总线 和局部总线间的桥接，为基于内存总线的应用设计提供了功能完备的接口部 件。 随后，本文重点讨论了基于通用嵌入式系统的机群互连网络n 1 c 设计。 作为结点的互连网络接入设备，n 1 c 的功能和性能对结点的互连网络接入性 能有着至关重要的影响。鉴于嵌入式技术的发展，本文给出了基于i n t e l i o p 3 1 0i o 处理器的曙光4 0 0 0 a 超级服务器d c n e t 机群互连网络n i c ( 简 称d c n e t - n i c ) 的设计与实现。采用m t i 技术实现了d c n e t - n i c 基于内存 总线的网络接口( m i n i ) 设计，取得了基于通用嵌入式系统n i c 体系结构研 究的重要成果。本文还对d c n e t n 1 c 进彳于了全面的测试与评价。测试结果说 明d c n e t n i c 不但实现了与m y r i n e t 、s c i 和q s n e t 等国外同类n i c 相近的 性能，而且证明基于通用嵌入式系统和m t i 技术实现高性能n i c 是有效可 哈尔滨工程大学博士学位论文 行的。 最后，将研究内容深入到机群结点芯片组的主p c i 桥设计。主p c i 桥 作为结点芯片组内部总线与p c i 总线的桥接部件，在机群通信系统层次化结 构中不但实现着不同总线间的协议转换，而且匹配着结点与n i c 的i o 性能。 文中介绍了基于龙芯的s m p 芯片组体系结构，分析了芯片组中p c i 总线接 口模块的相关概念和技术，重点讨论了基于龙芯的s m p 芯片组主p c ! 桥的 设计与验证。 作为研究工作的部分，文中给出了机群通信系统的层次化结构中某些 关键技术的设计实例，并对其进行了客观的性能评测。 关键词：机群互连网络：网络接口卡( n i c ) ；芯片组；主p c i 桥 机群通信系统互连接入技术研究 a b s t r a c t c l u s t e ri saw i d e l yu s e da r c h i t e c t u r ei ns u p e r c o m p u t e r t h es m pc l u s t e rp l a y s ad o m i n a n tr o l ei nt h eh i 曲p e r f o r m a n c ec o m p u t e rf i e l df o ri t sf a v o r a b l e s c a l a b i l i t y , u s a b i l i t y , r e l i a b i l i v ya n dh i g hp e r f o r m a n c e c o s tr a t i o t h ep e r f o r m a n c e o fn o d e si nt h ec l u s t e rs y s t e mi s i n c r e a s i n gc o n t i n u o u s l y , w h i c h c a l l sf o r c o r r e s p o n d i n gi m p r o v e m e n to nt h ep e r f o r m a n c eo ft h ei n t e r c o n n e c ta c c e s so f n o d e s ，o re l s ei tw i l lb et h eb o t t l e n e c ko fc l u s t e rp e r f o r m a n c e t h es t u d yo nt h e i n t e r c o n n e c ta c c e s st e c h n o l o g yo fc l u s t e rc o m m u n i c a t i o ns y s t e mi sam a j o ri s s u e o f t h e1 1 i g hp e r f o r m a n c ec o m p u t e rs y s t e ma r c h i t e c t u r e a f t e ra n a l y z i n gc l u s t e ra r c h i t e c t l l r ea n di n t e r c o n n e c t s ，a ni n t e r c o n n e c ta c c e s s s y s t e mh i e r a r c h ys t r u c t u r eo fc l u s t e rc o m m u n i c a t i o ns y s t e mi si n t r o d u c e di nt h i s p a p e r b a s e do nt h es t r u c t u r e ，an e t w o r ki n t e r f a c e 吖i ) b a s e do nt h em e m o r yb u s i sd e s i g n e df o rt h en e t w o r ki n t e r f a c ec a r d i c ) t h ed e s i g nn o to n l yi m p r o v e s t h ea c c e s sp e r f o r m a n c eb e t w e e nt h en i ca n dt h en i ，b u ta l s o ，w h a ti sm o r e ，s e t sa n e wa p p l i c a t i o nm o d eo nt h em e m o r yb u sw h i c hc o n v e r t st h em e m o wb u st oa l o c a lb u sf o rs y s t e mp e r i p h e r a li n t e r c o n n e c t i o n t h eg r e a te f f e c to ft h i sm o d ei s a d d i n gah i g he f f i c i e n ti o b u st o c o m p m e rs y s t e m w h a t e v e r u n i v e r s a lo r e m b e d d e ds y s t e m f u r t h e r m o r e ，t h er e s e a r c hi n c l u d e st h ei m p l e m e n t a t i o no ft h e m o d ea n dg i v e st h ed e t a i ld e s i g no ft h em e m o r yt a r g e ti n t e r f a c e ( m t i ) ，w h i c hi s u s e di nc o n v e r t i n gt h em e m o r yb u st oal o c a lb u s ，f u r t h e r m o r e ，p r o v i d e sf u l l i n t e r f a c ef u n c t i o n sf o ra l lt h ed e s i g no f d e v i c e sb a s e do nt h em e m o i yb u s t h e n ，t h i sp a p e rm a i n l yc o n c e n t r a t e so nd e s i g n i n gan e wn o d e sc l u s t e r i n t e r c o n n e c tn i cb a s e do nt h eu n i v e r s a le m b e d d e ds y s t e m a st h ed e v i c ef o r n o d e st oa c c e s si n t e r c o n n e c t s ，t h ee f f i c i e n c ya n df u n c t i o no f n i ci sc r i t i c a lt ot h e a c c e s sp e r f o r m a n c eo fn o d e s i nv i e wo ft h ed e v e l o p m e n to fe m b e d d e d 哈尔滨工程大学博士学位论文 t e c h n o l o g y , an i cb a s e do nt h ei n t e li o p 3 10i 0p r o c e s s o rc h i p s e ti sd e s i g n e d a n di m p l e m e n t e df o rd c n e t , w h i c hi sa b b r e v i a t e dt od c n e t - n i c d c n e ti st h e i n t e r c o n n e c t i o no fd a w n i n g4 0 0 0 ac l u s t e r am e m o r yi n t e g r a t e dn e t w o r k i n t e r f a c e ( m i n i ) a d o p t i n gm t it e c h n i q u e i se m b e d d e di nt h ed c n e t o n i c a r c h i t e c t u r e ，w h i c h i sa s i g n i f i c a n ta c h i e v e m e n t o nt h en i ca r c h i t e c t u r e f u r t h e r m o r e ，t h ea l l a r o u n dt e s ta n de v a l u a t i o no fd c n e t - n i ci sp e r f o r m e d t h e t e s t i n gr e s u l t ss h o wt h a tt h ed c n e t n i co b t a i n sc o m p e t i t i v ec o m m u n i c a t i o n p e r f o m l a n c ec o m p a r e d 、v i t ht h en i co fm y r i n e t ，s c i ，a n dq s n e t ，a n dp r o v et h a t t h ew a yt od e s i g nh i g hp e r f o r m a n c en i cb a s e do ne m b e d d e ds y s t e ma n dt h em t i t e c h n o l o g yi sf e a s i b l ea n de f f e c t i v e f i n a l l y , t h er e s e a r c hi se x t e n d e dt ot h ed e s i g no fah o s t p c ib r i d g e ，w h i c hi s ab r i d g ec o n n e c t i n gt h ei n t e r n a lb u sa n dp c ib u sf o rt h en o d e sc h i p s e t t h e h o s t p c ib r i d g en o to n l yp e r f o r m sb u sp r o t o c o lc o n v e r s i o nb e t w e e nt h ed i f f e r e n t t y p e so fb u s e s ，b u ta l s om a t c h e st h ei op e r f o r m a n c eb e t w e e nt h en o d ea n dt h e n i ci nc l u s t e rc o m m u n i c a t i o ns y s t e m t h ea r c h i t e c t u r eo fs m pc h i p s e tb a s e do n g o d s o nc p ui sd i s c u s s e d , a n dt h er e l m e dt h e o r i e sa n dt e c h n i q u e so fp c ib u s i n t e r f a c ea r ea n a l y z e d t h ed e s i g na n dv e r i f i c a t i o no ft h eh o s t p c ib r i d g ei nt h e c h i p s e ti sp r e s e n t e di nt h i sp a p e r a sa ni m p o r t a n tp a r to fo u rr e s e a r c hw o r k ，t h es p e c i f i cd e s i g ni n s t a n c e so f s o m ek e yt e c h n o l o g i e si nt h ea b o v em e n t i o n e di n t e r c o n n e c ta c c e s s s y s t e m h i e r a r c h ys t r u c t u r eo fc l u s t e rc o m m u n i c a t i o ns y s t e ma r ed e t a i l e d ，a n dt h ep r e c i s e t e s t sa n do b j e c t i v er e m a r k st ot h ed e s i g na r em a d ei nt h i sp a p e r k e y w o r d s ：c l u s t e ri n t e r c o n n e c t s ，n e t w o r ki n t e r f a c ec a r d ( n i c ) ，c h i p s e t ，h o s t p c i b r i d g e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ： 日期：g 年s - 月2t ，日 第1 章绪论 1 1机群系统 第1 章绪论 1 1 1 机群系统的定义与特征 机群系统是利用高性能通信网络将一组计算机( 结点) ，按某种结构连接 起来，并在并行程序设计及可视化人机交互集成开发环境支持下，统一调度， 协调处理，实现高效并行处理的系统。一般地，每个结点是一台高性能工作 站或高档p c 服务器。除了满足由交互用户单独地使用每个结点的任务外， 所有的机群结点必须能一起工作，如同一个单一集成的计算资源。机群中每 一个结点是一台完整的计算机，它有自己的处理器、高速缓存、磁盘以及i o 适配器并具有一个完整、标准的操作系统。机群系统采用单一映像( s s i ) 技术实现单一集成计算资源的概念，使得机群系统更易于使用和管理。结点 间的连接可采用商品化的网络( 如以太网等) 或其它高速网络( 如m y r i n e t 氅、 1 1 目o 当前，s m p 结点逐渐成为组成机群系统的主流设备。无论是高端的服务 器中，还是在低端的p c 机群上，采用s m p 结点能够提供更高的性能价格比。 越来越多的研究都集中在基于s m p 的机群系统【2 j 。 机群系统一般具有以下几个特征 3 1 - 7 ： 构成系统的每一个结点都是完整的计算机系统。结点可以是s m p 服 务器、工作站、也可以是p c 机，每个结点上都安装有一份完整的操作系统。 连接各结点的互联网络提供结点间高性能、高可靠性和可扩展的通 信服务，人们将这种网络称为系统域网络( s a n ) 。这种网络通常作为结点计 算机的i o 设备，通过网络接口卡( n i c ) 连接到结点的i o 总线上。 整个系统呈现给用户的是单一系统映像。系统中所有分布的资源被 组织成一个统一的整体由用户管理和使用，用户感受不到单个结点计算机的 存在。从用户的角度看，一个机群系统就如同一个具有巨大配置的单一计算 哈尔滨工程大学博士学位论文 机系统。单一系统映像由几方面的内容构成，主要包括单一登陆点( s e p ) 、 单一系统控制点( s c p ) 、单一文件系统( s f s ) 、单一内存空间( s m s ) 和单 一作业管理( s j m ) ，此外还有单一用户界面( s u l ) 、单一进程空间( s p s ) 等。单一系统映像是机群系统中的关键技术之一。 整个系统具有可扩展性( s c a l a b i l i t y ) 。机群系统的可扩展性是指通 过方便地增加或升级一个系统的现有资源，使其满足人们对性能和功能的更 高要求，包括资源可扩展、性能可扩展、软件可扩展等诸多方面。 整个系统具有高可用性( a v a i l a b i l i t y ) 。由于机群系统中的每一个结 点都是一个完整的计算机系统，都有一份完整的操作系统，因此一个或几个 结点的故障不会影响到整个系统的讵常运行，整个系统可以降级使用直至故 障结点得到修复。 1 1 2 机群系统的体系结构 机群系统的典型体系结构如图1 1 所示【8 9 1 。机群系统的编程环境和应用 包括如下一些软件： 匹巫至星置基固 图1 1 机群系统体系结构 f i g ，1 1 c l u s t e rs y s t e ma r c h i t e c t u r e 编程环境。包括编程使用环境和一些工具软件。编程使用环境包括 系统的管理软件、p v m 和m p i 上层通信库、编译器和基本库，以及数据库、 2 第1 苹绪论 w e b 服务器等通用软件；工具软件用于支持不同种类的应用，如服务器聚集 包、并行调试器、优化数学库等。 应用。包括应用基础和应用程序。应用基础是针对不同应用程序开 发的基础支撑包，如并行算法与数学库、深度偏移软件包、数据库中间件等； 应用程序包括科学计算、网络服务、数据库和事务处理等多种应用。 可用性和单一系统映像基础设施是把机群系统中所有结点的映像转化为 单一系统映像的一层软件。单一系统映像通常对系统支持的应用程序和各种 子系统中最紧迫需要的方面进行单一映像化，它让用户在整个机群系统中使 用这些应用程序和子系统时，感觉与使用一台工作站一样方便。 机群系统中结点操作系统一般采用易于扩展的操作系统，例如u n i x 、 w i n d o w sn t 和l i n u x 等。在机群系统中，除了结点本身的操作系统以外， 还必须对操作系统进行一些扩展，以便支持高速通信和单一系统映像等功能。 商品化或专用的互联网为机群中的结点提供连接和通信服务。 1 2 机群互连网络 1 2 1 机群互连网络的结构 图1 2 机群互连网络 f i g 1 2 c l u s t e ri n t e r c o n n e c t s 机群互连网络是连接一个机群系统内部所有结点并提供高性能、高可靠 通信服务的网络硬件及底层通信协议的总和。一般来说，机群互连网络只是 3 哈尔滨工程大学博十学位论文 用于系统内部互连，如图1 2 所示，无需考虑对异种结点间通信的支持。连 网后的计算机不仅可以访问本地资源，而且可以访问与之相连的其它计算机 的资源，达到资源共享的目的【1 0 川】。 机群互连网络的设计和实现技术是高性能计算机系统的关键技术之一， 与局域网( l a n ) 和广域网( w a n ) 相比，机群互连网络更强调整个网络的 延迟、带宽和吞吐率等技术指标。为降低硬件延迟，机群互连网络广泛采用 切入交换机制而不是存储转发机制，这样可以使数据包传送过程中的交换延 迟与数据包的大小无关。为降低软件延迟，机群互连网络广泛采用用户级通 信技术，简化通信的协议层次、旁路操作系统。为提高传输带宽，机群互连 网络多采用全双工通信链路、加宽每个链路上的数据宽度、并提高时钟信号 的频率。为提高吞吐率，机群互连网络的拓扑采用多级互连网络，如胖树( f a t t r e e ) 、c l o s 等网络，这些网络可以提供较高的对分带宽，网络内部是无阻塞 的。为扩展数据的传输距离进而增加网络规模，在机群互连网络中多采用屏 蔽双绞线和低电压差分信号( l v d s ) 或光纤传输介质来实现高速数据传输。 现有的以机群体系结构为特征的并行计算机系统，大多采用t o 总线( 如 p c i 总线) 实现结点与机群互连网络的连接。 1 2 2 机群互连网络的关键技术 机群互连网络的特征可以用五个要素来描述：网络拓扑结构( t o p o l o g y ) 、 交换方式( s w i t c h i n g ) 、流量控制机制( f l o wc o n t r 0 1 ) 、路由算法( r o u t i n g a l g o r i t h m ) 和交换芯片结构。这些技术的出发点是使机群互连网络具有更高 的传输带宽、更小的通信延迟和良好的扩展能力，为通信软件提供更好的支 持。这些技术是设计机群高效通信系统的基础，也是构造高性能机群系统的 f j 提【1 2 1 f 1 4 j 。 f 一) 网络拓扑结构 互连网络的拓扑结构可以分为静态结构和动态结构。静态( 或直接) 网 络由点到点直接相连构成，连接方式在程序执行过程中不会改变。动态( 或 间接) 网络是用开关通道实现的，可以动态地改变结构，使之与用户程序中 4 第1 章绪论 的通信要求匹配。 静态网络使用直接链路，它一旦构成后就固定不变。这种网络比较适合 于构造通信模式可预测或可用静态连接实现的计算机，常用来实现集中式系 统的子系统之间或分布式系统的多个计算机结点之间的固定连接。 为了达到通用的目的，需要采用动态互连网络，它能根据程序要求实现 所有的通信模式。按照价格和性能增加的顺序，动态互连网络的排队次序为 总线系统、多级互连网络和交叉开关网络【1 5 】。 最简单的动态拓扑结构是总线结构。总线技术一般用共享媒体实现，特 点是：网络上各结点共享信道，一个结点发出数据，其它结点都能收到。共 享媒体的缺点是随着结点的增加，每个结点能占用的平均带宽减小：由于争 用总线，容易造成某些结点无法获得总线的使用权，从而产生故障。在带宽 要求较高的场合，都用交换媒体代替共享媒体，从而增加结点时平均占用的 带宽不会下降。 交叉开关网络的带宽和寻径性能最好，但是由于交叉开关的硬件复杂度 以输入( 或输出) 端口数目的平方上升，所以造价昂贵。如果网络的规模较 小，那么交叉开关是一种理想的选择。 机群互连网络的拓扑结构直接决定着互连网络的可扩展性，在机群互连 网络中，有很多种拓扑结构可供选择，但常用的有环形( r i n g ) 、网格( m e s h ) 、 规则多级互连网络和非规则多级互连网络几种。多级互连网络相对予m e s h 网络具有更好的可扩展性，因此成为机群互连网络的首选拓扑结构，如 m y r i n e t 网络。 由于采用源址路由方式，m y r i n e t 交换芯片可以连接成任意拓扑结构，为 提高网络的可扩展性并减少网络内部阻塞，m y r i n e t 在多端口交换机内由多个 交换芯片连接成无阻塞的c l o s 网络，该网络拓扑结构也属于浏接多级互连网 络。m y r i n e t 网络的核心部件是对称的多端口交换芯片，m y r i n e t 2 0 0 0 的交换 芯片具有1 6 个全双工端口。1 2 8 结点交换机在机箱内的连接关系如图1 3 所 示【1 6 】，图中的每一圆圈代表一个1 6 端臼交换芯片。 5 哈尔滨工程大学博十学位论文 s p m o f l kc l l 岫e e k ( b a e k f l a m ) b 1 蕾d e s 图1 3 1 2 8 结点m y r i n e t 网络拓扑结构 f i g 1 31 2 8n o d e s m y r i n e t t o p o l o g y ( 二) 交换方式 互连网络交换方式决定了如何将消息从输入通道取走，然后送到输出通 道。交换方式主要分为以下几类： 电路交换( c i r c u i ts w i t c h i n g ) 电路交换类似于电话网络中的交换机制，它必须先在源结点与目的结点 间建立一条链路，然后才可以进行消息的传递；消息传递完毕之后再撤销链 路。电路交换的主要开销在于通信链路的建立，链路建立以后传输效率很高。 电路交换有三大优点：第一是建立连接后传输延迟小，实时性好，唯一的延 迟是电磁信号的传播时间，非常适合于持续传输大消息；第二是一旦电路建 立，便不会发生阻塞问题，也不需要路由，可靠性高；第三是不要求构成该 通信链路的中间结点拥有缓存空间，从而没有缓存管理开销。电路交换有两 大缺点：第一是建立链路需要较长的延时开销；第二是链路的利用率不高， 不管有没有数据在传送及传送数据多或少，总是不加区别地持续占有整个线 路，直到链路被撤销。在耦合较紧的多计算机系统内，电路交换具有一定的 生命力【1 8 】。 存储转发交换( s t o r e a n d - f o r w a r ds w i t c h i n g ) 存储转发交换方式在传递消息之前，不需要在源结点和目的结点之间建 6 第1 章绪论 立通信链路。源结点直接将整个分组交给第一个中间结点，中间结点将其全 部保存在本地的缓存空间中，当后续结点的链路可用并有可以缓存报文的空 间时传送给下一个中间结点，依次类推，直到消息到达目的结点。存储转发 交换方式的优点是根据需要动态地获得并释放通信链路，具有较高的链路利 用率。存储转发交换方式包含报文( m e s s a g e ) 交换和分组( p a c k e t ) 交换， 这两种交换方式的区别是一个报文包含一个或多个分组，分组交换比报文交 换具有更高的信道利用率和更低的网络传输延迟【l9 】。由于分组交换在i n t e m e t 上广泛使用，因此存储转发交换也常特指分组交换。几个第一代商业多处理 器系统( 如i p s c 1 、n c u b e1 、a m e t e k1 4 和f p st 系列) 曾采用分组交换方 式【”】；同时分组交换对链路的误码率要求不高，因此广泛应用于全球w a n 和l a n 网络( 采用t c p i p 协议) 。 存储转发的缺点是分组交换需要缓存每个进来的分组，对中间结点的分 组缓存空间会有较高的容量要求，同时引入一些管理操作丌销，例如接收分 组需要分配空间，分组转发成功则释放空间；另一个缺点是网络延迟随着路 由路线上经过的中间结点数目( 也称路径长度) 增加而线性增大，因此现在 的多处理器系统很少采用存储转发交换方式。事实上，在存储转发方式中， 中间结点没有必要等到整个分组全部被缓冲后再进行路由选择，只要分组的 目的地址域或者路由信息到达并可用后，就可以进行路由选择，这样便产生 了虚穿透( v i r t u a lc u t t h r o u g h ) 和虫洞( w o r m h o l e ) 交换方式。 虚穿透( v i r t u a lc u t t h r o u g h ) 交换 为了进一步减小数据传输延迟和提高通道利用率，p a r v i zk e r m a n i 和 l e o n a r dk l e i n r o c k 为计算机通信网络提出了虚穿透( v i r t u a lc u t t h r o u g h ) 交 换方式。在这种交换方式下，当分组的头部到达一个结点时，该节点根据头 部的路由信息立即进行路由，当发现输出通道正在被使用时，该结点缓冲后 面接收到的分组内容，这点与分组交换一样；当该分组的输出通道空闲时， 该分组立即从输出通道进行输出，就像从输入通道直接穿透到输出通道，因 此被称为虚穿透交换方式，这点与电路交换相似。相对分组交换，虚穿透交 换有以下优点：网络延迟小，通道利用率高获得的流向( 带宽) 大，缓 冲要求低l l ”。 虫洞( w o r m h o l e ) 交换 7 哈尔滨工程大学博士学位论文 w i i 帅j d a l l y 和c h a r l e sl s e i t z 提出了虫洞( w o r m h o l e ) 2 0 1 1 2 1 】交换方 式。在虫洞交换方式下，分组被进一步划分为更小的传输单位一微片( f l i t ) ， 利用头部微片中包含的路由信息为跟随其后的微片建立通信链路，其余微片 以流水方式跟进，尾部微片负责释放占用的链路，当发现头部阻塞时，分组 的后续部分停止前进，阻塞在原地并占用通道。虚穿透和虫洞交换的区别在 于当路径发生阻塞时，处理方式不同：虚穿透交换方式下，头部微片停止前 进被缓冲在中间结点汇总，而其余微片继续跟进，如果阻塞时间足够长的话， 所有的微片都会与头部微片缓冲在同一结点之中；而在虫洞交换方式下，一 旦头部微片停止前进，则其后所有微片也停止前进，分别缓冲在各自当前的 中间结点中。虫洞交换方式不需要中间结点具备较大缓存空间，但是导致死 锁问题的解决方案相对比较复杂；而虚穿透交换方式对死锁问题的解决方式 比较统一，但需要中间结点具备较大的缓存空间1 1 4 1 1 2 2 i 。虫洞交换的实现方式 有多种【1 2 1 1 2 3 1 1 2 4 1 ，o l a v l y s n e 作了典型的理论模型分析1 2 5 1 。 其它交换方式 此外，还有一些非主流的交换方式，例如类似于电路交换的a t m 信元 交换2 6 1 和介于虚穿透交换和虫洞交换之间的混合交换1 2 7 1 。 a t m 信元交换为：发送者到接收者之间寻找一个路由，并将路由信息存 放在沿途的交换机上；系统利用这个虚拟线路来发送固定大小的信元，一个 已经给定虚拟线路的信元，沿着交换机的路径流动；当不再需要此连接时， 释放此连接，并从交换机中删除路由信息。 介于虚穿透交换和虫洞交换之间的缓和交换为：为了减轻有一定负载时 的缓冲压力，同时避免死锁，避免有较大负载时链路利用率急剧下降，k a n g gs h i n 和s t u a r tw d a n i e l 提出一种混合交换方式，即碰到阻塞时根据经过的 路径长度动态缓冲或停止正在前进的分组，平衡占用的资源。 电路交换、分组交换、虚穿透交换和虫洞交换是主流的交换方式a 分组 交换主要用于w a n 和l a n 等有数据链路层协议的计算机网络，其特点是网 络传输经常出错。电路交换、虚穿透交换和虫洞交换主要用于紧耦合系统的 互连，它们的共同特点是通过中间结点的延迟小。虫洞交换是机群互连网络 的主要交换方式。 8 第1 章绪论 ( 三) 流控机制 当分组( 或数据) 沿着一定路径通过网络时，流控机制负责为分组分配 缓存空间与通道等资源。流控机制与交换方式紧密相关。当一个分组请求另 一个分组已经占用的资源时，这个分组不能继续前进，产生资源冲突。此时 流控机制决定这个分组被丢弃、阻塞在原地、缓存还是从另一通道重新路由。 好的流控机制在减小网络延迟的同时又能避免链路拥挤i 】4 1 。t c p 采用滑动窗 口流控机制，这在l a n 或w a n 中非常有效2 8 1 。 ( 四) 路由算法 路由算法决定从源结点传递消息到目的结点的路径选择方法。路由算法 有多种分类方法，根据路径是否唯一可以分为确定性( d e t e r m i n i s t i c 或 o b l i v i o u s ) 路由和适应性( a d a p t i v e ) 路由两类【1 7 l 。确定性路由只要源结点与 目的结点确定以后，消息传递的路径也就相应确定。适应性路由则能根据网 络的实时状态动态选择路径，具有一定的适应能力。 适应性路由算法又分为回溯型( b a c k t r a c k i n g ) 和前进型( p r o g r e s s i v e ) 。 当路径发生阻塞时，回溯型算法自动后退，搜索其它路径，因此它需要保存 一些搜索的历史信息，以保证不会出现重复搜索，这一方面增大了路由信息 量，另一方面也会增加路由的时间，但是它具有出色的灵活性和容错能力。 而前进型路由算法不保存路由过程的历史信息，只是利用当前有限的信息选 择路由通道，当碰到能使路径缩短的链路阻塞时，前进型路由协议可以等待 链路、丢弃该包或者在该结点选择另一路经进行路由，这类算法较简单，但 可能具有更大的盲目性。 路由算法还可以按照生成路径的最短性细分为最短路径( m i n i m a l ) 和非 最短路径( n o n m i n i m a l ) 路由。前者能确保生成的路径是源结点和目的结点 之间的最短路径之一，而后者可根据网络通信状况选择合适的路径，以绕远 路( m i s r o u t i n g ) 的方式避开网络中通信拥挤的结点或发生故障的结点。 在消息传递过程中，允许在已经占用某些资源的同时申请占用其它资源， 当这些资源占用和申请构成一个环或者形成其它形式的相互等待而永远不能 前进时，互连网络就发生死锁现象。对于非最短路径的路由算法来说，还可 能出现经过无限步都无法到达目的结点的情况，即所谓的活锁( 1 i v e l o c k ) 现 9 哈尔滨工程人学博士学位论文 象。因此，路由算法还必须解决死锁和活锁问题。通常情况下，路由算法用 限制m i s r o u t i n g 步数的方法来解决活锁问题；而解决死锁问题的办法是限制 路径的选择范围，因此就有了部分适应性( p a r t i a l l ya d a p t i v e ) 与完全适应性 ( c o m p l e t e l y a d a p t i v e ) 路由算法。虫洞交换方式的路由最容易出现死锁，路 由算法常采用虚通道( v i r t u a lc h a n n e l ) 方式避免死锁，采用虚通道技术会增 加硬件复杂度并且降低性能，也可采用其它方法避免死锁1 2 9 1 。 在表示方式上，路由算法可以分为源路由和分布式路由。 源路由：源结点在发送分组以前把路径信息放入分组，分组在传输 过程中不需要进行路由查找，可以直接选择输出端口。源路由把路径信息放 入分组，减少了路由查找时间，但增加了分组的长度，同时每个结点需要关 注整个系统的拓扑结构和运行状态( 有无链路和结点出错) 。 分布式路由：每个结点的路由器在接收分组的时候调用路由算法决 定该分组由本地处理器接收还是转发给相邻的其它结点。大部分的多处理器 系统采用分布式路由算法。 ( 五) 交换芯片结构 图1 4i b ms p 2 交换芯片组织结构 f i g 1 4 i b ms p 2s w i t c hc h i po r g a n i z a t i o n 交换芯片是构造机群互连网络的核心部件，交换芯片的结构直接影响着 1 0 第l 章绪论 网络性能。构造m e s h 网络的路由芯片内部采用不完全交叉开关互连各端口， 因为在m e s h 网络中数据传递按固定的方向进行，有些输入与输出端口间是 不可达的。多级互连网络的交换芯片采用对称多端口结构，在交换芯片内部 采用交叉开关实现输入端口与输出端口间的数据通路连接，如图1 4 所示【3 0 】。 1 2 3 机群互连网络的研究现状 机群互连网络一直是机群通信系统互连接入研究的热点问题，受到了学 术界和产业界的关注，并形成了很多国际标准| 3 1 j 。目前，机群系统广泛应 用的专用互连网络有m y r i c o m 公司的m y r i n e t 网路1 3 “、d o l p h o l l 公司的s c i 网络【3 6 】、q u a d r i c s 公司的q s n e t 网络m 以及最新的i n f i n i b a n d 3 8 】网络等。这 些网络从机群系统对互连网络的需求出发，实现了机群互连网络的硬件结构 和低层的数据传递协议，它们的设计思想和实现技术各具特色，均获得了较 好的通信性能。表1 1 是包括百兆、千兆以太网在内的几种机群专用互连网 络的性能说明【3 9 】。从表可见，专用互连网络在带宽、延迟方面极大地优于以 太网，但价格偏高。 表1 1 互连网络说明概要 t a b l e1 1 s u m m a r y o f i n t e r c o n n e c t ss p e c i f i c a t i o n s 且连网络 带宽( m b s )延迟( u s ) 价格端口( e u r o ) 0 s n e t ( q u a d r i c s ) 3 6 0 5 4 7 7 0 m y r i n e tr m y r i c o m ) 2 4 572 0 5 0 s c i ( d o l p h i n ) 2 d5 5 2 0 041 5 9 0 s c l ( d o l p h i n ) 3 d5 5 5 2 0 042 2 2 6 g i g a b i te t h e m e t 1 2 51 0 04 7 7 m e g a b i te t h e m e t 1 21 0 04 8 s c i 网络 s c i 网络 4 0 l 是由高性能总线设计师和系统结构设计师在研究快速总线和 未来总线标准时，通过对总线技术的局限性进行深入研究后提出的一种用于 构造多处理机的互连技术。s c i 将通常的底板总线扩展成全双工、点到点的 哈尔滨工程大学博士学位论文 互连结构，提供分布共享存储器一致的高速缓存映像。s c i 的主要技术特色 是：用点到点链路取代总线作为数据传输通道，使用基于数据包的分离事务 传输协议代替总线中的总线周期，可以获得可扩展的、与总线功能类似的互 联结构：s c i 使用环形或低维直接网络拓扑结构，连接简单，但当网络中的 结点数增加时，由于通信量增加会使数据传输的延迟时间增大。s c i 网络适 合用于构造共享存储形式的多计算机系统。 m y r l n e t 网络 m y r i n e t 网络1 起源于美国的两个研究项目，分别是加州理工大学 ( c a l t e c ) 的m o s a i c ，一种低粒度多计算机实验系统，和南加州大学信息 科学学院( u s c i s i ) 的a t o m i cl a n 。采用m o s a i c 部件建立的网络，这两 个项目的研究人员创立了m y r i c o m 公司，研发m y r i n e t 网络。m y f i n e t 网络的 设计目标是要在局域网环境中获得s a n 的性能，因此m y r i n e t 网络采用m p p 系统中数据包通信和交换技术。m y r i n e t 网络设计对充分考虑并行系统内部互 连网络传输距离近、出错率低的应用环境，可以使用简化的链路控制协议实 现数据传送，从而可以减小数据传输时的协议开销，进而降低传输延迟。采 用无阻塞的c l o s 网络拓扑结构，减少了数据包在网络中的冲突，提高了网络 的吞吐率，进一步降低了延迟时间。源址路由方式和虚穿透交换方法是降低 硬件延迟时间的最有效方法。增强n 1 c 处理器对数据传输的控制能力并简化 软件协议开销成为充分利用网络性能的根本手段。n i c 处理器对网络的自动 映像路由选择功能可以提高网络的可靠性。 q s n e t 网络 q s n e t 网络 4 2 1 起源于m e i k oc s 2 4 3 1m p p 系统的高性能互连网络，q s n e t 网络设计时主要针对并行处理系统内部应用环境，其设计目标是提供并行处 理系统内部各结点间的高效通信，因此网络具有高带宽、低延迟、可扩展的 特性，网络硬件对共享存储通信方式提供了良好的支持。q s n e t 网络通过增 强n i c 的处理能力，有效地支持了全局虚拟存储器共享、减小了通信延迟。 交换芯片通过增加虚通道，可以减小网络内的数据包间冲突，消除队头阻塞 ( h o l ) ，从而提高网络的吞吐率。胖树拓扑结构的多级互连