（通信与信息系统专业论文）torus交换结构流量均衡和容错路由算法研究.pdf

摘要 摘要 随着计算机广泛应用于各行各业，计算机应用在国民经济中扮演了越来越重 要的角色。依赖于计算机应用的一些领域如国防、金融、气象对计算机的性能要 求越来越高，它要求具有更快的处理速度，更高的带宽以及更大的存储容量。具 有多处理器的并行计算机为实现高性能计算提供了可行的解决方案。基于多处理 并行计算的相关技术也随之发展起来，如拓扑结构、交换技术、内部路由算法。 t o m s 交换结构由于具有灵活的可扩展性，良好的对称性已成为构建大规模并行 处理系统的常用选择。 在给定网络拓扑结构情况下，影响并行计算系统性能的因素很多：如路由算 法的自适应性、流量分布的均衡性。同时随着交换节点和服务类型的增多，路由 算法具有容错性能以及支持q o s 功能也不断得到重视。本文主要集中于在t o m s 交换结构下自适应均衡路由算法和容错路由算法的研究。 针对以上问题，本研究的主要工作和贡献在于t 提出了一种基于奇偶转弯模 型的自适应均衡路由算法，该路由算法在两层虚网络中引入对偶的奇偶转弯模型， 且数据包在虚网络中可以相互切换，对于所有的数据包而言都具有相同的路由自 适应性，因此可以很好地引导数据流均衡地分布于系统，且受流量模型的影响较 少，最大程度地提高了虚通道的利用率， 程度上减少了系统延时。进一步地， 能够较好地提高系统吞吐量，并在一定 我们提出了基于正向优先负向优先 ( p o s i t i v e f i r s t - n e g a t i v e f i r s t ) 的容错路由算法，该算法充分利用了正向优先负向 优先路由算法良好的自适应性，按照一定规则在双层虚通道上合理地分配数据包 来避免死锁，该算法操作实施简单、计算复杂度低、响应速度快，可以适用于不 同的故障模型的路由。 本文的结构如下： 第一章介绍了多维交换结构的拓扑结构，以及相应的基本交换技术和流控技 术，对路由算法的基本要求如死锁、活锁以及饿死的情况进行了分析。 第二章主要阐述了t o r u s 交换结构中不同机制的路由算法，比较了各自的优 缺点，然后介绍了本文的研究角度和相关工作。 第三章主要研究了基于奇偶转弯模型的自适应路由算法，分析了双层奇偶转 弯模型的路由自适应性以及流量的均衡性，阐述了算法的整体流程图，并进行无 摘要 死锁的证明，然后根据不同的业务流模型，与其它路由算法进行了性能比较。 第四章首先分析了正向优先负向优先自适应均衡路由算法的特性，对它具有 的容错特性进行了研究，针对特定的故障模型情况加一些限制进行绕道路由。然 后阐述了算法在容错路由的过程中正确绕道路由的机制，最后对算法的性能进行 了评估，分析了性能下降的原因及可采用的应对措施。 第五章主要阐述了仿真模型，给出了具体的仿真实验设计方案，模型建立和 主要的功能模块的介绍。 第六章对全文进行了总结，阐述了研究的不足以及以后的发展方向。 关键词：t o m s 交换结构，负载均衡，奇偶转弯模型，正向优先负向优先， 容错路由 a b s t r a c t a b s t r a c t a l o n gw i t ht h ea p p l i c a t i o no fc o m p u t e ri ne v e r yf i l e d ，c o m p u t e rp l a y sam o r ea n d m o r ei m p o r t a n tr o l ei nn a t i o n a le c o n o m i c s t h e s ef i e l d sw h i c hr e l yo nt h ec o m p u t e r m o r es e r i o u s l yd e s i r i n gt h es u p e r c o m p u t e rt h a th a sh i g h e rp r o c e s s i n gs p e e d ，m o r e n e t w o r kb a n d w i d t ha n db i g g e rs t o r a g ec a p a b i l i t y t h ep a r a l l e l m u l t i p r o c e s s o ri sa p o s s i b l e s o l u t i o nt or e a l i z et h e h i 曲 c o m p u t i n gp e r f o r m a n c e t h ec o r r e l a t i o n t e c h n o l o g yb a s e do nt h ep a r a l l e lm u l t i p r o c e s s o ri sa l s od e v e l o p i n gr a p i d l y , s u c ha st h e n e t w o r k t o p o l o g ys t r u c t u r e ，s w i t c h i n gt e c h n o l o g y , r o u t i n ga l g o r i t h m w i t ht h ef e x i b l e s c a l a b i l i t ya n dl a r g e rc a p a c i t y , t o m ss w i t c h i n gf a b r i ci sb e i n gw i d e l yu s e dt oc o n s t r u c t h i g hs p e e dt e r a b i tr o u t c r s t h e r ea r em a n yf a c t o r sa f f e c t i n gt h ep e r f o r m a n c eo fp a r a l l e lm u l t i p r o c e s s o r a c c o r d i n gt ot h en e t w o r kt e c h n o l o g y , s u c ha st h ed e g r e eo fa d a p t i v e n e s so fr o u t i n g a l g o r i t h m ，t h eu n e v e i 】ld i s t r i b u t i n go ft r a f f i c w i t ht h ei n c r e a s i n go ft r a f f i cp a t t e r n sa n d s w i t c h i n gn o d e s ，t h er o u t i n gf u n c t i o nw h i c hi n c l u d ef a u l t t o l e r a n ta n dq o ss u p p o r t i n g a l s od e s i r em o r ea n dm o r ea t t e n t i o n s oi nt h i sp a p e r , 0 1 1 1 a t t e n t i o ni sm a i n l yf o c u s i n g o nt h ef a u l t t o l e r a n tr o u t i n ga n dl o a d - b a l a n c e da d a p t i v er o u t i n g t h ec o n t r i b u t i o n so fo u rr e s e a r c hm a i n l yl i ei 1 1m a tw ef i r s t l yi n t r o d u c et h e l o a d - b a l a n c e da d a p t i v er o u t i n ga l g o r i t h mi nt o m sn e t w o r kb a s e do nt h eo d d e v e nt u r n m o d e l ，i m p o s i n gt h es y m m e t r i co d d e v e nt u r nm o d e l si n t ot h et w ov i r t u a ln e t w o r k s ，a t t h es a m et i m e ，p a c k e tc a ns w i t c hb e t w e e nt h et w ov i r t u a ln e t w o r k si fa b i d eb ys o m e r e s t r i c t i o n ，o u rr o u t i n ga l g o r i t h mp r o v i d et h ee q u a la d a p t i v e n e s sf o ra l lp a c k e t sa n d l o a dt h et r a f f i cd i s t r i b u t ee v e n l y , m o r e o v e rt h ep e r f o r m a n c eo ft h er o u t i n ga l g o r i t h m w h i c hm a ya f f e c t e db yt h et r a f f i cm o d e li sl e s sf l u c t u a n ta n dt h eu t i l i z a t i o no fv i r t u a l c h a n n e li si n c r e a s e da tt h em o s tl e v e l ，s oi tc a np r o v i d et h es t a b l et h r o u g h p u ta n de n d t oe n d d e l a y s e c o n d l y , w ea l s op r o p o s et h et w ol e v e lt u r nm o d e l sf a u l t - t o l e r a n tr o u t i n g a l g o r i t h mb a s e do nt h ec o n v e xa n dc o n v e xf a u l tb l o c k t h ea l g o r i t h mi sb r i n gf o r w a r d b ye x p l o r i n gt h es e l f - c h a r a c t e r i s t i co fp f n fr o u t i n ga l g o r i t h mw h i c hc a np r o v i d et h e f l e x i b l et u r na n dm u t u l - s w i t c h i n gp r o p e r t y , i ti s v e r yu s e f u lw h e na p p l yi nt h e f a u l t - t o l e r a n tf u n c t i o n ，t h ea l g o r i t h mh a st h eg o o dm e r i tt h a ti t sc o s tc o m p l e x i t yi s i i i a b s t r a c t v e r yl o wa n dt h er e s p o n s es p e e di sp r o m p ta n dc a l le a s i l ya p p l yi nd i f f e r e n tf a u l t m o d e l s ，s oi th a st h eg o o dm a n e u v e r a b i l i t y t h i st h e s i si so r g a n i z e da sf o l l o w s ： c h a p t e r1i n t r o d u c e st h et o p o l o g ys t r u c t u r eo fs w i t c h i n gf a b r i c ，t h ec o r r e s p o n d i n g s w i t c h i n gt e c h n o l o g ya n dt h eb a s er e q u i r e m e n to fr o u t i n ga l g o r i t h m ，t h e na n a l y s e st h e d e a d l o c k ，l i v e l o c ka n dt h es t a r v a t i o nw h e nt h ep a c k e tr o u t i n gi nt h en e t w o r k c h a p t e r2m a i n l yi n t r o d u c e st h ed i f f e r e n tr o u t i n gs c h e m e si nt h et o m ss w i t c h f a b r i ca n dc o m p a r e st h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h ep e r f o r m a n c e ，t h e nw e d e d u c tt h er e s e a r c hd i r e c t i o na n dc o n e l a t i o nw o r k c h a p t e r3g i v et h ek e yi d e a lo ft h et r a f f i c - b a l a n c e da d a p t i v e n e s sr o u t i n ga l g o r i t h m b a s e do nt h eo d d e v e l lt u r nm o d e l ，a n a l y s e st h ea d a p t i v e n e s sa n dt h et r a f f i c - b a l a n c e d o ft h et w ol e v e lo d d - e v e nt u r nm o d e l ；t h e nw e b r i n gf o r w a r dt h ew h o l ea l g o r i t h mf l o w a n dd e d u c et h ep r o o fo ft h ed e a d l o c k - f r e e ；a tt h ee n d ，w ec o m p a r et h ep e r f o r m a n c e w i t l lo t h e ra d a p t i v ea l g o r i t h mi nd i f f e r e n tf l o wm o d e l s i nc h a p t e r4 ，w ef i r s t l ya n a l y z et h ea d a p t i v e n e s sa n dl o a d - b a l a n c e dt r a i to ft h e p o s i t i v e - f i r s ta n dn e g a t i v e f i r s tr o u t i n ga l g o r i t h m ，a n dd os o m er e s e a r c h a b o u ti t s f a u l t - t o l e r a n tp r o p e r t y , t h e nw ed os o m er e s t r i c t i o nf o rt h er o u t i n ga l g o r i t h ma c c o r d i n g t ot h es p e c i f i cf a u l tm o d e l s ，s oa st ob y p a s st h ef a u l tn o d e s a tt h es a m et i m e ，w e d e s c r i b et h ef a u l t - t o l e r a n tr o u t i n gs c h e m e s a tt h ee n d ，w ee v a l u a t et h ep e r f o r m a n c eo f t h ea l g o r i t h ma n da n a l y z et h ef a c t o r sa b o u tt h ed e c l i n e dp e r f o r m a n c e t h ep l a t f o r mi sd e s c r i b e di nd e t a i li nc h a p t e r5a n dt h em a i nm o d e l sa leg i v e no u t , a tt h ee n do ft h ed i s s e r t a t i o n , s u m m a r i e sa r em a d e k e yw o r d s ：t o m s ，l o a d - b a l a n c e d ，o d d e v e nt u r nm o d e l ，p o s i t i v e - f i r s ta n dn e g a t i v e - f i r s t , f a u l t - t o l e r a n tr o u t i n g i v 图目录 图目录 图1 1t o m s 和m e s h 交换结构2 图1 22 元4 维h y p e r e u b e 2 图1 3 虚跨步交换时空图。3 图1 4 虫孔交换时空图4 图1 5 疯狂邮差交换的传输时空图5 图1 7 虚通道7 图1 9 支持虚通道流控制的逻辑图一9 图1 1 0t o m s 网络中的一种死锁配置1 0 图2 1 二维t o r u s 交换结构中的路由1 6 图2 2 三维平面自适应路由算法立体图1 8 图2 3 在x y 路由算法中允许的四个拐角1 9 图2 4 正向优先和负向优先路由算法1 9 图2 5m a y - y 算法允许的转弯( 实线) 1 9 图3 1 奇偶转弯模型2 7 图3 2 规定3 。1 对应的奇偶转弯模型2 9 图3 3规定3 2 对应的奇偶转弯模型2 9 图3 5 算法流程图3 4 图3 6 虚通道间的信道依赖图3 6 图3 7 算法性能比较( u n i f o r mt r a f f c ) 3 7 图3 8 算法性能比较( t r a n s p o s et r a f f c ) 3 8 图3 9 算法性能比较( h o t s p o tt r a f f c ) 3 8 图3 1 0 流量在节点中的分布：一3 9 图4 1d o r 路由算法在凸故障模型的容错路由机制一4 1 图4 2 基于中间节点的容错路由机制4 1 图4 3 各种故障模型4 2 图4 5 凸故障模型的位置类型4 4 图4 6 正向优先和负向优先转弯模型4 5 图4 7 及，d m 0 _ 绕道路由4 7 图目录 图4 8d i t r 。，d i m 绕道路由4 7 图4 - 9凸形故障模型下的p f n f 容错路由算法4 9 图4 1 0 凸形故障模型下的消息平均时延和网络吞吐率5 0 图5 1 16 x16t o r u s 交换结构5 3 图5 2 交换节点工作流程图5 4 图5 3 交换节点示意图5 5 图5 4 交换与调度流程图5 7 表目录 表目录 表禾1t o m s 网络中4 种报文定义4 6 表4 2 虚通道使用法则4 9 表5 1 业务模式5 8 x 简略字表 k a r yn - - c u b e k a r r a y 1 3c u b e m p p v c t v c d o r q o s p f n f 简略字表 k 元n 方 m a s s i v e l yp a r a l l e lp r o c e s s o r大规模并行计算机 v i r t u a lc u t - t h r o u g h v i r t u a lc h a n n e l d i m e n s i o no r d e rr o u t i n g q u a l i t yo fs e r v i c e 虚切通 虚通道 维序路由 区分服务 p o s i t i v ef i r s ta n dn e g a t i v ef i r s t 正向优先负向优先 x i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：抑碑易月乡日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：麴 日期：洲口年6 月3 日 第一章绪论 第一章绪论 2 0 世纪以来，计算机在工农业、国防科技、金融领域得到前所未有的大规模 应用，尽管处理器的性能大约每3 年翻一倍，但是由于国防，金融，通信领域出 现的大量具有挑战性的应用，以及网络数据的爆发式增长，使得对计算机要求具 有每秒万亿次级的浮点运算，甚至更高的级别。具有多处理器的并行计算机 ( m a s s i v e l yp a r a l l e lp r o c e s s o r , m p p ) 【l 】为实现高性能计算提供了解决方案，以 满足对计算能力日益增长的要求。而这些大规模并行计算机之间的互联方式、数 据交换、路由算法和流控制技术直接影响到并行计算机的整体性能。因此，并行 计算机之间的拓扑结构，网络的交换技术、路由算法的流量均衡以及容错能力成 为当今各国科学家研究的热点。 1 1 多维交换网络的拓扑结构 常用的多维交换结构有t o m s 、m e s h 。交换结构的维度、拓扑类型与并行计 算机的性能密切相关。针对不断出现的新应用和对性能提高的不懈追求，相关文 献提出了很多新的交换结构【2 】【3 】，如立方连接体环( c u b e c o n n e c t e dc y c l e ) 、d e b r u i j i n 网络和超立方体( 图1 2 ) ，本文将简要介绍m e s h 结构和t o m s 结构。 对于一个n 维网络，设第i 维度上有岛个节点，岛2 ，i = 0 ，1 ，2 ，n 1 ， 则全网共有x k l k 2 1 个节点。维度越高，包含相同数量的节点的网络直 径越短，同样布线更加复杂。 对于一个n 维网络，当且仅当其中任意两节点x 和y ，若满足以下命题： x 与y 相邻，当且仅当对所有i = 0 ，1 ，2 ，z 一1 ，f 布，有吲矽= a i ， 其中田纠= 田似1 。则该刀维网络为一个n 维m e s h 。如果对所有维度i ，都有 j j j = 七，即每一维度上的节点数都为七个，则称该n 维m e s h 为k 元，l 维m e s h 。如 图1 1 ( b ) 图所示。 对于一个n 维网络，当且仅当其中任意两节点x 和y ，若满足以下命题： 石与y 相邻，当且仅当对所有i ，i - - - - - - o ，1 ，2 ，甩- - 1 ，f 剪，有仉俐= 西纠， 其中乃劬= 回俐4 - 1m 耐奄。如果对所有维度f ，都有岛= 七，即每一维度上的节点 数都为k 个，则称该n 维t o m s 为后元”维t o m s 。如图1 1 ( a ) 图所示。 电子科技大学硕士学位论文 由以上定义可知，m e s h 网络中各节点由于处于网络中的位置不同，与其相邻 的节点的个数也不同，所以其结构不具有全网对称性。但是t o m s 结构的定义中 有取模运算，即在m e s h 结构直径的两端加了一条边，这些边通常称为w r a p a r o u n d c h a n n e l s ，其作用是使t o m s 结构中任意一个节点在每一个维度上均有两个相邻节 点，一共有2 咒个邻节点，没有中心节点或者边缘节点区别。因此，t o m s 结构具 有全网对称性。相对于m e s h 结构来说，t o m s 拓扑结构在对分带宽，信息传送距 离方面有优势，但是物理实现和路由算法的死锁避免方面相对要复杂些 一 一j 1r 一 1，1 r j ，1， 1， r1， r ( a ) t o t i 网络 ( b ) 二维m e s h g 习络 图1 1t o m s 和m e s h 交换结构 图i - 2 2 元4 维h y p e r c u b e 一个m p p 系统所采用的交换结构将直接影响它能提供的对分带宽大小、连 接度和流量的均衡性闱。如c r a y t 3 e 路由器采用的是双向三维环网，每个方向1 4 位数据，每条链路6 0 0 m b s ，i n t e lc a v a u i n o 路由器采用的是3 d 拓扑，1 6 位通道 宽度，2 0 0 m ，每个方向4 0 0 m b s 。本文所有的研究将基于t o m s 交换结构下进行 的。 2 第一章绪论 1 2基本的交换技术 在大规模并行计算机网络中，常用的交换技术有电路交换、报文交换、虫孔 交换【5 1 、虚跨步交换( v c t ) 【6 】和疯狂邮差交换1 7 。电路交换在早期的电话网应 用很多，在数据传输前先要从源和目的地之间预定一条物理路径，数据传输完之 前占用的资源不会释放；报文交换是基于存储转发的，在p 网络应用的较多，每 个报文从源节点到目的节点是独立路由的，报文在转发前完全存储在中间节点中。 虫孔交换和虚跨步交换在传输延时和所需要的节点资源方面有较大的进步，下面 将详细介绍虫孔交换、虚跨步交换和疯狂邮差交换。 1 2 1 虚跨步交换技术 前面简要介绍了报文交换，在报文到达目的地之前，报文必须完全存储在中 间节点，且每个报文独立路由，这样在多跳网络中会出现端到端的传输时延过大 的问题，所需要的存储容量大。但是如果前面的几个周期的报文已经包含了路由 信息，只要接收到报文头，就可以马上进行路由决策，而不用等待整个报文接收 完毕，虚跨步( v c t ) 就是基于这样的原理。在当前路由器接收完整的报文前消息 没必要在输出进行缓冲，可以直接跨接到下一个路由器的输入上，在没有阻塞的 情况下，报文头经过每个节点的延时由路由延时和通过路由器和物流通道的传播 延时构成。消息流水地通过各个开关。如果报文头在某个忙输出通道外阻塞，整 个消息就在该节点缓冲。当网路负载很重时，v c t 交换就跟报文交换一样。 链 路 占用时间 图1 - 3 虚跨步交换时空图 v c t 交换技术的信息传输时空图如图1 3 所示。消息经过第一段链路后就被 3 电子科技大学硕士学位论文 阻塞并等待输出通道空闲，在这种情况下，整个报文传输到第一个路由器维持阻 塞，同时等待输出端口空闲。从图中看出，消息成功地跨过第二过路由器并传送 第三段链路。v c t 在低负载时与虫孔交换相似，在高负载时与报文交换相似，此 时链路竞争将迫使报文缓冲在每个节点。成功地跨过每个中间路由器时消息的基 本延时如下： 广l t =d(t，+t，+t)+max(t，+tvetw。) l l( 1 1 )、rf 7 jw 7 l、j 一， i 矽i 1 2 2 虫孔交换技术 为了减少多级交换网中端到端的时延，提高交换机的整体性能，d a l l y 和s e i t z 提出了虫孔路由交换存储策略。其技术的基本原理是：一个消息报文分割成很多 微片，只有头微片中带有路由的相关信息，如源地址和目的地址，头微片先发送 出去进行先期路由，同一个包的后续微片不用考虑路由，而是根据头微片的相关 路由信息进行投递，消息在流水级上流水地通过网络，报文的接收与路由的决策 可以同时进行。相对于v c t 而言，它对路由器的缓冲需求更小，从而可以构造更 小的快速路由器，但是引起死锁的概率增大。虫孔路由的时空图如图1 4 所示。 链 路 头微片 占用时间 图1 4 虫孔交换时空图 片 采用虫孔路由的网络结构中，在包进行路由交换前，首先把包分成h e a df l i t 、 b o d yf l i t 和t a i lf l i t , 在目的地重新组合成一个包。h e a df l i t 包含了路由的相关信 息，在各个中间交换节点起路由判决、资源预约的作用。 b o d yf l i t 仅包含原分组 4 第一苹绪论 中的数据。h e a d e rf l i t 预约好相关资源后，同一个分组中的b o d yf l i t s 就沿着h e a d e r f l i t 走过的路径，一个接着一个依次传送，类似于一个火车头带着整列火车前进。 t a i lf l i t , 起到释放资源的作用，当t a i lf l i t 到达并传送出去后，相关的通道资源就释 放供其它包用。如果前方的h e a df l i t 在前方的端口遇到堵塞，则后续的相关b o d yf l i t 将就地阻塞。所以不同的消息传输不能交叉或者多路复用一条物理通道。其它消 息必须在一条消息完全通过通道之后，才能够使用这条通道。虫孔路由的基本延 时公式如下： 厂， t = d ( t ，- i - t ，+ t 。) + ma x ( t ，+ t v e t。) i i( 1 2 ) 、 ，tw7jw7ll、 一， 由此可见，在没有竞争的情况下，v c t 和虫孔交换具有相同的时延，一旦头 微片到达目的地，消息流水周期时间由开关和连线迟延中最大的值决定。 1 2 3 疯狂邮差交换 v c t 交换通过流水化消息流提高了报文交换的性能，同时保留了缓冲整个消 息报文的能力。虫孔交换允许小缓冲的v c t ，使路由可以全部在一个单片路由器 内处理，提供了更低的延时，从而为紧耦合并行处理提供了所需的低延时。疯狂 邮差交换机制进一步发展了这种增强消息流水的趋势，试图实现每个节点最小可 能的路由延时。 链 路 占用时间 图1 5 疯狂邮差交换的传输时空图 通过串通道来解释该技术，考虑一个二维网络，消息报文头具有两个微片， 5 电子科技大学硕士学位论文 路由是具有次序的，消息首先全部在第0 维上路由，然后在第1 维上路由，第一 个头微片包含了第0 维的目的节点地址，当消息到达第0 维的目的节点后，再沿 第1 维转发。第二个头微片包含了第1 维的目的地址。在v c t 和虫孔交换中，必 须等到路由器完全接收请求路由的头微片后，微片才可以转发。如果微片为8 位， 第一个头微片通过位串物理通道的传输就占用8 个周期，假定每个中间路由器选 择输出通道花费1 个周期延时，则头经过3 段链路到达目的路由器将花费2 7 个时 钟周期。疯狂邮差交换在位级上进行流水化，试图进一步减少每个节点的延迟。 当头微片开始到达某一路由器时，假定消息还在同一维传输，于是只要接收到头 微片时，马上就向同一维的输出链路转发，同时，头微片的每一位在本地缓冲。 一旦接收到第一个微片的最后一位，路由器就可以检查该微片，判断消息是否应 该继续沿该维传输。如果微片应该从向下一维转发，则消息从头的第二个微片开 始的剩余部分向下一维的输出传输。如果消息已经到达目的地，消息则送往本地 处理器。关键在于，消息首先送往一条输出传输，然后才检查地址，疯狂邮差交 换就是这样命名的。疯狂邮差交换的传输时空图如图1 5 所示。 使用疯狂邮差交换技术进行消息路由的基本延时如下： 1 3 流控机制 t m 口d p 口j ，m 口 = t + t d 4 阳 t = ( f ，+ t 。) d + ma x ( f ，t 。) 缈 ( 1 3 ) t 一。= ma x ( t ，t ，) l 1 3 1 虚通道技术 前面两节介绍了影响并行计算机系统性能的两个方面：拓扑结构和基本的交 换技术。本节将介绍交换结构中资源的一些控制机制【8 】【9 1 。 交换结构的资源主要包括两类：节点上的缓存器和物理链路带宽。在每个物 理通道的输入和输出缓冲器中，通常以f i f o 队列的形式操作，一旦一个消息占 用了两通道的缓冲器，即使消息被阻塞，通道也不能被其它消息访问，这样就降 低了通道的实际利用率。这种情况可以见如图1 - 6 所示，圆形框代表一个节点， 实箭头代表两个节点间的通道，长方形框代表f l i t 缓存，虚箭头代表前进的路由 方向。分组a 在持有缓存4 w ( 节点4 的西侧输入队列) 和6 n ( 节点6 的北侧输 6 第一章绪论 入队列) 的时候被阻塞。由于分组a 占用了缓存3 w ，即使分组b 可以获得所需要 的所有物理通道( 3 w 到4 w ，4 w 到5 w ) 也不能转发。这是由于仅当分组同时 拥有物理通道和对应的缓存才有可能被转发。 分组a 阻塞 图1 - 6 物理通道空闲的时候分组a 后面的分组b 仍被阻塞 5 分组b 的 目的地 为了解决上述问题，于是在物理通道中引入多条逻辑通道或者虚通道【1 0 】来多 路复用该物理通道，每条单向虚通道由一对独立管理的消息缓冲器来实现。如图 1 7 所示每个方向有两个单向虚通道，它们共用一条物理信道。从逻辑上讲，每 条虚通道就是以半速工作的物理通道一样，两条虚通道共享一个物理资源，虚通 道之间的两级调度算法下一节讲详细介绍。 铺【丽i i1 , 一 一一z 一一一一一一 二产f 亏可7 一ll 一! ! l _ jk 一山节点2 口： 、 气 r 眇 l |庸钿棚；甬：曾 虚通道组织方式 缓存 图1 7 虚通道 虚通道可以减低消息的延迟，提高网络吞吐量，在允许多条消息共享一条物 理通道的情况下，消息就可以继续发送而不必阻塞。如果阻塞的分组a 持有一个 与通道q 相关的缓存6 j 。，另外一个缓存6 订仍然允许别的分组超过分组a 。相对图 7 电子科技大学硕士学位论文 1 6 中的网络，图1 8 给出了实现虚通道后的情形。分组a 在持有缓存4 w 0 2 和 缓存6 n 2 被阻塞，因为4 w 1 可用，允许分组b 使用3 w 到4 w 的通道，从而分 组b 可以超过分组a 继续前进。虚通道最初是用做物理环路网络中的一种死锁避 免机制，因此在使用时会有一定的路由限制，而且关于一条物理通道中增加多少 虚通道才使性能达到最佳，有许多这方面的研究【9 】，因为当复用增加的延时超过 减少的阻塞延时时，导致系统的消息延时增加，而且虚通道的增加加大了虚通道 之间的两级调度和工程物理实现的难度，将影响系统的整体性能。 节点6 一 分组b 申请空闲虚通道 图1 8 虚通道提供了额外的缓存以允许分组b 超越被阻塞的分组a 1 3 2 虚通道的工作机制 分组b 的 目的地 5 在使用虚通道流控制技术的网络中，流控制采用两级方式【l o 】【1 1 】进行工作。第 一级是虚通道的分配，这个分配时给予数据包来进行的，所以第一级也叫数据包 级；第二级位节点间的物理链路带宽的分配，这个分配时基于f l i t 级进行的，所 以也叫f l i t 级。当包到达节点时，首先进行第一级操作，根据内部路由算法分配 一个输出通道，这个分配通道在包的生存期内不变，每一个获得虚拟通道分配的 数据包，竞争物理链路的带宽，根据物理链路带宽的分配策略，每个时隙( t i m es l o t ) 传送包的一个微片( f l i t ) 。 图1 9 描述了在物理链路上支持虚通道的框架。图中为两个相邻节点a 和b ， 在采用虚通道技术时，对应物理链路的缓存由简单的f i f o 模式，改为几个独立 的缓存队列，每个队列对应一个虚拟通道。因此文中虚拟通道和节点的输入缓存 或者队列在实际上是同一个概念的不同描述。每个节点上有一个状态寄存器，保 存相邻节点输入缓存的状态，状态信息具体包括输入缓存的分配信息，它用来表 示该缓存是否已经分配，剩余的空间大小多少。 8 第一章绪论 采用虚拟通道技术时具体工作流程如下：节点a 的虚拟通道分配单元为每一 个输入队列的第一个分组分配输出虚拟通道，具体的分配值是根据路由算法和包 的源、目的节点的地址柬确定，没有获得虚拟通道分配的分组等待下一个时隙。 所以获得的虚拟通道分配的分组向物理链路调度单元请求物理链路上的带宽，获 得物理链路带宽分配的分组进行传送发送到下一个节点b 的输入缓存中。由于 采用在节点上保存虚通道状态信息的方法，使得在虚通道的分配时仅需要本地的 信息而无需进行节点间的通信。在两极调度策略中，由于在第一级分配虚通道 需要包古的路由信息，而在采用虫孔路由时只有h e a dn i t 带有路由信息，因此第 一级调度的操作仅对h e a d e r f l i t 起作用，其它f l i t 不需要进行这一级调度而直接 进行第二级物理链路带宽的分配。 图1 9 支持虚通道流控制的逻辑固 14 路由算法的基本要求 在m p p 嘲络中，报文在到达目的节点之前通常需要经过多个中间节点或者 多个开关，中间节点和开关需要一定的缓冲器束存储部分报文或者整个报文。但 是缓冲嚣的容量是有限的，于是存在一些报文占用当前缓冲器，而申请邻接节点 的缓冲器，当这样的情况连接成一个循环申请的时候，就会导致死锁【i “，包含在 死锁配置中的报文将永远被阻塞。有些情况下，某些报文即使没有被永久阻塞， 它们也永远到达不了相应的目的节点，因为报文到达目的节点所请求的通道被其 它报文占用，报文只能围绕目的节点却到达不了目的地，这就是活锁【l ”。如果报 文由于请或的资源总是分配给其它请求同资源的报文，报文也会永久的阻塞， 这种情况称为饿死【1 。死锁，活锁，饿死的出现都是由于资源有限，并且这样的 现象会相互影响，一种情况会导致另外一种情况的出现，所以一个健壮的路由算 电子科技大学硕士学位论文 法，必须解决以上三个问题。 1 4 1 死锁、活锁及饿死 资源的循环申请导致死锁，死锁产生的根本原因就是有限的通道资源内出现 不合理的资源申请。解决死锁有三种策略：死锁预防【1 5 1 、死锁避免16 】和死锁恢复 【1 7 1 。图卜1 0 说明的是在t o r u s 网络中由于环路产生的死锁配置情况。 基于死锁预防的算法在对报文请求的资源分配时就不会导致死锁，要做 到这一点，可以在开始报文传输前保留所有的请求资源，允许回溯的各 种电路交换和p c s 就是这样的情况。在电路交换和p c s 中，源节点发送 一个探测头建立整个路径。一旦路径建立起来，数据微片就在网络中转 发，因为报文开始传输前所有的资源都已保留，所有不会发生死锁，如 果探测头不能前进，允许它回溯并释放某些先前保留的资源。 死锁避免中它的最根本思想便是通过一定的规则来约束缓存资源的使 用，从而使得路由节点内的缓存资源相互之间不产生资源循环申请，并 最终避免死锁的发生。死锁避免机制是路由算法中常采用的处理死锁的 方式，因为基于死锁避免的机制在资源的利用率和性能的最大化达到最 好的折中。本节将主要介绍死锁避免的一些定理。 基于死锁恢复技术的算法通常包括一种机制来检测和分解潜在的死锁情 况，如果检测到死锁，就强制一个或者多个报文释放他们占用的缓冲器 资源，以便其它报文使用，从而打破死锁。死锁恢复技术在死锁发生概 率很小的情况下使用，否则死锁检测和缓冲器释放产生的开销极大地降 低性能。 节点1节点2节点3 节点4节点5节点6 口：x 维正方向上分布的每节点缓存 1 ，2 ，3 - 三不同消息微片 ：每消息占据的链路通道 哼 ：每消息申请的链路通道 图1 1 0t o r u s 网络中的一种死锁配置 l o 第一苹绪论 在介绍死锁避免定理【1 8 】之前，先介绍几个相关概念：通道相关图，路由子函 数。互联网络i 的模型使用具有多