（计算机科学与技术专业论文）基于kary+ncube网络的高效通信.pdf

国防科学技术人学研究生院学位论文 摘要 互连网络子系统是并行处理计算机系统的重要组成部分。随着处理器数目的不断增 加以及处理器计算能力的不断提高，处理器之间的通信问题变得越来越突出，设计高性 能的互连通信子系统成为提高并行计算机系统性能的关键。而幻：连通信子系统的性能常 常受限于路由算法和通信方式，底层硬件得不到充分利用，造成网络通信系统实际使用 性能低效。 本文主要研究如何在通用的k - a r yn c u b e 网络上实现高效的通信，研究重点是自适 应路由算法和组播算法。 设计自适应路由算法首先需解决网络死锁问题。对于无边带连接的k - a r yn c u b e 网 络( 网格) ，我们利用虚跨步切换技术中消息的依存关系只与相邻缓冲区队列有关的特 点，设计实现了基于信约和报文路由信息的新型流控策略一r i f c ( r o u t i n g i n f o r m a t i o n b a s e df l o wc o m r 0 1 ) 。在r i f c 基础上，设计了完全自适应路由算法一 f a r ( f u l l ya d a p t i v er o u t i n g ) 算法。通过证明，我们得出：在采用r i f c 流控策略、虚跨 步切换的无边带连接的k - a r yn c u b e 网络中，f a r 路由算法是无死锁的。 我们在r s i m 模拟器上用实际应用程序测试了f a r 路山算法的性能。通过修改 r s i m 的网络模拟器一n e t s i m 的代码，实现了r i f c 流控和f a r 路由算法。模拟结果 表明：在二维网格中，f a r 路由算法的性能优于维序路由算法的性能，无论后者采用虫 孔切换还是虚跨步切换。 对于边带连接的k - a r yn c u b e 网络( 环网) ，我们综合b u b b l e 流控和r i f c 流控的设 计思想，设计实现了一种新的流控策略- - r i a b f c ( r o u t i n gi n f o r m a t i o n - b a s e da n d b u b b l e b a s e df l o wc o n t r 0 1 ) 。基于r i a b f c ，设计了完全自适应路由算法一n f a r ( n e w f u l l ya d a p t i v er o u t i n g ) 算法。并且证明了：对于采用r i a b f c 流控策略、虚跨步切换的 边带连接的k - a r yn c u b e 网络，n f a r 路由算法是无死锁的。 为了模拟n f a r 路由算法和组播算法的性能，我们采用c + + 语言设计实现了称为 r i n g n e t s i m 的模拟器。r i n g n e t s i m 模拟器实现二维环网结构采用离散事件驱动。在 r i n g n e t s i m 模拟器上，我们选择了不同的通信模式和仲裁策略，对n f a r 路由算法进 行了测试。模拟结果表明：在二维环网中，n f a r 自适应路由算法的性能优于维序路由 算法。 第f v 页 国防科学技术大学研究生院学位论文 高效的组播操作是改善通信系统性能的重要手段。另外在软件方面，分布存储和分 布共享存储编程模式都要求底层互连网络子系统支持聚合通信，而组播是实现聚合通信 中其它操作的基础，我们采用硬件实现组播操作。对于二维环网，我们设计了报文多目 标地址编、译码和报文复制操作实现方案，采用基于底层路由的思想，设计了组播算法 一2 d m r ( 2 1 3 m u l t i c a s t r o u t i n g ) ，解决了多目标路由问题。2 d m r 组播路由算法基于n f a r 路由算法。我们分析证明了：在虚跨步切换的二维环网中，2 d m r 算法无死锁。 我们采用r i n g n e t s i m 模拟器对2 d m r 组播路由算法进行了性能模拟。结果显示： 在二维环网中，采用2 d m r 组播路由算法可以很好地支持组播操作，大大提高系统性能。 最后，我们设计实现了适用于二维环网、支持组播操作的自适应路由芯片。实际测 试结果表明：该路由芯片的性能突出。 关键词 并行处理系统，k - a r yn - c u b e 网络，r i f c 流控，f a r 路由算法，r l a b f c 流控，n f a r 路由算法，r s i m 模拟器，r i n g n e t s i m 模拟器，2 d m r 组播路由算法。 第v 页 一一一一 国坊科学技术大学研究生院学位论文 = ! ! ! ! ! 自自! ! ! ! ! ! ! = = = = = = = = = = = = 2 a b s t r a c t t h ei n t e r c o n n e c t i o nc o m m u n i c a t i o ns u b s y s t e mi s a l l i m p o r t a n tp a r t o f p a r a l l e l p r o c e s s i n gc o m p u t e rs y s t e m s w i mt h et r c n d so fi n c r e a s i n gp r o c e s s o rs p e e d i n c r e a s i n gs i z e o fp a r a l l e ls y s t e m sa n ds e p a r a t i o no fp r o c e s s o r sa sc o m p l e t ec o m p u t e r s ，t h ec o m m u n i c a t i o n s u p p o r tb e t w e e nt h ep r o c e s s o r sh a sb e c o m em o r ea n dm o r ei m p o r t a n tt o t h eo v e r a l l p e r f o r m a n c eo ft h ep a r a l l e ls y s t e m t h e r e f o r e ，r e a l i z i n gah i g h - p e r f o r m a n e ec o m m u n i c a t i o n s u b s y s t e mi s c r i t i c a lt ot h ep e r f o r m a n c eo fap a r a l l e l s y s t e m t h ep e r f o r m a n c eo f i m e r c o n n e c t i o nc o m m u n i c a t i o ns u b s y s t e mi su s u a l l yr e s t r i c t e db yr o u t i n ga l g o r i t h ma n d c o m m u n i c a t i o nm o d ea n dt h ep o w e ro ft h eu n d e r l y i n gi n t e r c o n n e c t i o nn e t w o r kc a n n o tb e u s e df u l l y t h e r c f o r e , t h ei n t e r c o n n e c t i o nc o m m u n i c a t i o ns u b s y s t e mj si n e f f i c i e n t 。 t h eo b j e c t i v eo ft h i sd i s s e r t a t o i ni st ot a k et h ec h a l l e n g eo fp r o v i d i n ge f f i c i e n t c o m m u n i c a t i o no nk - a r yn c u b en e t w o r k s w el a ys t r e s so nt h er e s e a r c ho fa d a p t i v er o u t i n g a l g o r i t h m sa n dm u l t i c a s ta l g o r i t h m s t h ep r o b l e mo fd e a d l o c kq u e s t i o nc a u s e db yp h y s i c a lt o p o l o g ys t r u c t u r eo rr o u t i n g s h o u l db es o l v e db e f o r et h ea d a p t i v er o u t i n ga l g o r i t h m ，f o c u s i n go nt h e p a r t i c u l a r c h a r a c t e r i s t i c so fv i r t u a lc u t t h r o u g hs w i t c h i n gn e t w o r k ，w ef i n dt h a tm e s s a g ed e p e n d e n c i e s a r el o c a l i z e db e t w e e na d j a c e n tq u e u e s u s i n gt h i sc h a r a c t e r i s t i c ，w ed e s i g nt h en o v e ls t r m e g y o ff l o wc o n t r o lc a l l e dr i f c ( r o u t i n gi n f o r m a t i o n b a s e df l o wc o n t r 0 1 ) t h ef l o wc o n t r o l s t r a t e g yo fr i f cb u i l d s o nv i r t u a lc u t - t h r o u g hs w i t c h i n ga n dc r e d i t - b a s e df l o wc o n t r o l m e c h a n i s ma n da n a l y z e st h er o u t i n gi n f o r m a t i o nt or e a l i z et h ep o i n t p o i n tf l o wc o n t r 0 1 b a s e d o nt h er i f c ，w ed e s i g nt h ef u l l ya d a p t i v er o u t i n g ( f a r ) a l g o r i t h m i nt h e k - a r yn - c u b e n e t w o r k sw i t h o u tw r a p a r o u n dc o n n e c t i o n s ，w h e nt h ef l o wc o n t r o ls t r a t e g yo fr i f ci s a c c e p t e d ，f a ra l g o r i t h mc a r lg e tt h eg o a l si n c l u d i n gd e a d l o c k - f r e ea n dm i n i m a ld i s t a n c ee v e n i ft h ec y c l i cd e p e n d e n c i e se x i s t i nt h i sd i s s e r t a t i o n ，t h ed e t a i lp r o o fi s p r o v i d e df o rt h e s e c o n c l u s i o n s w ea d a p tt h es o u r c ec o d eo f n e t s i mt h a ti sas i m u l a t o ro f n e t w o r ka n dr e a l i z et h ef l o w c o n t r o lo fr i f ca n df a r a l g o r i t h mi nn e t s i m w ea d o p tt h ea c t u a la p p l i c a t i o np r o g r a m st o t e s tt h ep e r f o r m a n c eo ff a ro nr s i m t h es i m u l a t i o nr e s u l t ss h o wt h a tf a rr o u t i n g 国防科学技术大学碜f 究生院学位论文 a l g o r i t h mo w n sp r e f e r a b l ep e r f o r m a n c ec o m p a r e dw i t hd i m e n s i o n a lo r d e rr o u t i n ga l g o r i t h m o n2 dm e s hn e t w o r k b yt h ec o m b i n a t i o no ff l o wc o n t r o lo fb u b b l ea n dr 1 f c ，w ed e s i g nt h en e ws t r a t e g yo f f l o wc o n t r o lc a l l e dr i a b f c ( r o u t i n gi n f o r m a t i o n b a s e da n db u b b l e b a s e df l o wc o n t r 0 1 ) f o rk - a r yn c u b en e t w o r k sw i t hw r a p a r o u n dc o n n e c t i o n s b a s e do nt h er i a b f c ，w ed e s i g n t h en e wf u l l ya d a p t i v er o u t i n g ( n f a r ) a l g o r i t h m i nt h i sd i s s e r t a t i o n ，w ep r o v et h a tn f a r r o u t i n ga l g o r i t h mi sd e a d l o c k f r e ef o rt h ev i r t u a lc u t - t h r o u g hk - a r yn c u b en e t w o r k sw i t h w r a p a r o u n dc o n n e c t i o n sw h e nt h ef l o wc o n t r o lo fr i a b f ci sa c c e p t e d i no r d e rt oe v a l u a t et h ep e r f o r m a n c eo fn f a ra l g o r i t h ma n dm u l t i c a s ta l g o r i t h m ，w e d e s i g nt h es i m u l a t o rn a m e d a sr i n g n e t s i m r i n g n e t s i mi sp r o g r a m m e dw i t hc + + l a n g u a g e a n dr e a l i z e st h es t r u c t u r eo fr i n gn e t w o r ka n di sd r i v e nb ys c a r e re v e n t s w ea d o p td i f f e r e n t c o m m u n i c a t i o np a t t e r n st ot e s tt h ep e r f o r m a n c eo fn f a ro nr i n g n e t s i m t h es i m u l a t i o n r e s u l t ss h o wt h a tt h ep e r f o r m a n c eo fr o u t i n ga l g o r i t h mo fn f a ri sb e t t e rt h a nt h e d i m e n s i o n a lo r d e rr o u t i n ga l g o r i t h mo nt w o d i m e n s i o nr i n gn e t w o r k i nt h ei n t e r c o n n e c t i o nn e t w o r ks u b s y s t e m ，r e a l i z i n gt h ec o n c i s ea n de f f i c i e n tm u l t i c a s t o p e r a t i o ni sap e r f e c tm e t h o dt oa c h i e v et h ew e l lc 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 p r o g r a m m i n gm o d e so fd i s t r i b u t i n gm e m o r ya n dd i s t r i b u t e ds h a r i n gm e m o r yd e m a n dt h e u n d e r l y i n gi n t e r c o n n e c t i o nn e t w o r k t os u p p o r tt h ec o l l e c t i v ec o m m u n i c a t i o n t h em u l t i e a s ti s t h eb a s eo fo t h e ro p e r a t i o n si nc o l l e c t i v ec o m m u n i c a t i o n w ed e c i d et or e a l i z et h em u l t i c a s t o p e r a t i o nw i t h h a r d w a r es u p p o r t f o rt w o d e m i n s i o nr i n gn e t w o r k ，w er e a l i z e t h e e n c o d i n g d e c o d i n go p e r a t i o no fm u l t i d e s t i n a t i o na d d r e s sa n dd u p l i c a t i o no fp a c k e t i no r d e r t o s u p p o r t t h em u l t i - d e s t i n a t i o n r o u t i n g ， w e d e s i g n t h em u l t i c a s t r o u t i n g a l g o r i t h m - 2 d m r ( 2 - dm u l t i c a s tr o u t i n g ) a tt h es a m et i m e ，w ep r o v et h a tt h em u l t i c a s t r o u t i n ga l g o r i t h mi sd e a d l o c k - f r e e t h ep e r f o r m a n c ee v a l u a t i o no f2 d m ra l g o r i t h mi sd o n e o nt h es i m u l a t o ro fr i n g n e t s i m t h es i m u l a t i o nr e s u l t ss h o wt h a t2 d m ra l g o r i t h mc a n s u p p o r tt h em u l t i c a s to p e r a t i o nw e l la n di m p r o v et h ep e r f o r m a n c eo fs y s t e m f i n a l l y , t h e a d a p t i v er o u t e ri sd e s i g n e dt os u p p o r tt h em u l t i c a s to p e r a t i o ni nt h et w o d e m i n s i o nr i n g n e t w o r k t h et e s t i n gr e s u l t so f r e a la p p l i c a t i o ni n d i c a t et h ep e r f o r m a n c eo f r o u t e ri sw e l l k e y w o r d s ：p a r a l l e lp r o c e s s i n gc o m p u t e rs y s t e m s ，k - a r yn c u b en e t w o r k s ，f l o w g g v l r 页 国防科学技术大学研究生院学位论文 c o n t r o lo fr i f c ，f a ra l g o r i t h m ，f l o wc o n t r o lo fr i a b f c ，n f a r a l g o r i t h m ，r s i m r i n g n e t s i m ，2 d m ra l g o r i t h m 瓣，l l 页 国防科学技术大学研究生院学位论文 图表目录 图l 。1 并行计算机示意图：( a ) 多计算机；( b ) u m a 共享主存多处理器系统。 ( m = 存储器；p = 处理器) 一2 图1 2 典型结点的体系结构4 图1 3 严格正交直接网络拓扑：( a ) 2 - a r y 4 - c u b e ( 超立方) ( b ) 3 - a r y 2 - c u b e ，( c ) 3 - a r y 3 - c u b e 网格。5 图1 , 4 基于丌关的不规整拓扑网络6 图1 5 虚跨步切换消息时空图9 图1 6 虫孔切换消息的时空图1 0 图1 7 被阻塞的虫孔切换消息1 0 图2 1 平面自适应路由中平面a i 的升序和降序网络1 9 图2 2 单向环。2 0 图2 | 3 二维网格中的转弯模型：( a ) 二维网格中的抽象环；( b ) x y 路由中允许的 4 种转弯( 实线箭头) ；( c ) 西向优先路由中允许的6 种转弯( 实线箭头) 2 i 图2 4 构成抽象环的6 种转弯：( a ) 3 种剩余的左转弯等价于被禁止的右转弯：( b ) 3 种剩余的右转弯等价于被禁止的左转弯；( c ) ( a ) 和( b ) 组合形成环2 l 图2 5 二维网格的虚拟网络：a ) j ，_ y + 虚拟网络，( b ) ny + 虚拟网络，( c ) 爿。y - 虚拟 网络，( d ) ) “y - 虚拟网络2 5 图2 6f a r 自适应路由算法2 9 图2 7 线结构3 0 图2 8k k 的2 d 网格结构3 0 图2 9 路由器缓冲存储区结构 3 1 图2 ，1 0 x + 方向的缓冲区3 1 图2 1 1x + 方向的缓冲区3 2 图2 1 24 - a r y2 c u b em e s h 出现死锁现象3 5 图3 1 网络结点结构3 9 图3 2 两结点的互连3 9 图3 3 响应网络输入输出端口与设备的互连4 0 图3 4 请求网络输入输出端口与设备的互连4 0 图3 ，58 个处理器时，( a ) 响应网络时间：( b ) 请求网络时间4 2 图3 61 6 个处理器时，( a ) 响应网络时间；( b ) 淆求网络时间4 2 图3 73 2 个处理器时，( a ) n l 自应网络时间；( b ) 请求网络时间。4 2 图3 86 4 个处理器时，( a ) q 应网络时间；( b ) 请求网络时间4 3 图3 98 个处理器时，( a ) 响应网络时间：( b ) 请求网络时问。4 4 图3 1 01 6 个处理器时( a ) 响应网络时间；( b ) 请求网络时间4 4 图3 1 l3 2 个处理器时，( a ) 响应网络时间；( b ) 请求刚络时间。4 4 图3 1 26 4 个处理器时，( a ) n l j j 应网络时问：( b ) 请求网络时间4 4 图3 1 38 个处理器时，( a ) l a j 应网络时间：( b ) 请求网络时间。4 5 图3 ，1 41 6 个处理器时，( a ) 响应网络时间；( b ) 请求网络时间4 5 图3 1 53 2 个处理器时，( a ) 响应网络时间； ( b ) 请求网络时间。4 5 第1 页 国防科学技术大学研究生院学位论文 图3 1 66 4 个处理器时，( a ) n l 自应网络时问；( b ) 请求网络时间4 6 图3 1 78 个处理器时，( a ) 响应网络时间；( b ) 清求网络时间。4 6 图3 1 81 6 个处理器时，( a ) n 1 3 应网络时间：( b ) 请求网络刚间4 6 图3 1 93 2 个处理器时，( a ) g l f i j 应网络时间；( b ) 请求网络时间4 7 图3 2 06 4 个处理器时，( a ) 响应网络时间；( b ) 请求网络时间。4 7 图3 2 18 个处理器时，( a ) q f i j 应网络时间；( b ) 请求网络时 u 4 8 图3 2 21 6 个处理器时，( a ) 响应网络时间；( b ) 请求网络时间4 8 图3 2 33 2 个处理器时，( a ) n l 甸应网络时间；( b ) 请求网络时间4 8 图3 2 46 4 个处理器时，( a ) l l l ：, j 应网络时间；( b ) 请求网络时间4 8 图4 1 单个方向环上的b u b b l e 流控5 0 图4 2n f a r 自适应路由算法5 3 图4 3 环结构5 4 图4 4k x k 的2 维环网结构5 4 图4 5 路由器缓冲存储区结构5 4 图4 6x + 方向的缓冲区5 5 图4 7x + 方向的缓冲区5 6 图5 1r i n g n e t s i m 运行主界面5 9 图5 2 运行菜单项“测试”的界面6 0 图5 3 结点参数设置界面6 0 图5 4r i n g n e t s i m 流程图6 1 图5 5a 到b 按先x 再y 的走法6 2 图5 64 x 4 环网的网络延迟6 4 图5 78 8 环网的网络延迟6 4 图5 81 2 x 1 2 环网的网络延迟6 4 图5 94 4 环网的网络延迟6 5 图5 ，1 08 x 8 环网的网络延迟一6 5 图5 1 11 2 1 2 环网的网络延迟6 6 图5 1 24 4 环网的网络延迟一6 6 图5 1 38 8 环网的网络延迟6 7 图5 1 41 2 1 2 环网的网络延迟6 7 图5 1 54 x 4 环网的网络延迟一6 8 图5 1 68 8 环网的网络延迟一6 8 图5 1 71 2 1 2 环网的网络延迟6 8 图6 1 单播与组播操作过程一7 l 图6 2 单播与组播性能比较：( a ) 组播操作；( b ) 单播操作7 l 图6 34 x 3 网格中的结点标记法：( a ) 物理网络，( b ) 高通道网络，( c ) 低通道网络。 7 5 图6 4 二维网格中h l 算法7 7 图6 5 报文头的路由场定义7 9 图6 62 d m r 路由算法8 0 图6 7x + 方向上组播操作过程8 l 图7 14 4 环网的网络延迟8 6 幽7 28 x 8 环网的网络延迟8 6 第1 1 页 国防科学技术大学研究生院学何论文 第l i i 页 独创性声l 烬 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特剐加以标注和致谢的地方外，论文中不包含其他人己 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并袁示谢意 学位论文题目：基王l = ! ! x 坚i ! 坠虽垒煎壶熬烫焦 一 学位论文作者签名：轧 日期：。伽侔 年月 f 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阕和借阅；可以将学位论文的全部或部分内容鳊入有关数据库进行检索 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：基王s = ! 盟里! 叠! 塑垒垫齑鏊亟售 学位论文作者签名： 作者指导教师签名： 蛰! 兰垂 i 笙亟堕 日期： 己。口，年毕月f 口 日期：埘年妒月7 日 国防科学技术大学研究生院学位论文 第一章绪论 计算机互连网络已经有很长的历史。1 9 6 2 年，s o l o m o n 成为第一台采用m e s h 结构 的位串多计算机系统。随后在2 0 世纪7 0 年代，间接互连网络出现了，它用于向量和阵 列计算机中多处理器与多存储体之间的互连。在2 0 世纪8 0 年代，超立方体网络被广泛 采用。2 0 世纪9 0 年代是互连网络研究的黄金时期。多计算机通信需求的驱动、单芯片 v l s i 路由器的实现，使互连网络研究取得一系列革命性突破。研究人员经过大量的研 究，提出了许多死锁和活锁问题的新理论、新的自适应路由算法、新的性能分析方法、 聚合通信的新途径以及新的网络体系结构。采用这些思想的低维直接互连网络取代了7 0 年代的间接互连网络和8 0 年代的超立方体，并被许多商用公司的机器采用。 互连网络技术的发展与高性能计算和并行计算机体系结构的发展有着密切联系。随 着国防、航空航天、生命科学等应用领域对高性能计算需求的不断提高，设计实现具有 万亿次乃至于万亿次计算能力的高性能计算机系统才能满足要求。单机系统已经无法实 现如此高的性能，因此并行技术显得尤为重要，而设计实现高性能互连网络成为其中一 个关键问题。 这一章，我们将首先介绍并行计算机体系结构对互连网络的需求。然后，介绍互连 网络当前通用的一些技术。最后，介绍本文的主要贡献和组织形式。 1 1 并行处理与互连网络 虽然自1 9 8 0 年以柬，处理器的性能差不多每1 8 个月翻一番，但单机的性能仍然 满足不了来自科学、工程、商业等应用领域对高性能计算的需求【2 】。在科学计算领域， 主要是对物理现象的建模和模拟，如计算全球天气预报、分子动力学实验、流体物理实 验等。在工程计算领域，主要包括计算机辅助设计和计算机辅助制造，如自动化设计、 工业流程控制、汽车碰撞实验等。在商业计算领域，主要应用在高效安全处理在线交易， 如数据挖掘、在线预定系统维护等。 这些应用领域的高端计算需要万亿次乃至千万亿次高性能计算机系统才能满足要 求。特别在签署“全面禁止核试验条约”之后，核试验就必须依靠计算机的模拟完成。 美国能源部因此在1 9 9 6 年启动了a s c i 计划，目标在2 0 0 4 年完成具有1 0 0 万亿次处理 第1 页 国防科学技术人学研究生院学位论文 能力的超级计算机3 1 。设计实现如此高性能的并行计算机系统，必须解决处理器、存储 器、输入输出和互连网络等方面存在的问题。目前，处理器的速度发展很快，存储容量 可以通过存储空间的共享得到扩充，而处理器问的远程访问却是系统性能的瓶颈。因此， 设计实现高性能的互连系统已经成为提高并行计算机系统性能的一个关键问题。 1 2 并行计算机体系结构 在这一节，我们简单介绍并行计算机系统的体系结构，主要侧重于介绍互连网络在 其中的作用。 根据存储器是否共享，并行计算机体系结构通常可分为分布存储系统和共享存储系 统两类。分布存储系统由一组处理结点组成，其中每个处理结点都有自己的存储器，通 过互连网络，处理器之间彼此通信，协调工作，其结构如图1 1 ( a ) 所示。这种系统通常 采用消息传递的编程模式，要求编程人员把数据精确地分配给不同的存储器，当一个处 理器需访问其它处理器的存储空间时，必须通过函数调用来实现。这种系统的设计相对 简单，可扩展性好，但编程比较复杂。 互连网络 幽1 1 并行计算机不意图：( a ) 多计算机；( b ) u m a 共享主存多处理器系统。 ( m = 存储器；p = 处理器) 共享主存多处理器系统对所有的处理器提供单一存储器空间，处理器之间的通信通 过访问共享变量完成，简化了处理器之间的数据交换。这种系统采用共享存储编程模式， 编程时不必考虑数据的分配，简化了编程难度。处理器通过互连网络访问共享主存( 见 图】1 ( b ) ) ，系统中所有处理器访问共享存储器的时间相等，这种结构称作一致性存储访 问( 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 m p ) 就是这种 结构的一个实例。由于存储器访问时间包括互连网络的延迟，该延迟随系统规模的增加 而增加，所以这种体系结构可伸缩性差。 后来，共享主存多处理器系统采用了先前为分布计算机系统建立起来的模式，将共 第2 页 国防科学技术大学研究生院学位论文 享存储器物理地分布在多个处理器之间这样就减少了对本地存储器的访问时间。这种 并行计算机称作分布共享主存( d s m ) 多处理器系统。访问远地存储器是通过互连网络 实现的，与分布计算机系统非常类似。d s m 和分布计算机的主要区别在于消息的启动 方式，d s m 利用共享变量访问，而分布计算机系统通过系统功能调用来完成。为了减 少存储器延迟，每一个处理器都设有若干级c a c h e 存储器，以减小处理器和存储器之间 速度差异的影响。d s m 体系结构提供了非一致性存储器访问( n u m a ) 。很明显，与共 享存储系统相比，这种系统提高了可扩展性，同时，由于系统实现单一存储器空间，因 此，它又具有易编程性。这类系统的代表有s t a n f o r dd a s h t 4 1 、f l a s h i ”、s g lo r 涵n 2 0 0 0 、 o r i g i n 3 0 0 0 6 1 等。 分布和共享存储结合的多处理机结点的机群( c l u s t e r ) 系统也是目前比较流行的一 种体系结构，如s m p 机群和实现c a c h e 一致性的n u m a ( c c n u m a ) 机群。s m p 机群 就是将一个s m p 系统作为一个结点，多个结点通过高速网络互连，结点内部采用共享 存储，而结点间采用消息传递方式进行通信。如i b m 公司的a s c iw h i t e 由5 1 2 个结点 组成，每个结点包含1 6 个r s 6 0 0 0 s p 的处理器，结点问用高速的开关相连，构成包含 8 1 9 2 个处理器的系统【7 1 。另一种是由分布共享存储系统作为一个结点，多个结点通过高 速网络互连，结点内部共享存储，结点间采用消息传递。如s g i 公司的a s c ib l u e m o u n t m n 就是由4 8 个结点构成包含6 1 4 4 个处理器的c c n u m a 机群【8 j 。 目前，还有一种在并行系统领域中比较流行的结构是基于工作站或微机的机群系统 1 9 。它们采用高性能互连设备如m y r i n e t l l 0 1 、s e v e r n e t i ”1 以及i n f i n i b a n d i 坨) 等进行互连。 这些设备借鉴并行机互连网络技术，支持构造相对廉价的并行机群系统。虽然在性能上 机群系统还不能与高性能的并行处理机系统相媲美，但它具有相对低廉的价格。 总之，不管上层采用消息传递编程模式还是共享存储编程模式，并行系统的底层结 构都朝一个方向发展，那就是提供高带宽、低延迟、可扩展的互连通信网络。随着处理 器速度的提高，系统规模的不断扩大，互连通信子系统对于并行系统的整体性能尤为重 要。 1 。3 并行计算机系统的互连网络 构成通信系统底层的互连网络是影响并行系统性能的重要因素。它包含的内容很广 泛，这罩讨论影响其性能的一些主要因素。这些因素包括：网络拓扑结构、交换技术、 流控策略、路由算法和通信方式等。 第3 页 国防科学技术大学研究生院学位论文 1 _ 3 1 网络的拓扑结构 根据拓扑结构的不同，互连网络主要包括直接互连网络( d i r e c tn e t w o r k s 或 r o u t e r b a s e dn e t w o r k s ) 和间接互连网络( i n d i r e c tn e t w o r k s 或s w i t c h b a s e dn e t w o r k s ) 。 1 3 1 1 赢接互连网络 直接网络包括一组结点，每个结点直接连接到网络中其它结点的子集上。图1 2 是 一个典型结点的体系结构。 图1 2 典型结点的体系结构 这些结点的公用部件是路由器，负责结点间的消息通信。冈此，直接网络也称作基 于路由器的网络。每一个路由器都与相邻的路由器有直接连接。通常两个相邻结点由一 对方向相反的单向通道连接，也可以使用一条双向通道连接。虽然处理器也可以完成路 由器的功能，但是高性能多计算机系统中大多使用专门的路由器，以使各个结点计算和 通信时间重叠。随着系统中结点的增多，系统的总通信带宽、存储器带宽和计算能力也 相应增加。因此，直接网络是构造大规模并行计算机最流行的互连结构。 每个路由器都支持一定数量的输入和输出通道。内部通道或端口把本地处理器存储 器连接到路由器上。每个路由器通常只提供一对内部通道，但是为了避免本地处理器和 存储器与路由器的通信瓶颈，有些系统也使用多对内部通道