（计算机系统结构专业论文）多计算机互连网络上聚合通信算法的研究.pdf

摘要 现代科学、生活的发展越来越迫切地需要更强大的计算能力，而研制具有每 秒万亿次、千万亿次处理速度的并行系统需要设计高性能的互连网络来连接大量 的处理器。同时，随着系统规模的不断扩大，处理器之间的通信问题变得越来越 突出。在大规模科学计算和工程应用中，聚合通信的开销往往占到全部通信开销 的绝大部分。因此研究互连网络及相关的聚合通信算法对提高并行计算机的性 能，进而提高并行应用程序的执行效率具有重要的意义。 本文围绕如何提高互连网络上聚合通信操作的通信性能这一问题，开展了以 下研究工作： 本文首先深入研究了单端口环网结构上全交换操作的实现算法。环网结构是 一种具有很好拓扑特性和应用前景的互连网络，是目前很多超级计算机广泛选用 的互连拓扑结构。同时，全交换操作在并行计算领域中有着大量而且重要的应用。 本文基于高维单端口环网结构设计了新型网络划分策略，并运用该策略在高维单 端v i 环网结构上提出了通信量近似最优的间接全交换算法。与现有的其它相关算 法相比，本文提出的高维全交换算法不仅具有很好的可扩展性，而且通信性能有 特别显著的提高。 其次，本文改进了单端1 ：3 二维和三维环网结构上具有最小启动时间的全交换 算法。与原有算法相比，改进后的算法采用“自底向上再回送”的通信模式，在 取得最小启动时间的同时，提高了算法整体的通信性能。 再次，考虑到目前多端口环网结构上全交换操作的研究不足，本文充分利用 了多端口环网的多个通信端口，首次在多端口一维环、二维和四维环网上提出了 通信量完全达到理论下限的间接全交换算法。分析结果表明，当消息较长时，与 已有的相关算法相比，本文提出的多端口环网上的全交换算法具有更优的通信性 能。 然后，基于由多台以太网交换机分层级联而成的机群系统，本文提出通信量 达到理论下限的直接全交换算法d c e 和间接全交换算法m c c e 。全交换算法 m c c e 不仅达到了通信量的理论下限，而且大幅度地减少了消息启动开销和同步 开销，进一步提高了全交换操作的通信性能。实验结果表明，当消息较长时，本 文提出的这两个全交换算法在上述机群系统中明显优于m p i c h 和l a m m p i 中 实现的全交换算法。 接下来，针对传统的基于软件层面的多播技术容易导致路由延迟并加剧内存 读写瓶颈等问题，本文考虑在路由器和交换机的内部交换结构中采用支持并发多 摘要 播等通信方式的多级互连网络，从而在硬件层面上实现并发多播等通信方式。在 深入研究了广义非阻塞型多播网络的低代价构建和多播路由算法的优化等问题 之后，本文提出了一种低代价的广义非阻塞四级c l o s 网络及相关的多播路由算 法。与现有广义非阻塞多播网络相比，本文构造的多播网络具有如下特色：网 络的硬件代价降低到1 2 n 个交叉点以下，仅相当于广义非阻塞置换网络的常数 倍；时间复杂度为o ( n ) 的多播路由算法简单、高效，易于硬件实现；降 低了单个交叉开关模块的引脚( 端口) 数目，更有利于v l s i 芯片的集成。增 加的一级开关模块可以有效地平衡多播负载，增加网络的灵活性。 最后，本文深入研究了能够支持并发多播目标端口重叠的广义非阻塞k - f o l d 多播网络及相关的多播路由算法。该网络可以用较低的硬件代价来有效地减少多 播连接的外部阻塞，从而为多播通信提供更好的q o s 性能。本文通过重新计算 广义非阻塞四级c l o s 多播网络的中间两级开关个数，以提供足够的网络内部路 径来实现k - f o l d 多播路由。基于此思路，本文提出了两个广义非阻塞k - f o l d 多播 路由算法及相应的硬件条件。 需要说明的是，虽然本文整体的研究工作是根据并行分布式多处理机系统的 特点以及特定的应用需求展开的，但是其中提出的广义非阻塞多播网络并不局限 于多处理机系统，也适用于广域网、局域网的路由器和交换机中。 关键词：互连网络；聚合通信；环网；全交换操作；机群；c l o s 网；广义非 阻塞；多播；多级互连网络；并行通信模型 n a b s t r a c t a b s t r a c t t h ed e v e l o p m e n to fm o d e ms c i e n c ea n dl i f eh a sr e s u l t e di ni n c r e a s e dd e m a n df o rp o w e r f u l c o m p u t i n gc a p a c i t y , a n dt h ed e s i g no fp a r a l l e ls y s t e m st h a th a v et h es p e e do ft e r a f l o p sa n de v e n p e t a f l o p sr e q u i r e sh i g hp e r f o r m a n c e i n t e r c o n n e c t i o nn e t w o r k st oi n t e r c o n n e c tn u m e r o u s p r o c e s s o r s m e a n w h i l e ，w i t ht h eg r o w i n go ft h es y s t e ms i z e ，i n t e r p r o c e s s o r c o m m u n i c a t i o n o v e r h e a dm o r ea n dm o r eb e c o m eab o t t l e n e c k i nl a r g e s c a l es c i e n t i f i cc o m p u t i n ga n de n g i n e e r i n g a p p f c a t i o n s ，t h eo v e r h e a do fc o l l e c t i v ec o m m u n i c a t i o nu s u a l l yt a k e s a b s o l u t em a j o r i t yo ft h e e n t i r ec o m m u n i c a t i o no v e r h e a d t h u s ，t h er e s e a r c ho ni n t e r c o n n e c t i o nn e t w o r k sa n dc o l l e c t i v e c o m m u n i c a t i o ni sc r u c i a lt oi n c r e a s et h ep e r f o r m a n c eo fm u l t i c o m p u t e r ss oa st oi m p r o v et h e e x e c u t i o ne f f i c i e n c yo fp a r a l l e la p p f c a t i o n s t h er e s e a r c hw o r k sp r e s e n t e di nt h i sd i s s e r t a t i o na r cm a i n l yc o n c e n t r a t e do ni m p r o v i n gt h e p e r f o r m a n c eo fc o l l e c t i v ec o m m u n i c a t i o no p e r a t i o n so ni n t e r c o n n e c t i o nn e t w o r k s f t r s to fa l l ，t h i sd i s s e r t a t i o ne x t e n s i v e l ys t u d i e dt h ea l g o r i t h m sf o rc o m p l e t ee x c h a n g eo n s i n g l e - p o r tt o m s t o m sh a sb e c o m em o r ea n dm o r ep o p u l a r f o ri n t e r c o n n e c t i n gt h ep r o c e s s o r si n p a r a l l e la n dd i s t r i b u t e ds y s t e m sd u et oi t st o p o l o g i c a lf e a t u r e s ，a n dh a sb e e nw i d e l ya d o p t e db y m a n ys u p e r c o m p u t e r st o d a y m o r e o v e lc o m p l e t ee x c h a n g e ，a l s ok n o w na sa l l t o a l lp e r s o n a l i z e d c o m m u n i c a t i o n ，o c c u r si nn u m e r o u si m p o r t a n ta p p h c a t i o n si np a r a l l e lc o m p u u n ge n v i r o n m e n t t h i sd i s s e r t a t i o np r o p o s e san o v e ln e t w o r kp a r t i t i o n i n gs c h e m eo nm u l t i d i m e n s i o n a ls i n g l e 。p o r t t o m s b ya d o p t i n gt h en e t w o r kp a r t i t i o n i n gs c h e m e ，an e a r - o p t i m a l ( i nt e r m so ft r a n s m i s s i o nt i m e ) i n d i r e c ta l g o r i t h mh a sb e e np r e s e n t e do nm u l t i d i m e n s i o n a ls i n g l e p o r tt o m s c o m p a r e dw i t ho t h e r e x i s t i n ga l g o r i t h m s 。t h ea l g o r i t h mf o rc o m p l e t ee x c h a n g en o to n l yh a sab e u e rs c a l a b i l i t y , b u ta l s o p r o m i n e n t l yi m p r o v e st h ec o m m u n i c a t i o np e r f o r m a n c e s e c o n d l y , t h i sd i s s e r t a t i o ni m p r o v e st h ea l g o r i t h mf o rc o m p l e t ee x c h a n g e ，w h i c hh a sm i n i m u m s t a r t u pc o s to ns i n g l e - p o r t2 da n d3 dt o m s ，b ya d o p t i n g ab o s o m - u p s e n d - b a c ka p p r o a c ht o s c h e d u f n gp a r a l l e lc o m m u n i c a t i o n c o m p a r e dw i t ht h eo r i g i n a la l g o r i t h m ，t h ei m p r o v e da l g o r i t h i nn o to n l ya c h i e v e sm i n i m u ms t a r t u pc o s t ，b u ta l s oh a sb e u e rc o m m u n i c a t i o np e r f o r m a n c e m o r e o v e r , t h e r ea r ef e wr e s e a r c h e st h a th a v eb e e nd o n ef o rc o m p l e t ee x c h a n g eo na l l p o r tt o m s t h i sd i s s e r t a t i o nf i r s t l yp r o p o s e si n d i r e c ta l g o r i t h m sf o rc o m p l e t ee x c h a n g eo na l l p o r ti dr i n g ， 2 da n d4 dt o m s w h i c hc o m p l e t e l ya c h i e v et h et h e o r e t i c a ll o w e rb o u n d so nm e s s a g et r a n s m i s s i o n t h e n e wa l g o r i t h m sf u l l yu t i l i z ea l lp o r t sa n dc o m m u n i c a t i o nf i n k si na l l p o r tt o m s ，a n dt r a n s m i t m e s s a g e sa l o n gs h o r t e s tp a t h s t h ea n a l y t i c a lr e s u l t ss h o wt h a tt h ep r o p o s e da l g o r i t h m so na l l p o r t t o m sh a v et h eb e s tc o m m u n i c a t i o np e r f o r m a n c ea m o n ga l le x i s t i n ga l g o r i t h m s ，w h e nt h em e s s a g e s i z ei se n o u g hl o n g t h ed i s s e r t a t i o np r o p o s e st h ed i r e c ta l g o r i t h md e ea n di n d i r e c ta l g o r i t h mm c c ef o rc o m p l e t e e x c h a n g eo nc l u s t e r sc o n n e c t e db ye t h e m e ts w i t c h e dh i e r a r c h i c a ln e t w o r k t h et w oa l g o r i t h m s f u l l vu t i l i z e dt h eb a n d w i d t hi nt h eb o t t l e n e c kf i n k sa n dt h e o r e t i c a l l ya c h i e v et h el o w e rb o u n d so n m e s s a g et r a n s m i s s i o n i na d d i t i o n ，t h ea l g o r i t h mm c c es i g n i f i c a n t l yr e d u c e sm e s s a g es t a r t u pc o s t a n ds y n c h r o n i z a t i o nc o s ts oa st of u r t h e ri m p r o v et h ec o m m u n i c a t i o np e r f o r m a n c eo fc o m p l e t e e x c h a n g e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e o t h e rc o m p l e t ee x c h a n g ea l g o r i t h m si n c l u d e d t w op r o p o s e da l g o r i t h m ss i g n i f i c a n t l yo u t l ； e r f o r m i nm p i c ha n dl a m m p i ，o ne t h e m e ts w i t c h e d i i i a b s t r a c t c l u s t e r sw i t hl l i e r a r c h i c mn e t w o r kt o p o l o g i e sw h e nt h em e s s a g es i z ei sl o n g t om i n i m i z em u l t i c a s tl a t e n c ya n de l i m i n a t et h em e m o qb o t t l e n e c ki n d u c e db yt r a d i t i o n a l m u l t i c a s ti ns o f t w a r e ，t h i sd i s s e r t a t i o nt a k e si n t oa c c o u n tm u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k s w h i c hs u p p o r tc o n c u r r e n th a r d w a r em u l t i c a s ti nt h ei n t e r n a ls w i t c hf a b r i co fr o u t e r sa n ds w i t c h e s t h i sd i s s e r t a t i o np r o p o s e sac o s t e f f e c t i v ew i d e - s e n s en o n b l o c k i n gf o u rs t a g ec l o s - t y p em u l t i c a s t n e t w o r ka n dt h em u l t i c a s tr o u t i n ga l g o r i t h m c o m p a r e dw i t hp r e v i o u sw i d e s e n s en o n b l o c k i n g m u l t i c a s tn e t w o r k s ，t h ep r o p o s e dm u l t i c a s tn e t w o r kh a sf o l l o w i n ga d v a n t a g e s ：1 ) t h eh a r d w a r e c o s t , i nt e r m so ft h en u m b e ro fc r o s s p o i n t s ，i sa b o u t1 2 n 5 ，w h i c hi so n l yas m a l lc o n s t a n tf a c t o r h i g h e rt h a nt h a to fw i d e s e n s en o n b l o c k i n gp e r m u t a t i o nn e t w o r k s ；2 ) t h et i m ec o m p l e x i t yo f m u l t i c a s tr o u t i n ga l g o r i t h mi so ( 加，w h i c hi sc o n c e p t u a l l ys i m p l ea n de a s i l yi m p l e m e n t e db y h a r d w a r e ；3 ) i tr e d u c e st h en u m b e ro fp o r t si ne a c hs w i t c hm o d u l e ，w h i c hi sb e t t e rf o rv l s i i m p l e m e n t ；4 ) t h ea d d i t i o n a ls t a g eo fs w i t c h e sc a l le f f e c t i v e l yb a l a n c em u l t i c a s tl o a d s ，t h e r e f o r e i m p r o v e st h ef l e x i b i l i t yo ft h en e t w o r k f i n a l l y , t h i sd i s s e r t a t i o ne x t e n s i v e l ys t u d i e sw i d e s e n s en o n b l o c k i n gk - f o l dm u l t i c a s tn e t w o r k s ， i nw h i c ha n yd e s t i n a t i o nn o d ec a nb ei n v o l v e di nu pt oks i m u l t a n e o u sm u l t i c a s tc o n n e c t i o n si na n o n b l o c k i n gm a n n e r t h e s en e t w o r k sc a ne f f e c t i v e l yr e d u c ee x t e r n a lb l o c k i n go fm u l t i c a s t a s s i g n m e n t ，s ot h a tt h e yc a np r o v i d eb e t t e rq o s ( q u a l i t yo fs e r v i c e ) f u n c t i o nf o ra r b i t r a r y m u l t i c a s tc o m m u n i c a t i o n i na d d i t i o n ，t h en e t w o r k sh a v eam u c hl o w e rh a r d w a r ec o s tt h a nt h a to f s i m p l yp u t t i n gkc o p i e so f1 - f o l dn e t w o r kt o g e t h e r b yr e c a l c u l a t i n gt h en u m b e ro fs w i t c h e so ft h e i n t e r m e d i a t es t a g e si naw i d e s e n s e n o n b l o c k i n gf o u r - s t a g ec l o sn e t w o r k ，t h i sd i s s e r t a t i o n p r o v i d e ss u f f i c i e n ti n t e r n a lp a t h sb e t w e e ni n p u t sa n do u t p u t st or e a l i z ek - f o l dm u l t i c a s tr o u t i n g i n s p i r e db y t h i si d e a ，t w ow i d e s e n s en o n b l o c k i n gk - f o l dm u l t i c a s tr o u t i n ga l g o r i t h m sa n d c o r r e s p o n d i n gh a r d w a r ec o n d i t i o n sh a v eb e e np r o p o s e d a l t h o u g ht h ew h o l er e s e a r c hw o r ki sc o n d u c t e dt om e e tt h ed e f i n i t er e q u i r e m e n to fa p p l i c a t i o n s i np a r a l l e la n dd i s t r i b u t e ds y s t e m s ，t h ep r o p o s e dw i d e s e n s en o n b l o c k i n gm u l t i c a s tn e t w o r k sa r e n o tl i m i t e dt om u l t i c o m p u t e r s t h e yc a nb ea l s oa p p l i e di nr o u t e r sa n ds w i t c h e sf o rw i d ea r e a n e t w o r k sa n dl o c a la r e an e t w o r k s k e yw o r d s ：i n t e r c o n n e c t i o nn e t w o r k ，c o l l e c t i v ec o m m u n i c a t i o n ，t o m s ，a l l t o a l lp e r s o n a l i z e d c o m m u n i c a t i o n ，c o m p l e t ee x c h a n g e ，c l u s t e r ，w i d e s e n s en o n b l o c k i n g ，m u l t i c a s t ， m u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k ( m i n ) ，p a r a l l e lc o m m u n i c a t i o nm o d e l i v 中国科学技术大学博士学位论文第一章绪论 第一章绪论弟一早珀t 匕 互连网络目前正日益广泛地应用于许多不同的领域中，小到超大规模集成电 路( v l s i ) 的内部总线，大到计算机广域网。互连网络应用主要包括底板总线和 系统域网s a n ( s y s t e m a r e an e t w o r k ) 、电话交换网络、a t m ( a s y n c h r o n o u s t r a n s f e rm o d e ) 和p 交换机内部网络，同时还包括向量超级计算机中处理器存 储器互连、多计算机和分布式共享存储多处理器的互连网络、工作站集群、局域 网、城域网、工业用网络等，并且互连网络的应用还在不断增长。互连网络的特 性和成本与具体应用密切相关，因此不存在通用的解决方案。 对高性能和高可靠性的需求推动了多计算机互连网络技术的发展，这些技术 又被用来提高分布式共享存储多处理器系统的可扩展性。而分布式共享存储多处 理器对互连网络有更高的要求，这又直接推动了互连网络技术的发展。最近，这 些技术被推广应用到局域网中。因此，多计算机互连网络的发展进步是其它结构 或环境发展的基础。 本章首先介绍了并行计算和并行计算机的体系结构对互连网络的需求以及 互连网络的分类，随后介绍了互连网络所涉及的几个重要技术问题，包括拓扑结 构、流控制机制、交换技术和路由算法。最后给出本论文的研究内容和组织结构。 1 1 并行计算与互连网络 当前科学技术迅猛发展，人类对高性能计算技术的需求越来越大。自上世纪 8 0 年代以来，计算机处理器的性能每1 8 个月翻一番，但仍不能满足国防、航 空航天、石油勘探与开发、材料设计和生命科学等应用领域对高性能计算的需求。 目前出现了许多具有重大挑战性的应用问题，如全球天气预报、分子动力学实验、 核试验的模拟和生物遗产密码破译等。这些应用问题都要求计算机具有万亿次 ( t e r a f l o p s ) 甚至千万亿次( p e t a f l o p s ) 以上的计算能力，而单个处理器即使集成 度达到极限也是远远不够的，唯一的途径就是把成千上万个处理器连接起来，组 成并行计算机。例如，在最新公布( 2 0 0 5 年1 1 月) 的全世界速度最快的超级计 算机5 0 0 强【2 】排名中，排名第一的是i b m 的b l u eg e n e l 【3 】，其峰值速度超过每 秒2 8 0 6 t e r a ( 1 0 1 2 ) 次浮点运算，所用的处理器数多达6 5 ，5 3 6 个。为了连接这么多 的处理结点，获得如此之高的计算速度，就必须设计高性能的互连网络和提供高 效的通信系统。 互连网络在多计算机系统中占有重要的地位，对它的研究已经形成了一个门 中国科学技术大学博士学位论文 第一章绪论 类广泛的学科。如果从电话网络算起，互连网络的研究已有四十多年的历史。动 态互连网络基本上是从电话网络移用过来的，大多数分析方法在电话网络的研究 中就己建立。从研究的重点来看，互连网络的研究最初集中在拓扑结构和功能特 性上，在多计算机出现以后，大量与实现、性能有关的问题成为研究重点。互连 网络的研究内容很多，包括拓扑结构理论、网络系统设计、网络嵌入与划分、路 由算法、聚合通信( c o l l e c t i v ec o m m u n i c a t i o n ) 算法、v l s i 设计及性能评价等。 各方向每年都有大量的研究成果发表，这些研究为多计算机的发展起到了重大作 用，但是现在仍有大量的理论和实现上的问题亟待解决。 1 2 并行计算机体系结构 本节将从系统结构的角度简单介绍最流行的并行计算机体系结构，主要侧重 于互连网络在其中扮演的角色。 根据存储器是否共享，并行计算机基本上可以分为分布式存储( d i s t r i b u t e d m e m o r y ) 多处理机和共享存储( s h a r e dm e m o r y ) 多处理机。 ( a ) 分布式存储多处理机 ( b ) 共享存储多处理机 图1 1 并行计算机的两种基本结构 图1 2 分布式共享存储多处理机 分布式存储多处理机又被称为多计算机，由多个处理结点组成，每个处理结 点都有自己的局部存储器，结点之间通过在互连网络上传递消息进行通信，其结 构如图1 1 ( a ) 所示。代表性的机器有i n t e lp a r a g o n 、m i tj - m a c h i n e 和n c u b e 3 。 分布式存储多计算机具有很好的可扩展性，并且系统的设计相对简单。但是在这 种系统中，处理器之间的通信是通过显式的消息传递( m e s s a g ep a s s i n g ) 实现的。 中国科学技术大学博= 卜学位论文第一章绪论 消息传递使程序设计者在编程时就需要考虑数据在结点上的分配和负载平衡，这 增加了程序设计者的负担。但是当处理机台数较多时，也只有消息传递并行程序 设计方式才能发挥其潜在的并行计算性能。 在共享存储多处理机系统中，所有处理器具有统一的地址空间，处理器之间 的通信是通过访问共享变量来实现的，因而编程比较容易。图1 1 ( b ) 给出了这种 系统的结构。由于系统中所有处理器访问共享存储器的时间都相同，因此这种结 构也被称为均匀存储器访问( u n i f o r mm e m o r ya c c e s s ，简称u m a ) 结构。对称 多处理机( s y m m e t r i cm u l t i p r o c e s s o r s ， 简称s m p ) 就是这种结构的一个实例。 共享存储多处理机尽管编程简单，但其可扩展性受到限制。因为访问存储器的时 间包含了互连网络的通信时延，当处理机的数目增加时，多个处理机对同一存储 器的访问必然会造成严重的冲突和延迟，从而影响系统的性能，所以用共享存储 模型来构造大规模并行处理机是相当困难的。代表性的共享存储多处理机包括 c r a yc 9 0 、c r a yt 9 0 和n e cs x 4 。s m p 系统则包括i b mr 5 0 、s g ip o w e r c h a l l e n g e 和d e ca l p h a 服务器8 4 0 0 。 由于上面两种结构都各有利弊，因此结合分布式存储系统的可扩展性和共享 存储系统的易编程性，产生了目前比较流行的分布式共享存储d s m ( d i s t r i b u t e d s h a r e dm e m o r y ) 系统。这种系统物理上采用分布式存储的结构，逻辑上则将分 布的存储器用硬件和软件构成共享的统一地址空间，如图1 2 所示，其中结点表 示一个或多个处理器。和多计算机一样，当结点访问远程的存储器时，需要通过 互连网络。分布式共享存储多处理机和多计算机的主要区别在于，前者的消息是 由访存操作引起的，而后者则是由系统函数调用引起的。为了减少存储器访问的 延迟，每个结点都有多级高速缓存，以便匹配处理器和存储器的速度。当d s m 中每台处理机直接访问它的本地存储器时，所用的时间开销小于访问远程存储器 的时间，所以这种结构被称为非均匀存储器访问n u m a ( n o n u n i f o r mm e m o r y a c c e s s ) 结构。这种结构提高了可扩展性和易编程性，但是需要把物理上分布的 存储器映射成统一的共享地址空间，因而增加了系统设计的复杂性。目前代表性 的机器有s t a n f o r dd a s h 、f l a s h 、c r a yt 3 d 和s g io r i g i n 。 分布存储和共享存储结合的多处理机结点的机群( c l u s t e r ) 系统是目前并行 计算研究中的另一个热点。机群系统由于采用低廉的商品化互连网络，而不是专 用互连网络，大大降低了成本，因而也有广泛的市场。在机群系统中，结点可以 是s m p 服务器、工作站，甚至是一台p c 机( 也称为b e o w u l f 系统) 。连接结点 的互连网络可以是高速网络、高性能开关( 例如m y r i n e t ，s e v e r n e t 和i n f i n i b a n d 等) ，甚至可以是以太网等。在s m p 机群中，多个结点通过高速网络互连，结 点内部采用共享存储，而结点之间采用消息传递方式来通信，如i b m 的a s c ib l u e 中国科学技术大学博= i ：学位论文第一章绪论 p a c i f i c 就是由1 4 6 4 个结点组成，每个结点包含4 个处理器。虽然机群系统在性 能上还不能与采用专门互连网络设计的并行计算机相媲美，但是它低廉的价格是 设计系统时应考虑的有利因素。 在设计超级计算机系统时，最难的技术问题是设计处理器之间通信的互连网 络。互连网络的选择决定了多计算机系统的许多重要特性，例如机器的大部分价 格、性能、可靠性、可扩展性、易编程性和实现的复杂性。可见，互连网络在多 计算机系统中占有重要的地位。除非特别指出，本文主要以分布式存储多计算机 系统为主要研究对象。 总之，不论采用何种体系结构，互连网络都是其中的研究热点。本文的工作 就选题于这个领域。 1 3 互连网络分类 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用 于在多计算机系统的处理结点之间或多个功能部件之间传递包含数据和同步信 息的消息。互连网络在现代并行计算机中扮演者十分重要的角色，已成为并行处 理系统的核心组成部分。己知的互连网络按照网络拓扑结构可分为四类 4 】：共享 介质网络( s h a r e d m e d i u mn e t w o r k ) 、直接网络( d i r e c tn e t w o r k ) 、间接网络( i n d i r e c t n e t w o r k 或s w i t c h b a s e dn e t w o r k ) 和混合网络( h y b r i dn e t w o r k ) 。 1 3 1 共享介质网络 在共享介质网络结构中，所有的通信设备共享传输介质，同一时刻只允许一 个设备使用网络，如图1 3 所示。这种网络的一个重要问题是仲裁策略，当网络 访问产生冲突时，由仲裁机制来决定介质的使用者。根据仲裁机制的不同，共享 介质网络又可分为争用总线( c o n t e n t i o nb u s ) 、令牌总线( t o k e nb u s ) 、令牌环( t o k e n r i n g ) 和底板总线( b a c k p l a n eb u s ) 等。 图1 3 共享介质网络 共享介质网络的优点是它具有支持原子广播的能力，网络上所有的设备都可 以监听网络活动，接受共享介质上传输的信息，因此可以有效地支持那些要求一 对全或对多广播服务的应用，如栅栏同步和监听c a c h e 一致性协议。由于网络 带宽的局限性，共享介质成为系统扩展的瓶颈，因此这类网络不适用于大规模的 4 中国科学技术大学博：匕学位论文第一章绪论 系统，一般用于局域网和用于单处理器内部和多处理器中的底板通信。 1 3 2 直接网络 直接网络是指网络中的每个结点都与其它一些结点直接相连的网络。由于这 类网络在运行过程中不能改变网络的连接方式，因此也被称为静态网络。在直接 网络中，结点之间的连接方式决定了互连网络的拓扑结构。网孔( m e s h ) 、环网 ( t o r u s ) 和超立方体( h y p e r c u b e ) 都是典型的直接网络，而k 元，z 一立方体则是 这三种网络的通用形式。其它如树( t r e e ) 、带环立方( c u b e c o n n e c t e dc y c l e ) 、 星图( s t a rg r a p h ) 等也都是经常被研究的直接网络。图1 4 ( a ) 和图1 4 ( b ) 分别描 述了一个6 6 的网孔和一个6 6 的环网，而图1 4 ( c ) 1 ) l j j 是一个4 维的超立方体 网络。 广广广m liiiil iiilii liilii iliiii ( a ) 6 6 网孔 i 一l气一、一、一上 illi 一- o - o 一- o - 0 一- o 、 liliii 一- o - 一- 0 一- 一- 、 liiii 一- 0 一- 一- 0 一- 卜、 iliiil ，一- 一- o 一 - 0 一- 0 一 - 0 、 iiilii 一一- 0 一一- 一- 、 ( b ) 6 6 环网 ( b ) 4 维超立方体 图1 4 三种典型的直接网络 1 3 2 1 结点的结构 在直接网络中，每个结点由处理器、存储器、路由器( r o u t e r ) 和其它功能 单元组成，如图1 5 所示。路由器的主要功能是完成结点之间的消息传递。由于 路由器在直接网络中占有重要的地位，因此直接网络也称为基于路由器的网络。 其它 处理器 局部 功能单元存储器 iii fj 内部通道 1 路由器r - 叫卜卜 图1 5 直接网络中结点的结构 虽然本地处理器就可以实现路由的功能，但在高性能计算机系统中一般都采 中国科学技术大学博士学位论文第一章绪论 用专用的路由器，以便每个结点的计算和通信操作可以同时进行。路由器的一般 结构如图1 6 所示，主要包括五个部分：接口通道、链路控制器、缓冲区、开关、 路由及仲裁单元。 接口通道每个路由器都有几对外部通道与相邻结点的路由器相连接。每 对外部通道中的一个用作输入，另一个用作输出。每个路由器还通过一对 ( 或多对) 内部通道与本地的处理器相连接。每对内部通道中，输入通道 通常被称为注射通道( i n j e c t i o nc h a n n e l ) ，用于将本地处理器发出的消息 注射到网络中去：输出通道则通常被称为消费通道( c o n s u m p t i o nc h a n n e l ) 、 排除通道( e j e c t i o nc h a n n e l ) 或递送通道( d e l i v e r yc h a n n e l ) ，用于将从网 络中接收到的消息传送到本地处理器。本文中，除非特别声明，通道( 或 链路) 指的都是外部通道。 链路控制器( l c ) 用来提供相邻路由器之间的握手信号，以实现消息在物 理通道上的传输。 缓冲区用来暂时存储传输中的消息，通常由f i f o ( f i r s ti nf i r s to u t ) 存 储器构成。在图1 6 所示的模型中，每个输入通道和每个输出通道( 包括 内部通道) 都有缓冲区。具体实现时可以只设立输入通道缓冲区或只设立 输出通道缓冲区。 开关负责连接路由器的输入缓冲区和输出缓冲区。高速路由器通常采用 全连接的交叉开关，而低速路由器中的开关不一定都是全连接的。 路由及仲裁单元用来实现路由算法，为输入通道中的消息选择一条输出 通道并设置开关。如果多个消息同时申请同一个输出通道，该部件对它们 进行仲裁。 输入通道 图i 6