（微电子学与固体电子学专业论文）片上网络的拓扑结构设计和路由算法研究.pdf

摘要 摘要 片上网络的提出，是为了弥补总线通信的不足。由于总线通信时可用于信 息传输的带宽比较的低，并且非常的难以进行再次的扩展。片上网络的提出弥 补了这方面的不足，n o c 的特点是使用了一些比较规则的结构；使得布线简单 同时全局更容易同步；n o c 的优势是使得s o c 的功耗减少；使s o c 的制造费 用降低；s o c 的性能得到了提高；s o c 的上市时间更少同时也使得它的设i - t 风 险得到了降低。 n o c 使用了计算机网络技术以及方法来进行设计，但是汁算机网络中的计 算机是分命在不同的位置，而在n o c 中，所有的资源节点和交换节点都必须局 限在一个芯片上，所以计算机网络中的许多东西在n o c 中并不适用，n o c 具 有以下一些特性。 论文的工作分为以下几点： 1 对片上网络的几个关键技术进行了总结性研究，包括拓扑结构、路山算法、 路由器结构、功耗评估、性能分析等，在这之后，对片上网络的研究仃了更多 的了解和关注，并对每个参数的研究现状进行了分析。 2 对片上网络的拓扑结构进行了探索，并在探索几种经典拓扑结构之后，提 出了两种新的拓扑图，x c m e s h 拓扑和g p 4 拓扑，x c m e s h 拓扑通过增加一 些长的连线，使得网络的延迟时间变小了，网络的通信速度更加快。而g p 4 拓 扑通过增加长连线和在每个路山器上连接4 个i p 模块，不仅使得通信方便，延 迟变短，并且4 个模块内部之间通信变得更加的方便。 3 通过对片上网络拓扑结构的设计，针对不同的拓扑，我们分别对它们设计 了新的路由算法，并在n i r g a m 上做了仿真，确定这两种拓扑可以降低延迟和 增加网络的吞吐量，改善了网络的各方面的能力。 关键字：片上网络，片上系统，拓扑结构，路由算法，n i r g a m 仿真 片j ：网络的| f j 扑结构设计和路由箅0 左研究 a b s t r a c t p u t t i n gf o r w a r dn e t w o r ko nc h i pi si no r d e rt om a k eu pf o rt h ei n a d e q u a c yo f b u s c o m m u n i c a t i o n s i n c et h eb u sc o m m u n i c a t i o no c c u r sc a nb eu s e df o r i n f o r m a t i o nt r a n s m i s s i o nb a n d w i d t hi sl o w , a n dv e r yd if f i c u l tt oo n c ea g a i ne x t e n d n e t w o r ko nc h i pm a k e su pt h i sd e f i c i e n c y , n o ci sc h a r a c t e r i z e db yt h eu s eo fs o m e o ft h em o r er e g u l a rs t r u c t u r e t h es i m p l ew i r i n ga n dg l o b a le a s i e rt os y n c h r o n i z e ； t h ea d v a n t a g eo fn o ci s t h a ts o cp o w e rr e d u c ea n dt h em a n u f a c t u r i n gc o s ti s r e d u c e d ；s o ch a v ei m p r o v e dp r o p e r t i e s ；s o cl i s t e di nl e s st i m ea tt h es a m et i m e a l s om a k e si tt h ed e s i g nr i s kb er e d u c e d n o cu s eo fc o m p u t e rn e t w o r kt e c h n o l o g ya n dt h em e t h o dt oc a r r yo u tt h e d e s i g n ，b u tt h ec o m p u t e rn e t w o r ki sd i s t r i b u t e di nd i f f e r e n tp o s i t i o n s ，i nn o c ，a l l r e s o u r c en o d ea n ds w i t c h i n gn o d e sm u s tb ec o n f i n e dw i t h i nac h i p ，s ot h ec o m p u t e r n e t w o r ko fm a n yt h i n g si nt h en o cd o e sn o ta p p l y , n o ch a v et h ef o l l o w i n g p r o p e r t i e s t h ew o r ko ft h i sp a p e ri sd i v i d e di n t ot h ef o l l o w i n gs e v e r a lp o i n t s ： 1 n e t w o r ko nc h i ps e v e r a lk e yt e c h n o l o g i e sw e r es u m m a r i z e dr e s e a r c h ? i n c l u d i n g t o p o l o g y , r o u t i n ga lg o r i t h m ，r o u t es t r u c t u r e ，p o w e re s t i m a t i o n ，p e r f o r m a n c ea n a ly s i s ， a f t e rt h a t ，t h en e t w o r ko nc h i pr e s e a r c hh a sm a d eag r e a t e ru n d e r s t a n d i n ga n d c o n c e r n ，a n df o re a c hp a r a m e t e rs t u d ys t a t u sa n a l y s i s 2 o nt h et o p o l o g yo ft h en e t w o r ka r ee x p l o r e d ，a n di nt h ee x p l o r a t i o no fs e v e r a l c l a s s i c a lt o p o l o g ys t r u c t u r e ，p u tf o r w a r dt w ok i n d so fn e wt o p o l o g i c a l g r a p h ， x c - m e s ht o p o l o g yt o p o l o g ya n dg p 4x c m e s ht o p o l o g y , b yi n c r e a s i n gt h en u m b e r o f l o n gl i n e s ，m a k i n g t h en e t w o r k d e l a y t i m eb e c o m e s s m a l l ，n e t w o r k c o m m u n i c a t i o ns p e e dm o r eq u i c k l y w h i l et h eg p 4 t o p o l o g yb yt h ea d d i t i o no fl o n g l i n ea n da te a c hr o u t e rt oc o n n e c tu pt o4i pm o d u l e s ，n o to n l ym a k e st h e c o m m u n i c a t i o nc o n v e n i e n t ，d e l a yi s s h o r t e n e d ，a n dt h e4m o d u l eb e t w e e nt h e i n t e m a lc o m m u n i c a t i o nb e c o m e sm o r ec o n v e n i e n t 3 t h en e t w o r kt o p o l o g yd e s i g nf o rd i f f e r e n tt o p o l o g y , w er e s p e c t i v e l yd e s i g n e da a b s t r a c t n e wr o u t i n ga l g o r i t h m ，a n di nn i r g a mt od os i m u l a t i o n ，t od e t e r m i n ew h i c ho ft h e t w oc a nr e d u c et h ed e l a ya n di n c r e a s et h et h r o u g h p u to ft h en e t w o r k ，i m p r o v e n e t w o r kv a r i o u sa s p e c t sa b i l i t y k e y w o r d s ：n e t w o r ko nc h i p ，s y s t e mo nc h i p ，t o p o l o g y , t o u t i n ga l g o r i t h m ， n i r g a ms i m u l a t o r i i i 第一章绪论 第一章绪论 1 1 片上网络的研究背景 伴随着半导体工艺技术的发展，片上系统川( s o cs y s t e mo nc h i p ) 技术也 在不断的发展和完善，如今的s o c 已经可以在片上集成一个或几个处理器、存 储器模块、数模混合电路、模拟电路以及可编程逻辑模块等等的i p 块，把这些 模块用总线连接起来，虽然这些年很多人对片上总线结构进行了改进，但是， s o c 中的i p 核的数量越来越多时，s o c 就面临着很大的挑战，如在延迟、可 靠性、功耗以及性能等方面。为了解决s o c 面临的这些问题，于是人们提出了 片上网络( n o cn e t w o r ko nc h i p ) ，n o c 的特点是使用了一些比较规则的结构， 使得布线简单同时全局更容易同步，n o c 的优势是使得s o c 的功耗减少、s o c 的制造费用降低、s o c 的性能得到了提高、s o c 的上市时f h j 更少，同时也使得 它的设计风险得到了降低。 n o c 是在单一的芯片上集成了许多的存储资源、计算资源和使这些资源之 间进行通信的通信网络，这些通信网络可以实现资源节点的快速通信。 n o c 使用了计算机网络技术以及方法来进行设计，但是计算机网络巾的计 算机是分布在不同的位置，而在n o c 中，所有的资源节点和交换节点都必须局 限在一个芯片上，所以计算机网络中的许多东西在n o c 中并不适用，n o c 具 有以下一些特性： ( 1 ) 节点之间通信的局部性：n o c 的通信具有片上局部性，延迟小并且具有 高的带宽。 ( 2 ) 具有非常多的连线资源：在n o c 中，i p 核之间通信时，仅仅受到连线资 源和开关的束缚，现在的工艺有了很大的进步，使得增加布线层已经比以前降 低了成本，所以，以后的n o c 设计，线密度将不会是n o c 设计最主要的约束。 ( 3 ) 网络缓存的使用：由于连线资源有限，因此在资源节点通信时，会产生竞 争同时也限制了网络的吞吐量，所以需要使用缓存资源，n o c 设计中，面积资 源的开销、功耗开销是很宝贵的，所以在保证带宽性能的基础上，我们尽量使 缓冲区减小。 l ：l q 络的拼；扑 m 勾设计和路由算法研究 n o c 具有以下几个方面的优点： ( 1 ) 使用全局异步与局部同步的时钟策略：它就是把芯片进行划分，使它成为 很多个同步的小的功能单元，每个同步的功能单元都具有自己的工作时钟，同 步单元与同步单元之间使用的通信方式是异步的。 ( 2 ) i p 核的复用：在n o c 2 】设计中，i p 核的复用技术是一个基础，n o c 把一 个系统进行了划分，变成了很多个同步单元，它们之i 白j 相射独立，其中的同步 单元内部基本上使用了我们已经j j 有的i p 模块。 ( 3 ) 具有很好的可扩展性：因为n o c 的每个同步单元之l 、h j 没有直接的联系， 它们之间是通过遵守一个通信协议米协同工作的，所以如果n o c 需要扩展，只 要增加一个已经存在于它们之1 白j 的通信的丌关副本，再设计一个它们之问通信 用的接口，再把该单元集成到n o c 中来完成。山于n o c 中有一个可扩展、可 复用通信机制，所以它的扩展性好于s o c 。 ( 4 ) 通信带宽高：用来衡量n o c 性能的指标很多，其中一个很重要的就是它 的通信带宽，n o c 的通信方式使用的是异步通信，这样有不少的好处，也有一 些的缺点，它的缺点是实时的通信带宽可能不会很高，可是，从平均的通信带 宽来看，只要协议设讨的好，n o c 的通信带宽还是会比s o c 高。 总之，在集成度不断增加、工艺【3 】提高的条件下，n o c 在很多方面都优于 s o c ，如解决扩展性、深亚微米效应、时钟的全局同步问题等。 1 2 片上网络的国内外的研究动态 1 2 1 国外的研究现状 自从n o c 被提出以后，人们对n o c 的研究就一直在进行，使得n o c 这 个研究领域变得越来越热门，近几年，不少的研究机构都丌始进入这个领域进 行研究，也发表了很多好的研究成果。 2 0 0 0 年，法国的p i e r r ee tm a r i ec u r i e 学校的以g u e r r i e r 为代表的人在胖树 ( f a t t r e e ) 结构的基础上提出了一种新的拓扑结构，即s p i n ( s c a l a b l e p r o g r a m m a b l ei n t e g r a t e dn e t w o r k ) ，同时也引进了一种在并行计算机中提出的分 组交换( p a c k e t s w i t c h e d ) 的技术。2 0 0 0 年底，瑞典皇家理工学院的以k t h 为 代表的人也对n o c 领域进行了研究。同时给了n o c 一个定义，也就是在单一 2 第一章绪论 芯片上来实现的，用交换丌关来进行连接的存储资源、i o 资源、处理资源组成 的系统。之后，他与芬兰的v t t 大学一起，展丌了对片上网络基础架构 4 进行 的研究。2 0 0 1 年，b e r k e l e y 大学进行了片上系统的设计方法学，在此基础上， s g r o i 等提出了一种新的思想，即在网络通信基础上的多核系统。同年，斯坦福 大学对网络结构进行了研究，d a l l y 等提出了一种新的连线结构，即在报文 ( p a c k e t ) 基础上的互联。之后，人们对n o c 进行了广泛的研究，研究的范f l j 也变得越来越广泛，包括通信模型、设计方法学、模块之i 日j 的互联结构、拓扑 结构、交换技术、n o c 的功耗等各方面进行了研究。从2 0 0 1 年起，开办了用 来研究n o c 的年会，即i n t e m a t i o n a lf o r u mo n a p p l i c a t i o ns p e c i f i c m u l t i p r o c e s s o rs o c 。2 0 0 5 年，i e e e 举行了关于片上网络的专题，讨沦了一些 问题，关于拓扑结构、相关算法、可重构、可靠性、d 订沿技术等问题。自从2 0 0 7 年，i e e e 举办了专门讨论n o c 的国际会议，即i e e ei n t e r n a t i o n a ls y m p o s i u mo n n e t w o r k so nc h i p ，这些会议的举办都为n o c 的发展提供了更多的机会。表1 1 总结了一些国际上的研究成果。 ”f ：m 络的拓扑结构设计f 路由算： 上研究 表1 1n o c 几年米的研究成果总结 t a b l e1 1t h er e s e a r c ho f n o caf e wy e a r s 科研机构研究成果说明 u n i v e r s i t e s p i n ( s c a l a b l e 通过可扩展的互联网络，綦于f a t p i e r r e e t p r o g r a m m a b l e t r e e 拓扑结构，使用自适应路由策 m a r i ec u r i ei n t e g r a t e d 略，采用冲孔交换方式进行数据交 n e t w o r k ) 换 k t hr o y a l i n s t i t u t eo f t e c h n o l o g y t h eu n i v e r s i t y o fm a n c h e s t e r n o c a r c ( n et w o r k o n c hip a r c h it e c t u r e ) c h a i n ( c h i p a r e a i n t e r c o n n e c t ) u n i v e r s i t yo f b o l o g n a x p i p e s a n ds t a n f o r d u n i v e r s i t y s t a n f o r d + ， netchipun i v e r s i t y 。 k t hr o y a l i n s tit u t eo f 。 m o s t r u m t e c h n o l o g y x $ n o c 架构进行的研究，开 发一种片上网络设计平台，同时对 系统物理层和结构层提供的支持 使用握手信号进行数据交换的自定 时n o c ，采用丫细粒度流水线的链 路，它把发送信廿的交换网络和响 应信廿的交换网络分成两个独立的 嘲络，网络采取_ r 存储转发的包交 换技术和分布式路由策略 一种可综合、性能高0 9 n o c ，通过对 通信节点、通信链路、网络接口的 配置，可以得到任意拓扑结构的 n o c ，采用的虫孔交换技术和确定性 路由算法 研究n o c 设计过程中的自动综合过 程，面向特定应用而进行自动的复 杂设计步骤 基于2 d m e s h 拓扑结构，主要研究n o c 物理层到应用层的通信问题，采用自 适应反射路由策略，避免网络拥察并 且具有一定的容错能力 m i t , m a s s a c h u sn e x tg e n e r a t i o n 研究片上多处理器系统的通讯协议 e t t s ，】 o n c h i p 呙箬：。蓓葛禧翥蓑采：。溉萝运送筘in s t i t u t l e o f ! c o m m u n i c a t i o n倒、。诨禚蓊耗善”7 ”1 ” t e c h n 0 1 0 9 y n e t w o r k ”“1 。” t h eu n i v e r s i t y m a r b l e 以异步共享总线为起点，研究s o c l ， c a r n e g m e l l o u n i v e r s u n i v e r s i m i n i l e s 的建模、q o s 、以及g a l s 等 l i c n e t s；研究目标基于通讯的s o c 设计，并 i 为片上通信体系结构那个形式化分 析方法和优化方法 一- _ _ l 一。 m e s h s t a r i 提 h 了一种m e s h s t a r 混合结构， h y b r i d 可以降低网络热点问题，提高网 a r c h i t e c t u r e 络效率 一一l ， 4 - 第一帝绪论 1 2 2 国内的研究现状 困内有很多的对n o c 进行研究的机构和大学，目d 订，国内的对n o c 进行 的研究主要有以下几个方面，包括路由算法、交换节点设计、性能评估、拓扑 结构设计等各个方面。在拓扑结构方面，由于m e s h l 5 1 和t o r u s 拓扑结构是最基 础最典型的拓扑结构，因此很多的研究都是在此基础上的改进，交换节点、性 能评估、路由算法等主要研究的是m e s h 结构，2 0 0 5 年，周干民博士的学位论 文( ( n o c 基础研究，该论文r 主要研究了i p 核映射、路由算法、n o c 设计方法 学等几个方面。之后，越来越多的人对n o c 进行了研究，表1 2 是一些国家自 然科学基金的项目，归纳如下： 5 卜嗍络的拓扑结构设计和路l | 】算法硼f 究 表1 2 国家自然科学基金资助n o c 项目情况 t a b l e1 2t h en o cf u n d e db yn a t i o n a ln a t u r a ls c i e n c ef o u n d a t i o n 项目名称起始年限 项目承担单位 集成电路n o c 低功耗通信协议栈基础研究 2 0 0 6 - 0 1 至2 0 0 8 - 1 2合肥工业人学 无线通信自重构容错n o c 研究2 0 0 6 0 7 至2 0 0 8 1 2 电子科技人学 高性能片上互联网络及其可测性设计研究2 0 0 6 0 7 至2 0 0 8 1 2 清华大学 低功耗片上网络系统模型及异步互联技术 2 0 0 7 o i = 至2 0 0 9 - 1 2 西安电子科技大学 基于网络编码的m p s o c 共享存储器动态分配技术 2 0 0 8 0 1 至2 0 1 2 1 2西安电子科技大学 s n o c ：片上网络体系结构及设计方法的研究2 0 0 8 0 1 - 至2 0 0 8 1 2哈尔滨工业大学 片上网络系统的拓扑和路由关键问题研究2 0 0 8 0 1 至2 01 2 1 2中山大学 多处理器结构级功耗评估与优化关键技术研究 2 0 0 9 0 1 至2 0 11 1 2 中科院计算所 无线片上网络及设计方法的研究2 0 0 9 0 1 - 举2 0 1 1 1 2 清华大学 基于片上网络的系统芯片测试架构设计与优化研究 2 0 0 9 0 1 至2 0 1 1 - 1 2 深圳先进技术研究所 多核异步数据触发器处理器没计关键技术研究 2 0 0 9 o i 至2 0 1 1 1 2国防科学技术大学 片上网络通信模型g n l s 及动态可重构无缝切换 2 0 0 9 0 l 至2 0 1 1 1 2哈尔滨工业大学 方法的研究 支持高速缓存一致的片上髓络关键技术研究 2 0 0 9 0 1 至2 0 11 1 2清华大学 基于差分c d m a 的高性能片上互联网络关键技术研究2 0 0 9 o l 至2 0 11 1 2 国防科学技术大学 片上网络芯片中路由器电路和互联线的测试方法研究2 0 0 9 o i 至2 0 ll _ 1 2中科院计算所 片上网络商性能互联技术的研究 2 0 0 9 o i 至2 0 1 1 1 2西安电子科技人学 三维片上网络关键技术研究 2 0 0 9 o l 伞2 0 11 1 2 南京大学 1 3 论文的工作和创新 我在读硕士期问，参加了导师的省自然基金项目“可重构片上网络技术研 究”，通过参加这个项目，我查阅了大量的关于片上网络的资料，并对片上网络 的拓扑结构和路由算法进行了大量的研究，在此基础上确定了自己的研究方向， 并通过n i r g a m 仿真器，把新设计的拓扑结构与现有的经典拓扑结构进行了比 较，验证了新的拓扑在很多方面拥有自己的优点，论文的工作分为以下几点： 1 对片上网络的几个关键技术进行了总结性研究，包括拓扑结构、路由算法、 路由器结构、功耗评估、性能分析等，在此基础上，对片上网络的研究有了深 刻的理解，并对每个参数的研究现状进行了分析。 6 第一章绪论 2 对片上网络的拓扑结构进行了研究，并在研究几种经典拓扑结构的基础上， 提出了两种新的拓扑图，x c m e s h 拓扑和g p 4 拓扑，x c m e s h 拓扑通过增加 一些长的连线，使得网络的延迟变小了，网络的通信更加快。而g p 4 拓扑通过 增加长连线和在每个路由器上连接4 个i p 模块，不仅使得通信方便，延迟变短， 并且4 个模块内部之间通信变得更加的方便。 3 通过对片上网络拓扑结构的设计，针对不同的拓扑，我们分别对它们设计 了新的路由算法，并在n i r g a m 上做了仿真，确定这两种拓扑可以降低延迟和 增加网络的吞吐量，改善了网络的性能。 1 4 论文的结构 本文一共分为五章，每章的具体安排如。f ： 第一章：在绪论中首先对文章的背景进行了介绍，说明了提出片上网络的 优辨和解决的问题，接着通过圈内外当日仃对片上网络的最新研究，了解了当自订 片上网络的研究情况。 第二章：介绍了片上网络的儿个关键的技术，包括拓扑结构、路由算法、 路由器结构、功耗评估、性能分析等。通过对它们的研究，知道了片上网络主 要的研究方面和对每一块的研究情况。了解了它们的研究现状，使我们通过对 上面的研究，确定自己的研究方向。 第三章：片上网络仿真器的介绍。 第四章：本章通过对片上网络的拓扑结构和路由算法的研究，提出了自己 设计的拓扑结构和相应的路由算法，并把它们在片上网络仿真器上进行了仿真， 它们与经典的拓扑结构相比，的确使得延时有了降低，并增加了网络的吞吐量， 使得网络的性能得到了改善。 第五章：结论和展望。 7 ”i - b 4 络的拓扑结构设计和路山算法研究 第二章片上网络关键技术的研究 片上网络包括有基础的通信构件、中f n j 件、还有操作系统供给的通信服务， 它还涉及到系统设计方法学和映射规则这些很广的内容。片上网络最主要的任 务是构建一个适用于片上多核系统的、可以让片内资源获得低的通信延迟同时 获得高的性能的通信网络。 n o c 系统包含两个部分：即用来完成计算任务的资源节点和网络系统。资 源：宵点可以是d s p 核、片上存储体、嵌入的处理器核【6 】，还可以是专用逻辑模 块以及s o c 系统等。 网络系统包括了三个部分：交换节点、n i u ( 网络接口单元) 和传输通道。交 换节点的任务是负责资源节点与资源节点中间的通信以及他们之间的数据传 输。资源节点与资源节点之问的双向数据传输通道可以使用点对点的总线方式。 网络接口单元的作用是连接资源节点和传输网络，它的作用就像协议转换器。 由于现在的计算机网络技术在n o c 中并不适用，因此我们需要设计适合 n o c 特征系统，该系统可以提供高带宽、物理实现简单、低延迟等。本章主要 是对目前的n o c 设计中的关键技术进行了介绍，n o c 的研究主要有以下几个 方面，包括拓扑结构、路由算法、路由器结构、功耗评估、性能分析等几个方 面。 2 1 片上网络的拓扑结构 2 1 1n o c 基本结构 一个基础的n o c 拓扑结构需要包括如图所示的几个部分： li p 核：i p 核模块有的是同质的，有的是不同质的。有的是细粒度，也有的 是粗粒度。 2网络适配器：它是i p 核模块与n o c 交换节点模块之间的接口，使得通信 和计算模块之间分离。 3 路由节点：它是通过路由协议来进行通信路径的选择，实现通信路由。 4 链路：它实现了资源节点之问的连接。 8 第二章i j ：嗍络关键技术的研究 图2 1 是一个4 x 4 的2 d - m e s h 拓扑，其中包含了n o c 的基本组成部分，这 个结构图并没有使用总线来进行连接，也没有使用专门的点对点来进行连接， 它使用的就是一种网络拓扑图，只要选用合适的路由算法，便可以使其中的任 意两个资源节点之间实现通信，路由方式可以选择包交换、电路交换【7 】等。也 可以采用同步、异步等逻辑来实现。 黪缓j i i l |。薹 i j 缀 内核 麓i ； j 0 能囊 1 及 。汐秒沙沙 嘲络适配器 oo路由节点 i jj j 。爱 ； j 毫 链路 汐桫诊? 秒 i 篓 j j i 。痧汐秒 4 “ 0 h 一一；f ： ?，j 7 “汐。汐汐“。汐 图2 14 x 4 n o c 拓扑结构 f i g2 1t h e 4 x 4t o p o l o g yo f n o c 2 1 2 常见的n o c 拓扑结构 常见的网络拓扑结构有2 d m e s h 、t o r u sm e s h 、o c t a g o n 、f a t - t r e e 和 s p i d e r g o n 等。 以下介绍了几种片上网络的不同的拓扑结构，得出了一些结论，2 d m e s h 的结构比较简单，延迟方面相对于s p i d e r g o n 和o c t a g o n ，也比较小，并且也很 容易实现的。 1 )2 d m e s h 8 1 是最典型的拓扑结构，它的所有交换节点的集合为 i x o r o 、墨z 彳，艺，x 川y 一。】，x ；艺( f n - 1 ，jem - 1 ) ，其中坐标 f ，】表示交 换节点在拓扑结构中的位置。一个交换节点连接一个资源节点，每个资源节点 有唯一的标识，在这种拓扑结构中，两个交换节点相邻的条件为 i i - k i + i j - 1 i = 1 ，其中x , r j 和x 女兄为两个节点坐标。2 d - m e s h 非边缘交换节点 的节点度是5 ，其中四个是相邻的交换节点和一个连接资源模块，每个边缘交 i i ：网络的拓扑结构设计和路由算法研究 换节点连接四个端口，而交角的交换节点连接三个端f 。2 d m e s h 网络拓扑如 图2 2 ，结构简单，扩展性很好，是同前使用最广泛的结构之一。缺点是网络直 径大，平均距离也大，所以当扩展网络规模以后，它的功耗也比较大，而且中 i u j 交换节点容易捌塞和产生交换“热点”。 圜豳圈 交换节点 t p1 pl pt p 豳圈墨 溺圈囝翻 豳曩囫囫 i pi pi pi p i p 块( 计算单元) 图2 2 4 x 42 dm e s h 拓扑结构 f i g2 2t h et o p o l o g yo f 4 x 42 dm e s h 2 ) t o r u sm e s h 9 1 的优点是在理论上使得整个网络的功耗降低了。它的缺点是 增加的这种长的环形链路会使网络产生额外的延迟。 3 ) b u t t e r f l y ：f a tt r e e 1 0 1 结构是由二叉树的结构变化而来的，在这种结构中， 处在树的叶子部分的是该结构的资源节点，而交换节点则处在了根部，陔结构 的优点是资源节点与资源节点之l 白j 拥有相等的距离，但是，它们中任何链路发 生拥塞或其他的硬件错误时，资源节点之自j 的数据通信就会不畅通。如图2 3 所示： 1 0 第二章片i ：刚络关键技术的研究 一一 b u t t e r f l yf a t _ 。t r e e 图2 3 蝶形胖树结构 f i g2 3b u t t e r f l yf a t - t r e e 4 ) s p i d e r g o n ：该结构的链路数量相对其他几种较少，结构的扩展性是一定的， 节点与节点之间关系对称，适用于资源节点较少的网络。如图2 4 所示： rrr r 图2 4s p i d e r g o n 拓扑结构 f i g2 4t o p o l o g ys t r u c t u r eo fs p i d e r g o n 5 ) o c t a g o n ：在该结构中，节点i ( o f 7 ) 连接相邻的三个交换节点，顺时 针方向，节点f 连接到节点i + 1 ，沿着逆时针方向上，节点i 连接到节点f 一1 ， 沿着对角线方向上，节点i 连接到节点i + 4 ，这个结构的优点是平均距离很短， 在每一个圆环形的网络中，任何两个交换节点如果需要通信的话，只要经过两 跳就可以进行通信了，该结构中，每个交换节点又可以进行扩展，构成一个 o c t a g o n 系统，而且可以一直扩展下去。这样的话布线就比较复杂。如图2 5 所 示： 一 ， 、。、曩 、一 儿i - n 络的拓扑结构设计和路由算法研究 圜 笛曩 ，嗣刁 移“ 应i 譬，彳7豳刃 j 溜| _ 二。穆 2 翻 7 函繁 奄 夕滋气 图2 5o c t a g o n 拓扑结构 f i g2 5t o p o l o g ys t r u c t u r eo fo c t a g o n 2 1 3 常见片上网络的结构属性的比较 片上网络的结构属性直接影响了网络的连接规则，关系着这个网络中各个 资源节点与网络中的交换节点之间是如何连接和分布的，我们选用以下几个参 数来研究片上网络的结构属性：交换节点数、网络直径、交换节点度、链路容 量、平均最短距离。 1 )节点数：它用来说明片上网络中交换节点的数目和资源节点的数目。 2 )网络直径：它代表的是网络中任意两个交换节点之间最短的路由路径的最 大值。它是用来表示网络规模的一个很重要的参数，网络直径影响网络的平均 延迟，基本上成线性的正比。 3 )交换节点度：在拓扑结构中，交换节点度用来代表交换节点与另外的交换 节点和它的资源节点进行通信时，交换数据时所有的输入端口数和输出端口数。 其中的输入输出通道与跟它们相连的输入输出端口相连，节点度大则代表了节 点进行数据传输时可选择的输出端口数比较多，也就是它们进行数据传输时可 以选择的路径比较多，但这样也增加了芯片的面积，同时也增加了设计的复杂 度。 4 ) 链路容量 1 2 】：它表示网络中用来进行数据传输的通道的数目，链路容量大 第一二章 ；：m 络关键技术的研究 则表示该网络可进行的通信的容量也大。 5 )平均最短跳数：它表示网络中两个交换节点之问进行数据通信时，通过最 短路径时所经过的跳数。它只是代表了网络之间的连接特性，但是即使是经过 最短路由跳数进行数据传输，也不表示它是最好的路径选择。这是因为当经过 最短路径进行数据传输时，可能会存在资源竞争、网络j 爿j 塞等现象，这样就会 阻碍数据的传输。 表2 1 给出了一些n o c 网络结构属性的对比，从表中町以看出，b u t t e r f l y 的平均最短路由跳数在几种拓扑图中是最小的，表明它的两个资源节点之问进 行通信时所通过的交换节点的数量是最少的，可是它的网络的容量也是很小的， 所以在该拓扑结构有资源可用时，它也是最容易出现拥塞的。o c t a g o n 拓扑结 构很简单，可是它的平均最短路由跳数却是这几种拓扑中最大的，当两个不同 的环之问需要进行数据传输时，需要经过很多的交换节点转发，使得它的数据 传输是最慢的，所以不适用于高速的通信。 表2 i 资源1 7 点数为n 的片上网络结构属性 t a b l e2 1t h en e t w o r ko fc h i po fs t r u c t i o na t t r i b u t ew h i c hn u m b e ro fr e s o u r c en o d ei sn 2 d m e s ht o r u s m e s h b u t t e r f l y s p i d e r g o no c t a g o n 交换节点数 n n 网络直径 交换节点度 链路容量 平均最短跳数 娟 5 n 8 6 n n n 1n h 44 - 7 3 n - 舸 3 n 2 n 5 n 2 ( n 8 + 1 ) 。2 0 ：瓜 2 - 6 ( 2 n - 1 ) 一 一 表2 2 是对一些典型的片上网络的研究结果的比较，从拓扑、交换模式、 路由算法等几方面进行了总结：在拓扑结构方面，大多数选择2 d m e s h 为网络 拓扑结构，是因为它的可扩展性和它的结构的规整性。从交换节点【1 4 】来看，多 数选择的是虫洞路由模式，因为虫洞路由延迟时间小，使用的缓存数量少。在 路由算法方面，x y d o r 应用的比较多，是因为它可以避免死锁。 表2 2 多核处理器的片上网络拓扑结构、交换方式和路由算法的比较 t a b l e2 2t h et o p o l o g y 、e x c h a n g ew a y sa n dr o u t i n ga l g o r i t h mo fn e t w o r ko n 1 3 m il ：州络的拓扑结构设计和路由算i 上研究 c h i pa b o u tm u l t i p l ep r o c e s s o r 研究机构片上网络名称拓扑类型交换模式路由算法 m 1 1r a m f d n ) 2 d - m e s h ( 3 2 b i t ) 虫洞路由 x y r 算法 t i l e r at i l e 6 4i m e s h2 d - m e s h ( 3 2 b i t ) 流水式电路交换 x vd o r 算法 s o n y , i b m t o s h i m c e l le l b r i n g ( 1 2 8 b i t ) 虫洞路由 s h o r t e s t p a t h 算法 i n t e l t e r a f l o po c n 1 0 x 8t i l em e s h ( 3 2 b i t )虫洞路由 基于源节点算法 l p m cl i p 6s p i n f a t - t r e e ( 3 2 b i t ) 虫洞路由 u p d o w n 算法 i f ta u s t i nt r i p s 2 d - m e s h ( 1 0 9 b i t ) 虫洞路由 x 、d o r 算法 2 2 片上网络的路由算法 n o c 拓扑结构需要使得任意两个资源节点之间可以发送数据到其他的资 源节点，但是当没有一个很完善的拓扑图时，优秀的路由算法决定了两个资源 节点之间通信的路径，即源节点与目标：j j 点之问的通信路径，因此，好的路由 算法是决定n o c 性能的关键凶素。 当我们对路由算法进行分类时，不同的标准分类的结果足不一样的，如有 分析i 式路由( d i s t r i b u t e dr o u t i n g ) 、源路由( s o u r c er o u t i n g ) ，确定性路由 ( d e t e r m i n i s t i cr o u t i n g ) 、自适应路由( a d a p t i v er o u t i n g ) 。 2 2 1 确定性路由 确定性路由算法【”1 是我们经常使用的一种路由算法，确定性路由的路径选 择只与我们路由的源节点和目的节点的地址有关，只要我们知道了源节点和目 标节点的地址，它的路由路径就被唯一的确定了，它与我们当前的网络是否拥 塞无关，我们最常使用的确定性路由就是维序路由( d i m e n s i o no r d e r e dr o u t i n g ) ， 我们常使用它的原因是因为他的路由逻辑非常的简单，并且很容易实现。在这 种路由中，每次我们只需要在一个维度上路由数据包，当我们在这个维度上达 到了目标节点在这个维度上的坐标后，彳在另外的维度上路由，直到达到目标 节点。因为维序路由是单调的按照维数变化来进行路由的，所以这个路由没有 死锁现象。n o c 的最基本的2 d m e s h 拓扑用的就是维序路由，即x y 路由算法， 1 4 第一二帝i ji - n 络关键技术的研究 x y 路山相对简单，路由过程是这样的：数据包先沿着x 方向路由到目标节点 的那列，然后再沿着y 方向路由到目标节点所在的行，这样，源节点的数掘包 便到达了目标节点。 图2 6 表示了x y 路由算法的路由过程，该算法是按照先x 方向再y 方向 进行路由的，首先在x 方向上进行路由判断，先比较x 方向的当日仃节点和目标 节点，如果当前节点比目标节点在x 方向小，那么就应该向东方路由，反过来， 则应该向西方路由，x 方向到达了目标节点所在的列之后，在比较y 方向，当 y 方向也到达了目标节点所在的行之后，源节点便路由到了目标节点。具体的 路由过程可以看下图。 虽然确定性路由算法的路由过程比较简单，当网络的拥塞比较低的时候， 该算法有很多的优越性，但是当网络出现搠塞时，由于它不能根据网络的当前 状态而变化，所以容易拥塞，使得路由的延迟增加，降低了它的性能。 s i a r t d e s x c u r - 一x n o ，7 y e s 一一 、v e s tr o u t e i e a s t r o u t e 2 2 2 自适应路由 d e sx c u rx y e s d e sx - - - - c u r x r e c l v e ，|， 、，ynodes)cup ，。 yy y e s 一一 - ， 一 一、 n o r t hr o u t e s o u t hr o u t e e n a ， 。e n d 】 ie n d ， 一j ， 图2 6x y 路由算法的路由过程 f