（计算机软件与理论专业论文）一种基于片上torus结构的多路径路由方法.pdf

中文摘要 中文摘要 目前，多处理器系统单晶片已经成为高性能芯片领域的研究热点之一，而片 上网络( n o c s ) 技术则是解决多处理器系统单晶片上信息传输问题的一个重要方 法。在n o c s 设计方面，随着半导体尺寸的不断减小和交换速度的不断加快，传 输延迟与串扰噪声已经成为一个制约系统整体性能的严重问题。更宽的线间距 可以减轻线间串扰带来的问题，但是由于有限的片上面积，在工艺和实现复杂 度不变的前提下，更宽的线间距必然导致数据线的减少，以及由此导致的网络 吞吐量降低、传输延迟增加。 针对以上问题，本文提出了一种基于t o m s 结构的路由方法，其中包括多路 最小路由算法( m m r ) 和虚拟通道模型( v c m ) 。在本文提出的虚拟通道模型v c m 上，所有最小路由算法都被证明是无死锁的。所提出的m m r 路由算法将消息拆 分成若干个数据流，并发地经不同最短路径以虫蚀方式到达目的节点，以达到 减轻线间串扰、减少消息传输延迟目的。同时m m r 算法被证明具有单源无阻塞 性质，即在一定情况下可以使同源的数据流同时到达目的节点，以达到优化系 统性能的目的。 通过与一些其他的算法和模型进行比较，可以由理论分析和测试结果得出以 下结论，当网络负载较轻时m m r 路由算法性能优于传统的路由算法，而v c m 也有较好的性能水平。这说明m m r 路由算法和v c m 模型都具有在某些领域实 际应用的潜质和继续研究的价值。 关键词：多路最小路由( m m r ) ，虚拟通道模型( v c m ) ，无死锁，t o m s 网， 单源无阻塞， a b s 仃a c t a b s t r a c t r e c e n t l y , m u l t i p r o c e s s o rs y s t e m o n c h i p ( m p s o c ) h a sb e c o m eah o t s p o ti n l l i 曲p e r f o r m a n c ec h i pa r e a a n dn e t w o r k - o n - c h i p s ( n o e s ) t e c h n o l o g yi so n eo ft h e m o s ti m p o r t a n tm e t h o d st or e s o l v et h ei s s u eo fm e s s a g et r a n s f e ro nm p s o c i nn o c s d e s i g n s ，w i t l lt h ec o n t i n u o u s l ys h r i n k i n gg e o m e t r yo fs e m i c o n d u c t o rd e v i c e sa n dt h e i n c r e a s i n gs w i t c hs p e e d ，t r a n s f e rd e l a ya n dc r o s s t a l kn o i s eh a v eb e c o m eas e r i o u s i s s u ew h i c hl i m i t st h ep e r f o r m a n c eo ft h ew h o l es y s t e m t h i sp r o b l e mc a l lb e m i t i g a t e db yw i d es p a c i n go fs e r i a ll i n e s h o w e v e r , i ft h et e c h n i c sa n dc o m p l e x i t ya r e u n c h a n g e d ，w i d e rs p a c i n go fa d j a c e n tl i n e sw i l lr e d u c et h ed a t al i n e sn u m b e rb e c a u s e o ft h ef i x e dc h i pa r e a , a n dt h u sr e d u c et h et h r o u g h p u ta n di n c r e a s et h et r a n s f e rd e l a y i nt h i sp a p e r , ar o u t i n gm e t h o df o rt o m s - b a s e dn o c sw h i c hi n c l u d e sav i r t u a l c h a n n e lm o d e l ( v c m ) a n dam u l t i p a t hm i n i m a lr o u t i n ga l g o r i t h m ( m m r ) i s p r e s e n t e dt os o l v et h i sp r o b l e m o nt h ev c m ，a l lt h em i n i m a lr o u t i n ga l g o r i t h m sa r e c e r t i f i e dt ob ed e a d l o c k f r e e a n dt h em m r r o u t i n ga l g o r i t h mw i l ls p l i tt h em e s s a g e i n t os e v e r a ld a t as t r e a m s ，a n da l lt h e s ed a t as t r e a m sw i l lb et r a n s f e r r e df r o md i f f e r e n t s h o r t e s tp a t h st ot h ed e s t i n a t i o nn o d ec o n c u r r e n t l yu s i n gw o r m h o l es w i t c h i n g t h e n t h em m r m a ym i t i g a t et h ee r o s s t a l ka n dr e d u c et h ea v e r a g em e s s a g et r a n s f e rd e l a y m m ri sc 2 r t i f i e dt ob en ob l o c k i n gu n d e rs i n g l es o u r c e ，n a m e l yo ng i v e nc o n d i t i o n s ， t h em m rc a r lg u a r a n t e et h a td a t as t r e a m sf r o mt h es a m em e s s a g ew o n tb l o c k e a c h o t h e ra n dr e a c ht h ed e s t i n a t i o nn o d ec o n c u r r e n t l yt oo p t i m i z es y s t e mp e r f o r m a n c e t h r o u g ht h ec o m p a r i s o nb e t w e e nt h ep r o p o s e da l g o r i t h m s m o d e l sa n ds o m e o t h e r s ，t h ef o l l o w i n gc o n c l u s i o n sc a l lb er e a c h e df r o mt h et h e o r e t i c a la n a y l s i sa n d s i m u l a t i o nr e s u l t s t h ep e r f o r m a n c eo fm m ri sm u c hb e t t e rt h a nt r a d i t i o n a lr o u t i n g a l g o r i t h ma n dv c m a l s op e r f o r mw e l l ，w h i c hm e a n st h a tm m ra n dv c mm a yb e a p p l i e di ns o m ef i e l d sa n di t sw o r t ht h ef u r t h e rr e s e a r c h k e yw o r d s ：m u l t i - p a t hm i n i m a lr o u t i n g ( m m r ) ，v i r t u a lc h a n n e lm o d e l ( v c m ) ， d e a d l o c k f r e e ，t o m sn e t w o r k , n ob l o c k i n go ns i n g l es o u r c e i i 目录 图目录 图1 1 线间串扰示意图。2 图1 2i n t e l8 0 核n o c s 原型3 图1 3n o c s 配置设计流程。4 图2 1t o r u s 网络及其节点8 图2 2n o c s 概念性构架9 图2 3 路由单元结构1 0 图2 4 两种类型的传输模型1 2 图2 5 路由协议分类1 4 图2 6 虫蚀交换15 图3 1 虚拟通道组1 8 图3 2v c m 虚拟通道模型一m 砌移廊0 1 9 图3 3v c m 虚拟通道模型- - n e t w o r k1 2 0 图3 4 形成完全模型2 1 图3 5 完全模型中任意节点所具有的加移庸0 虚拟通道2 4 图3 6t o r u s 拓扑下两种死锁模型2 5 目录 图4 1 消息彳路由过程示例3 8 图5 1 消息长度为1 2 0f l i t s 情况下算法比较b n f 图5 5 图5 2 消息长度为6 0f l i t s 情况下算法比较b n f 图5 6 图5 3 模型比较b n f 图5 7 v i i 目录 表目录 表4 1 坐标差值及其对应情况3 2 表4 2 最大可能最短路径数与标志位c 的取值3 3 表4 3x y 维上的优先方向3 5 v i i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：绝锾建 侈口年r 月幻日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：曼栩廷 阳田莎年岁月加日 第一章引言 1 1 1 研究背景 第一章引言 第一节研究背景与现状 随着信息技术的日益普及、数据量的急剧膨胀和所处理问题复杂度的逐渐 提高，许多应用领域对于计算量的需求不断加大。而其中的一些应用方向要求 单一芯片在具有较高的计算能力的同时，也要具备低功耗、低成本等特征，如 在家庭日常的多任务操作中，要求计算机能够在压缩高清视频的同时流畅地支 持大型3 d 游戏系统运行，这就需要计算机在提供较高的计算能力的情况下，保 持功耗处于较低的水平上。 而另一方面，尽管在多年来计算机发展过程中，处理单元的性能几乎始终 遵循着摩尔定律，大约每两年提高一倍 1 】，但是由于诸如晶体硅的晶圆切割工艺 对芯片尺寸的限制【2 】、以硅材料制成的晶体管从本质上存在最薄界限【3 】和芯片能 耗等问题的日益突出，担负计算任务的处理单元遭遇到了频率提升的瓶颈。因 此人们期望在单位芯片处理能力难以继续提升或提升所消耗的代价太大的情况 下，在单一芯片上集成一个由多个处理单元或其他功能模块所组成的网络，以 此来达到提高以芯片为单位的处理器件的计算能力。在此背景下，对于片上网 络( n o c s ，n e t w o r ko nc h i p s ) 【4 】【5 】【6 】及其相关领域的研究成为了解决这一问题、提 高计算机运算速度、推动信息技术继续前进的一个重要研究方向。 但是在v l s i 设计领域，由于半导体器件几何尺寸不断缩小以及交换速度不 断加快，n o c s 的设计对延迟差别、噪声、瞬时错误和其它干扰因素更加敏感 【6 】【8 1 。如图1 1 所示，线路间的串扰作为主要的噪声源之一可能在工艺水平很 高、数据交换频率很快的器件上使并行数据线路间传送的数据产生错误【8 】，从而 影响n o c s 上各节点( 即各种功能模块) 之间数据传送的可靠性和传输效率。作 为解决方法之一，增加片上并行线路之间的距离可以减轻这一问题带来的影响 【8 】，但是对于固定面积的芯片来说，较宽的线间距必将以减少节点之间的线路数 目为代价。而这将减小n o c s 网络上每对相邻节点之间的数据传输线宽，增加消 息传输延迟，降低系统性能。 第1 页 第一章引言 受侵害线 侵害线 s c ：线间电容引起的串扰s i ：线间电感引起的串扰 图1 1 线间串扰示意图 为了改善串扰问题造成的影响，可以利用某些网络拓扑的多可选路径特征， 如t o m s 9 】 1 0 】，使消息从多条路径并行传送。本文提出一种多路最小路由算法 ( m m r ) ，它将根据消息源节点和目的节点的位置关系，在源节点将消息拆分成 多个数据流，并将它们以不同的最短路径并发的传输到目的节点。m m r 算法可 以实现在消息实际传输线宽( 多条传输路径线宽之和) 不变的前提下，减少相 邻节点之间的数据线数目，从而减小线路间的噪声，提升系统性能。或者当保 持相邻节点间数据线路数目不变的前提下，此算法也可通过增加的实际传输线 宽，减少每个消息的平均传输时间，同样可以达到提高系统性能的目的。虽然 m m r 算法将消息拆分成为多个数据流传输增加了网络上阻塞的概率，但是 m m r 算法通过特定的机制保证在单源的情况下( 虽然网络上任何节点在任何时 刻都可以发送消息，但在同一时刻，网络上都只有属于一个消息的数据流在传 输) 数据流之间不会相互阻塞。同时m m r 路由算法具有全自适应性的特点，这 也增加了当网络为多源时数据流路由的灵活性。 1 1 2 领域现状 目前，国际上包括计算机、电子、通讯等多个学科在内的科研技术人员和 公司企业都对n o c s 领域的研究产生了兴趣，这些力量推动了n o c s 相关的理论 研究和产品开发取得了极大的进展。近年来有大量的关于n o c s 的论文和科研成 果通过各种渠道发表出来，其研究内容主要涉及n o c s 的体系结构5 1 、功耗代价 【1 1 1 、芯片设计【1 2 】、q o s ( q u a l i t yo f s e r v i c e ) t 1 3 1 、模拟仿真【1 4 】等几个方面。 第2 页 第一章引言 _ 一1 26 4 mr n h 纛2 ；o m 蠹m - t 1 霜帮 图1 2 t n t d8 0 棱n o c s 原型 在国际上近几年的研究中，一些新的模型、设计方法或布局结构被提案出 来，以降低n o c s 系统整体功耗，达到使n o c s 的功耗水平接近单一助能芯片的 功耗水平的日的，如c r o s s r o a di n t e r c o n n c c t i o na r c h i t e c t u r e 、p a c p ( p o w e r - a w a r e c o r ep l a c e m e n t ) e ”) 、s a p p “】、n o v f i p m 1 ”等。其中值得特别注意的是i n t c l 所发 布的基于“瓷砖片”设计( t i l ed e s i g n ) 的8 0 核n o c s 1 ”，甚至可以将功耗水平 降至当前主流处理器功耗水平之下。与此同时，另一些论文着重于q o s 方面的 研究，如一些对基于m e s h 的n o c s 的研究【1 9 1 、对于实时n o c s 系统的研究 2 0 1 、 毗及其他一些对应用于n o c s 的q o s 结构和设计处理方法的研究。而在体系结 构方面，原有的经典并行机体系结构，如f a t - t r e e 2 j 】、m e s h ：f o r a s ”、c c cc u b 扩2 1 、 d eb r u i j n ”j 等都有被移植于n o c s 系统的可能，而且一些新的关于n o c s 体系结 构方面的成果和论文也不断在近期国际期刊和会议上发表出来 2 4 1 2 5 】口q 。本文所 要讨论的正足在一定的网络拓扑环境下，如何通过设计新的体系结构和与之相 适应的路由算法，来提高n o c s 系统的整体性能。 第3 页 第一章引言 n o c 却幽鲥， d ，口n 0 ，m 图13 n o c s 配置设计流程 由于n o c s 的具有较远的前瞻性和较为现实的应用前景，所以自n o c s 构架 被提出后，包括b o l o g n a 、k a i s t 、k t h 、l i p - 6 、m i t 、u c s d 、m a n c h e s t e r 、 s t a n f o r d 、t c m p e r e 和t e c h n i o n 以及菲利普研究实验室、意法半导体和v r r 技术 研究中心等产业研究实验室都已经在积极发展相关领域的技术。目前已有多个 公司或组织开始将n o c s 理论应用于实际产品，如a r t ss a 公司于2 0 0 5 年推 出了业界第一款商用n o c s 工具套件，图13 所示为其设计流程：s o n i c s 推出了 基于套接字的设计的s o n i c s m x ；2 0 0 7 年2 月的i s s c c 大会上意法半导体、 c e a l e 耵、法国电信研发中心和m i t s u b i t s h i e l e c t r i c i t e - t c l 合作描述了个集 成基带处理构架的f a u s t 芯片，其上模块是通过一个n o c s 进行通讯的鲫：i n t e l 也同样在2 0 0 7 年2 月的i s s c c 大会上发布了一款具有万亿次运算能力的8 0 核 心n o c s 原型( 如图1 2 所示) 。这些产品和概念模型在附和了n o c s 发展方向的 同时也进一步印证了n o c s 的发展潜力，尤其对未来的m p s o c 极具吸引力。但 是依然有很多问题尚未解决，例如选择合适的拓扑、路由选择和流量控制策略、 资料封包消息格式、节点到节点的网络服务类型等。由此可见n o c s 的理论研 第4 第一章引言 究与实际应用已越来越引起领域内的关注，并且其新颖的想法、尚待完善的理 论体系和函待解决的一系列问题都为这一领域的研究提供了良好的发展前景和 机遇。 1 2 1 主要研究工作 第二节主要工作及成果 在对于本课题的研究中，主要涉及两方面的内容：全自适应多路最小路由 算法的提出和无死锁虚拟通道模型的提出。围绕这两方面的主要内容，一些如 仿真模拟、无死锁证明、单源无阻塞证明、传输模型的提出等研究工作也同时 展开。在本文中，对于t o m s 结构的网络拓扑提出了一种虚拟通道模型( v c m ) ， 它被证明是对于任意的最小路由算法都是无死锁的。因为m m r 算法同样是最小 路由算法，所以在此模型上它同样是无死锁的。因此，m m r 算法和v c m 模型 一起构成了一个基于t o m s 网络的路由模型。通过理论上的分析，可以看到所提 出的路由机制与传统的y x 路由算法相比，在单源的情况下，平均消息传输时间 大幅下降。同时通过一些仿真实验，数据显示了在一般状态下( 多源) m m r 算 法相比于y x 算法所具有的优势。 1 2 2 主要研究成果 通过对上述课题内容的研究工作，主要得到了以下研究成果： ( 1 ) 提出t o m s 网络上全自适应多路最小路由算法 2 引，该算法具有全自适应 性，可以利用任意一对通讯节点之间的所有最短路径来进行消息的路 由。而且由于该算法具备同样在本文中提出的“单源无阻塞”特性。 ( 2 ) 提出“单源无阻塞”性质 2 引，具有此性质的多通道路由算法可以在低 负载的网络条件下达到极高的性能。本文中所提出的m m r 路由算法正 是具有此特性的路由算法之一。 ( 3 ) 提出t o r u s 网络上v c m 虚拟通道模型【2 9 1 ，其具有中心对称的特征。在 此虚拟通道模型上，任意最小路由算法均可被证明为无死锁的，而且 v c m 模型对最小路由算法的完全自适应性提供了支持。 第5 页 第一章引言 ( 4 ) 为了分析比较所提出算法和模型的具体性能 2 9 】【3 0 1 ，开发了基于w i n d o w s x p 平台的模拟仿真程序，经模拟运算和理论分析，所提出的路由算法 被证明为具有较高的性能和较好的适用性。 ( 5 ) 提出了两种传输模型 2 8 1 ，即多路全线宽传输模型和多路半线宽传输模 型，以适用于n o c s 设计领域所可能面临的两种不同的情况，并给出了 其性能比较和适用的范围。 第三节本文内容结构 为了便于阐述所提出的路由方法，本文的其余章节将按以下方式进行组织。 本文第二章将介绍一些与t o m s 路由及新的路由算法相关的概念和理论，以 作为在后面的章节中进一步论述路由模型的基础和前期准备；在此之后，论文 第三章将提出v c m 虚通道模型，并详细介绍其组成结构、使用规则和无死锁证 明，作为运行路由算法的载体，它和其后将介绍的m m r 路由算法一起构成了整 个路由模型；有了之前两章的内容铺垫，m m r 路由算法将在文章第四章被提出， 其中包括决策信息组成、路由决策等内容，而且针对m m r 算法单源无阻塞的特 性，论文将给出其证明；在所有理论论述完成之后，文章的第五章将对m m r 算 法与y x 路由算法，以及对v c m 虚通道模型与目前世界上较为先进的卑c h a n n e l s 虚通道模型分别在理论分析和模拟仿真两个方面进行性能比较，并对数据结果 给出和理解释；最后，文章第六部分将对全文做出总结，并给出此课题今后的 前景与研究方向。 第6 页 第二章片上t o m s 路由相关理论与研究 第二章片上t o r u s 路由相关理论与研究 t o m s 网络模型在n o c s 设计领域以及并行机体系结构中都是常见的拓补结 构，这种结构具有可扩展、直径短、平均距离短、以及网格带环网格的良好嵌 入性等诸多优秀特性，这使得t o m s 网络成为片上网络领域重点研究对象之一， 在以往的研究以及文献中已经有许多对于t o m s 网络环境下路由算法、通道模 型、理论性能分析、耐故障特性、模拟仿真等方面问题做了专门的论述和探讨。 本文针对这一网络拓扑结构，提出了一系列的路由算法、虚通道模型和性能分 析比较，以期在n o c s 上采用所提出的路由模型可以在串扰、延迟、吞吐率等方 面达到更好的性能。 在详细阐述基于t o m s 的路由算法和虚通道模型之前，本章对t o m s 网络等 一些在以后的论述中会提到的相关概念和理论给出了具体的定义，以方便后文 的理论论述。此外，本章的第二节提出了两种可能适用n o c s 环境的传输模型， 并对二者的特点和适用性进行了初步的探讨。 第一节t o r u s 网络的概念与特点 在网络拓扑结构的研究中，通常从网络的直径、容错能力和网络中节点的 度等几个方面对某一种拓扑结构进行分析和评价。所以，本节首先对网络拓扑 直径、网络拓扑度等概念予以定义，然后再根据这些定义介绍t o m s 网络的概念 和特性。 定义1 网络拓扑直径 拓扑图中的两个节点之间某条路径的长度指的是此路径上包括的边的数 目；而两个节点之间的距离d 则指的是两个节点之间所有路径中长度最短的路 径所包括的边的数目。由此网络拓扑直径d 可以定义为：某一网络的拓扑图g ， d = m a x ( d x y ) ，栅，y g 。口 第7 页 第二章片上t o m s 路由相关理论与研究 ( a ) t o r u s 网络 y - 图2 1t o m s 网络及其节点 y + ( b ) 网络节点 x + 定义2 网络拓扑度 对于无向拓扑来说，网络中某一节点的度是指连接到该节点的边的数目； 由此网络的度是指此网络的所有节点中拥有最大节点度的节点的度。口 定义3 相邻节点( 或邻居节点) 对于某一网络的拓扑度来说，如果两个节点间的距离d = l ，则称它们相邻， 而这两个节点互为相邻节点( 邻居节点) 。口 根据以上定义，对于二维t o m s 网络可有以下描述。假设在一个双向二维网 络中有七k 个节点，其中k 是任意维度上节点的个数；且其上每个节点x 都由 二维坐标阮力定义，其中0 x ，y k ，那么此网络若满足以下条件则可被称为 t o m s 网络：对于此网络中任意的两个节点x 和y ，它们相邻的充要条件是：存 在石或y 使得x x = ( 即1 ) 后或y 膏= ( y y 1 ) 尼，而对应的y x = y y 或h = x y 。 二维t o m s 网络可以被形象地描绘为如图2 1 ( a ) 所示的网络。它是一种二 维正交网络，由于其具有环绕通道，这就使得其网络模型规整且对称，便于以 硬件来实现高效的简单路由方法【3 1 】。 按照本节前面所述的三个定义，二维t o m s 网络具有以下特点： ( 1 ) 规模为后k 的二维t o m s 网络的拓扑直径为k 。实际上对于行维t o m s 来讲，其网络直径d 可以表达为d = l 咒七2i ，但是本文所讨论的范 围将仅限于二维t o m s 网络。 第8 页 第二章片上t o m s 路由相关理论与研究 图2 2 n o c s 概念性构架 ( 2 ) 对于二维t o m s 网络而言，其网络拓扑度为4 ，且此网络上任意节点的 节点度也均为4 。 ( 3 ) 在t o r u s 网络中，所有节点的相邻节点数目相同，都为4 个。亦即如图 2 1m ) 中所示的四个方向都存在邻居节点。 以上为二维t o m s 网络的一些基本特性。 在基于t o m s 的n o c s 网络中，每个节点都由一个逻辑模块、一系列的存储 单元和一个将节点连接到内部互联网的路由单元组成，如图2 2 所示。其中每 个路由单元内部具有相应的虚拟通道缓存、仲裁机构和c r o s s b a r 以供网络上消 息的路由，如图2 3 所示，而路由模块也是本文主要涉及到的部分。为了便于直 观表达，在本文中所有的节点都将在图中表达为一个矩形，并且一个基于t o m s 规模为2 n x 2 n 的n o c s 网络将被表达为一个2 n x 2 n 矩阵( 是t o m s 网半径) 。 第9 页 第二章片上t o r u s 路由相关理论与研究 x + v c v c c r o s s b a r k o u t m g 茂 a r b i t r a t i o n v c v c 图2 3 路由单元结构 七 位于t o m s 网络上的每个节点在本文中都将以一对分别代表x 维和】，维的坐 标仅，) ，) 来标识，其中0 x ，y 2 n 一1 。通过将每个节点的坐标值作运算y x1 0 t + x ( 其中t 为x 的位数) 可以得到一个节点号，这个节点号便于以单维的顺序来表 示网络上的节点。t o r u s 网络上的每个节点都由4 条物理链路，分别连接与其相 邻的4 个邻居节点。图2 1 ( b ) 说明了4 条物理链接的方向及其表示方法，在本文 后面的内容中将用到这种方向表示方法来进行理论阐述。 第二节片上传输模型 如前所述，由于半导体器件几何尺寸不断缩小以及交换速度不断加快，n o c s 的设计变得对噪声干扰因素更加敏感【8 】。线路间的串扰作为主要的噪声源之一可 能在深亚微米水平以上等级的器件上使并行数据线路间传送的数据产生错误， 从而影响n o c s 上各节点之间数据传送的可靠性和效率。虽然理论上可以通过增 加片上并行线路之间的距离来减轻这一串扰噪声所带来的影响1 8 j ，但是在芯片面 积一定的前提下，加宽线间距势必将减少节点之间的线路数目、减小数据传输 线宽、增加消息传输延迟、降低系统性能。 第l o 页 第二章片上t o m s 路由相关理论与研究 但是，通过将一个消息拆分成多个数据包，使其在网络上并发传输的方法， 可以使系统达到在消息传输延迟和平均消息传输实际带宽基本不变的前提下， 将节点间并行数据线路减半、线间距加倍，以达到大幅降低线间串扰的效果， 并且可以使系统获得由此带来的数据传输高有效性、高可靠性、低误码重传率 等相对于线间距较小情况下的优势。此模型相对于传统的全线宽下单路传输模 型成立的判断是建立在加倍的线间距可以带来更高的数据有效性、更低的数据 重传率以及为提高数据传输频率提供可能性，并且这些优势足以抵消甚至超过 数据线宽减半带来的不良影响的预期效果上的。 另一方面，如果较宽的线间距带来的正面效果不足以抵消其负面效果，或 者说在数据线宽不变的前提下，使系统同样采用多路传输机制可以达到或超过 半线宽情况下的性能，则全线宽的数据传输模型仍然具有其实际意义。 2 2 1 多路全线宽传输模型 全线宽传输模型( 简称为f m ，f u l l w i r e - b a n km u l t i p a t ht r a n s p o r tm o d e l ) 是 基础的传输模型，或者说是作为讨论基准的参照系，其并行数据线间距为d 。只 有预先规定了这样的一个传输模型，讨论半线宽的情况才具有意义。在f m 上， 任意数据流在节点之间传输时，都是利用链路的全部线宽进行传输，如图2 4 ( a ) 所示( 以4 条线为例，图中0 1 节点作为消息源节点，2 2 节点作为消息目的节点， 带有方向的粗线表示用来进行消息传输的数据线和传输方向) 。其优点为充分利 用了所有线宽，相邻节点间带宽较大，但是其缺点同样明显：线间串扰严重。 2 2 2 多路半线宽传输模型 半线宽传输模型( 简称为h m ，h a l f - w i r e b a n km u l t i p a t ht r a n s p o r tm o d e l ) 相对于f m 而言，其并行数据线间距为d 2 ，任意数据流在传输时都只利用节点 之间f m 情况下线宽的一半进行传输，即利用所有数据线中的半进行传输。传 输时，利用编号为奇数全部线路进行传输或者编号为偶数线路传输，以此减轻 线间串扰的影响并增加网络的耐故障性1 32 1 ，如图2 4 ( b ) 所示( 以4 条线为例， 图中0 1 节点作为消息源节点，2 2 节点作为消息目的节点，带有方向的粗线表示 了用来进行消息传输的数据线和传输方向) 。其优缺点恰与f m 模型相反：它的 线间串扰程度较小且有一定的耐故障性，但未能充分利用节点间的线宽。 第1 1 页 第二章片上t o m s 路由相关理论与研究 ( a ) f m m o d e l 图2 4 两种类型的传输模型 2 2 3 两种传输模型间相对于同种算法的比较 ( b ) h m m o d e l 当脱离开算法的层面，仅就两种模型的性能进行讨论时，不妨假设同种路 由算法运行于两种传输模型之上。因缺乏相应的实际产品的性能数据统计，这 里仅能就宏观理论性能得到以下简要结论。 当h m 模型在降低线间串扰、并由此而增加数据传输效率、更大程度地提 高线上数据传输时钟频率等正面效果和降低数据传输线宽等负面影响的共同作 用下，其实际性能大于f m 模型时，h m 模型更为适用。 当f m 模型在高数据传输线宽等正面效果和高串扰、低有效、数据传输时钟 频率不变的负面影响的共同作用下，其实际性能大于h m 时，f m 模型更为适用。 另外，当f m 模型在高数据传输线宽、提高线上数据传输时钟频率等的正面效果 和由于提高时钟频率而导致的更高的串扰的负面影响下，其实际性能大于h m 时，f m 模型更为适用。 为了方便分析比较在m m r 算法下，增加消息传输的平均线宽与减少网络上 并行线路间的串扰这两种方式哪一种更能提高系统的总体性能，本文在此提出 了两种传输模型。由于这两种模型只是在线宽的利用率上和缓存大小上存在不 同，而在路由的选择和传输的控制等方面都相同，所以在第三、四节中将不再 对二者做特别区分，只是在第五章对二者进行性能分析比较。 第1 2 页 第二章片上t o r u s 路由相关理论与研究 2 3 1 路由相关理论 第三节相关概念与理论 在介绍具体的路由算法之前，有必要先对路由算法的分类和它可能具有的 性质进行一下大体的介绍。目前n o c s 上针对各种拓扑结构的路由算法大多是由 并行计算机体系结构方面的路由算法直接引用而来或稍加改动演变而来，因此 其路由算法大致可从如下几个方面进行分类【”】( 更具体的分类如图2 5 所示) 。 ( 1 ) 路由算法可以首先按目的地的数量进行分类。消息可以只有一个目的 地( 单播路由) ；也可以有多个目的地( 多播路由) 。 ( 2 ) 路由算法还可以根据路由决策地点进行分类。原则上，路径可以由源 节点的集中式控制器在消息注入网络之前决定( 集中式路由) ；也可以 当消息在网络中传播时以分布式的方式来决定( 分布式路由) 。 ( 3 ) 路由算法也可以根据它们所选择路径是否必须为最短分为最小路由算 法和非最小路由算法。 ( 4 ) 路由算法既可以是确定性的，也可以是自适应的。确定性路由算法是 指在给定源目的节点之间总是提供相同的路径；自适应路由算法则使 用关于网络流量和或通道状态的信息来避免阻塞或网络中的故障区。 特别要说明的是自适应路由算法还可以根据可选择的路径数进一步分为完 全自适应路由算法和部分自适应路由算法。全自适应路由算法可以利用它的集 合中的所有的物理通道；而部分自适应路由算法只能使用它们路径集合中的一 个子集。应该指出，对于完全自适应路由算法来说，尽管所有的物理路径都是 可用的，但是一个给定的路由算法为了避免死锁可能会限制对虚拟通道的使用。 在本文中提出的m m r 路由算法依据分类，可以定性为单播分布式无死锁多 路完全自适应最小路由算法。其中无死锁和多路两个概念并没有在算法分类中 被提及。其中死锁的概念是一个路由算法所必须克服的，但是它可以实现为死 锁避免，也可以实现为死锁恢复两种解决方式。本文所提出的算法依靠死锁避 免来解决死锁问题，因此可以称之为无死锁的，这将在第三章予以证明。而多 路路由则是m m r 路由算法的特性之一，它是针对传统的单路路由而提出的一个 概念，在此概念之下，一个被成为单源无阻塞的重要性质被提出，且在第四章 予以证明。 第1 3 页 第二章片上t o r u s 路由相关理论与研究 跆田舁瑟 ， 目的数单播路由多播路由 一一1 、- - 苦由决策 集中式路由 源路由 分布式路由多阶段路由 实现查表有限状态机 ，c 闰， 适应性- - 确定性路由自适应路由 顺序性一i d 前进型回溯型 ，p 习 路径数完全自适应部分自适应 图2 5 路南协议分娄 2 3 2 交换相关理论 目前，一些常见的交换机制包括存储转发( s 蛆s t o r ea n df o r w a r d ) 交换、虫 蚀交换 3 3 】 3 4 】 3 5 】、虚跨步( v e t , v i r t u a lc u tt h r o u g h ) t 3 6 1 交换等。s a f 要求报文在向 下一个节点转发之前完全缓冲在每个中间节点中，这就要求了较大的缓冲资源， 不适于在面积和资源极为有限的片上网络实现。v c t 虽然不要求消息在路由单 元完整接受报文前将消息在当前节点缓冲，而是允许消息直接跨步到下一个节 点的输入上以实现流水传输，但它要求当消息阻塞时缓冲器能够容纳整个消息 在当前节点缓冲，即它对于缓冲资源的需求等同于s a f ，同样不适于n o c s 实现。 本文所采用的虫蚀交换则将消息分割成微片( f l i t ) ，使消息在微片级上流水地 通过网络，它只要求能够储存几个微片的缓存，对于资源的需求很低，便于在 n o c s 上实现。因此本文所讨论的路由方法的一个潜在基础就是采用虫蚀方式。 图2 6 表现了消息以虫蚀的方式进行传输的情况，但图中也显示出一个问题：消 息以虫蚀方式传输时需占用从源节点到当前节点的一系列缓存而容易引起阻 塞。本文第四章提出的m m r 算法正是在某种程度上试图解决这一问题。 第1 4 页 第二章片上t o m s 路由相关理论与研究 2 33 相关定义 口 哗。 # 女m m m ”删m h 口m t ，s a g 。b m # m h 口 十月h # 图2 6 虫蚀交换 为了简单高效地描述本文所提出的路由算法和虚拟通道模型，现对一个2 n x 2 n 规模的t o m s 网络做以下定义。 定义4 边界节点 对于网络中的任意节点，如果在它的坐标( z ，) 中任意一个坐标的值为0 或2 n - 1 ，则称此节点为边界节点。口 定义5 越界 对于任意数据流，如果它从一个x 或y 坐标为0 ( 或2 n - 1 ) 的边界节点发送 到另一个相应的x 或y 坐标为2 n - i ( 或o ) 的边界节点，则称此数据流越界。口 定义6 到达边界 对于任意数据流，如果它从一个t ( 或力坐标不为0 ( 或不为2 n - 1 ) 的节点 发送到另一个对应的，( 或计坐标为0 ( 或2 n - 1 ) 的节点则称此数据流到达边 界。口 定义7 优先方向 对于任意数据流假设它处于当前节点无阻塞情况下如果它在多个输出 第1 5 页 第二章片上t o r u s 路由相关理论与研究 方向上都有最短路径，则根据路由算法所优先选择的输出方向被称为此数据流 在此时的优先方向。在数据流的源节点，其所发出的方向即被称为优先方向。 口 定义8 优先维度 对于任意数据流，假设它处于当前节点无阻塞情况下，如果它在两个维度 上均有最短路径，则根据路由算法所优先选择的维度被称为此数据流在此时的 优先维度。在数据流的源节点，其优先方向所在的维度被称为此数据流在此时 的优先维度。口 以上是一些与文章主体内容相关的概念定义，在后面的章节中，很多理论、 定理、证明、阐述将直接引用这些概念，而不再另外进行解释。尤其是本文的 核心内容m m r 路由算法，其一些关键技术是基于以上的定义或限制而提出的， 这些理论将在第四章予以讨论。 第四节本章小结 本章主要对一些涉及到基于t o m s 拓扑上n o c s 路由的相关理论与概念进行 了简要的介绍和分析，以便于在后面的文章中更为准确详细地表达m m r 路由算 法和v c m 虚拟通道模型。其中包括关于t o m s 网络及其上节点的一些定义；路 由算法的各种性质和分类，以及本文所提出的路由算法所具备的性质；针对于 所提出算法和模型的一些具体概念的定义。此外，本章还介绍了两种在第五章 进行具体分析的模型。这两种模型可能会在不同的实际情况下适用于不同的应 用环境，并对系统性能产生一定程度的影响。 总体来说，本章作为随后章节的铺垫，为详细的理论阐述准备了一些预备 知识，并在一定程度上简化了算法和模型的描述难度。 第1 6 页 第三章v c m 虚拟通道模型 第三章v c m 虚拟通道模型 虚拟通道作为一种逻辑通道，通常以物理通道两端的多组缓冲器的形式予 以实现，来起到复用物理通道的作用【3 丌。所有由某物理通道两端的相邻节点 上对应于此物理通道的缓冲器所构成的虚拟通道共享此物理通道。最初引入虚 拟通道的目的是为了解决虫蚀交换中的死锁问题，但是经研究发现，虚拟通道 也可以用来减少网络阻塞、降低消息延迟、提高网络吞吐量。既然允许多个虚 拟通道共享一个物理通道，则当某一消息因阻塞在网络中而占用某一段虚拟通 道时，其所从属的物理通道不会因此而被标记为占用，其它消息可通过同属于 此物理通道的其他虚拟通道来继续传输，以达到优化使用物理通道资源的目的。 正因为虫蚀交换方式与虚拟通道技术在并行