（信息与通信工程专业论文）片上网络拓扑结构研究及仿真平台设计.pdf

摘要 摘要 半导体工艺的飞速发展，使得在单块芯片上集成多个处理器核成为了可能。 随着芯片上处理器核数量的增加，传统的总线通信方式逐渐不能满足片上多处理 器之间数据的通信要求。片上网络( n o c ) 技术成为解决复杂多处理器系统中通信瓶 颈问题的重要方法之一，也成为相关领域的前沿和热点研究的内容。 在此研究背景下，本文选取了片上网络拓扑结构及其对应路由算法和片上网 络仿真验证平台这两个方面作为研究方向。深入的探讨了片上网络拓扑及其相关 内容，详细的阐述了片上网络仿真验证平台设计的相关技术，并在此基础上完成 了以下工作： 1 详细的总结了2 dm e s h 、2 dt o m s 以及超立方体这三种经典的片上网络拓 扑结构及其对应的路由算法，并通过仿真对它们在不同通信量模式流量下的网络 性能进行评估。 2 在总结已有的经典n o c 拓扑的基础上，设计并提出了两种全新的n o c 拓 扑：多维平面n o c ，即m d pn o c ：以及色域跳转n o c ，即c d hn o c 。m d pn o c 通过将多维拓扑n o c 的节点标识引入至平面拓扑n o c 中，实现了较好的网络性 能；c d hn o c 将图论中的着色算法引入至n o c 拓扑设计中，提高了n o c 的可 扩展性并节约了资源的消耗。之后通过进行m i ) pn o c 与c d hn o c 仿真，验证 了其相对于几种经典n o c 拓扑在网络性能以及资源消耗上的优势。 3 研究了n o c 仿真平台的设计，包括n o c 节点的模块化设计方法，n o c 拓 扑的生成，以及n o c 网络通信流量的产生机制。并完成了基于s y s t e m c 的n o c 仿真验证平台i n s v p 。并在其上进行了大量的仿真验证工作，证明了n s v p 平台 的可靠性、可扩展性以及便利性。 关键词：片上网络，拓扑结构，网络性能，软件仿真验证平台 a b s t r a c t a b s t r a c t - w i t h r a p i dd e v e l o p m e n to ft e c h n o l o g y , i ti sp o s s i b l et oi n t e g r a t em u l t i p l ec o r e so n o n es i n g l ec h i p a st h en u m b e ro fc o r e so fs y s t e mc h i pi n c r e a s e d ，t r a d i t i o n a ls o c d e s i g n m e t h o d o l o g yw i l ln o tf i to n - c h i pm u l t i c o r ec o m m u n i c a t i o ne n v i r o m e n t a tt h i st i m e n o cb e c o m e st h ek e ys o l u t i o nt oo n c h i pm u l t i c o r ec o m m u n i c a t i o n , a n dr e s e a r c h e s r e l a t e dt on o cs o o nb e c o m e st h ef r o n t i e ra n dh o t s p o to ft h ec o r r e s p o n d i n gf i e l d s o nt h i sr e s e a r c hb a c k g r o u n d ，t h i sp a p e rc h o o s en o ct o p o l o g ya n di t s c o r r e s p o n d i n gr o u t i n ga l g o r i t h m , a n dn o c s i m u l a t i o na n dv e r i f i c a t i o np l a t f o r ma so u r f i e l do fr e s e a r c h i nt h i sp a p e r , w em a i n l yd i s c u s st h en o ct o p o l o g y , a n dt h ed e s i g no f n o cs i m u l a t i o np l a t f o r m t h em a i nr e s u l t sa r ca sf o l l o w ： 1 s u m m a r i z e dt h r e ec l a s s i c a ln o ct o p o l o g yi nd e t a i l ，i n c l u d e dm e s h , t o m sa n d h y p e r c u b en o c a n de v a l u a t e dt h e i rp e r f o r m a n c et h r o u g hc o m p l e t e l ys i m u l a t i o n u n d e rd i f f e r e n tt r a f f i cp a t t e m 2 p r o p o s e dt w on o v e ln o ct o p o l o g y ：t h em u l t i d i m e n s i o np l a n en o c ( m d p n o c ) a n dc o l o r - d o r m a i nh o pn o c ( c d hn o c ) m d pn o c i n t r o d u c e st h en o d e i n d e x i n g o fh i 曲- d i m e n s i o nt o p o l o g yt o2 dp l a n en o c ，b r i n g sh i g h e rn e t w o r k p e r f o r m a n c e ；a n dc d h n o c r e f e r st ot h ec o l o r i n ga l g o r i t h mo fg r a p ht h e o r y , e n h a n c e t h es c a l a b i l i t yo fn o ca n dr e d u c et h er e s o u r c e sc o n s u m e d t h e ne v a l u a t e dt h e i r p e r f o r m a n c ea n dr e s o u r c e sc o n s u m i n gb yc o m p a r i n gt os o m ec l a s s i c a ln o c 3 r e s e a r c h e dt h ed e s i g no fn o cs i m u l a t i o na n dv e r i f i c a t i o np l a t f o r m ，i n c l u d e m o d u l a z i e dn o cn o d es t r u c t u r ed e s i g n , g e n e r a t i o no fn e t w o r kt o p o l o g ya n dn e t w o r k t r a f f i c d e v e l o p e d as y s t e m c b a s e dn o cs i m u l a t i o na n dv e r i f i c a t i o np l a t f o r m n s v eb yi m p l e m e n t i n gp l e n t yo fs i m u l a t i o na n dv e r i f i c a t i o nw o r ko nn s v p , p r o v e d i t sr e l i a b i l i t y , e x p a n d a b i l i t ya n dc o n v e n i e n c e k e y w o r d s ：n o c ，t o p o l o g y , n e t w o r kp e r f o r m a n c e ，s o r w a r es i m u l a t i o na n dv e r i f i c a t i o n p l a t f o r m 图目录 图目录 图2 1n o c 总体结构7 图2 2t o r u s 结构、h y p e r - - c u b e 结构、3 级c l o s 结构、b u t t e r f l y 结构8 图2 34 x 4 的m e s h 片上网络。9 图2 - 44 x 4 的2 dt o r u s 结构一10 图2 5t o m sn o c 中长信道实现方法。1 0 图2 - 6 一个4 维的超立方体1 1 图2 7x y 路由的过程1 2 图2 8x y 路由的选径流程13 图2 - 9t x y 路由算法14 图2 1 0e c u b e 路由过程1 5 图2 1 l 超立方体展开方法1 7 图2 1 28 x 8 的m d p 结构2 0 图2 1 3 不同i p 数量下的z 取值2 4 图2 1 4 不同口数量下的z ”取值2 4 图2 1 5 不同i p 数量下的z ”取值2 5 图2 1 6 不同口数量下的z 取值2 5 图2 1 7 着色算法流程图2 7 图2 18 节点标识算法流程图2 8 图2 19 5x 6c d hn o c 结构2 9 图2 2 0c d h 拓扑生成程序2 9 图3 1 基于o p n e t 平台的n o c 拓扑及节点模型3 3 图3 2n s v p 平台结构3 5 图3 3 直接型网络拓扑结构3 6 图3 - 4x y 路由算法3 7 图3 5t x y 路由算法3 7 图3 - 6n s v p 中实现的一种路由节点结构3 8 图3 7n s v p 平台的界面4 3 图3 8n s v p 的运行过程4 4 图3 - 9 对o r i o n 进行配置4 5 图3 1 0 仿真得到的两个输出文件4 5 图3 1 1 数据包结构4 6 图4 14 x 4m e s h 中不同通信模式下延时性能仿真4 8 图4 24 x 4m e s h 中不同通信模式下吞吐性能仿真4 9 图4 3 均匀通信模式下，虚拟通道对数据包传输延时的影响5 0 图4 - 4m e s h 和t o r u sn o c 在不同通信模式下的延时性能比较5 1 图4 5m e s h 和t o m sn o c 在不同通信模式下的吞吐性能仿真比较5 2 v 图目录 图4 6m e s h 、t o r u s 以及m d pn o c 的平均延时比较5 3 图4 7m e s h 、t o r u s 以及m d pn o c 的归一化吞吐率比较5 3 图4 8m d p 路由节点各个部分功耗5 4 图4 9m e s h 、t o r u s 以及m d pn o c 的总功耗5 4 图4 1 0m e s h 、t o r u s 以及m d p n o c 的面积5 4 图4 1 1m e s h 与c d hn o c 的延时性能对比5 5 图4 1 2m e s h 与c d hn o c 的归一化吞吐率性能对比5 6 图4 1 3c d h 与t o r u s 的延时、吞吐率比较5 6 图4 1 4c d h 与t o r u s 的面积比较5 7 v l 表目录 表目录 表1 1 国外已有n o c 系统总结3 v 缩略词表 英文缩写 s o c n o c i p v c m d p c d h n s v p m i c i f c o c o b o f c r i b 缩略词表 英文全称 s y s t e mo nc h i p n e t w o r ko nc h i p i n t e l l e c t u a lp r o p e r t y v i r t u a lc h a n n e l m u l t i d i m e n s i o np l a n e c o l o rd o m a i nh o p n o cs i m u l a t i o na n dv e r i f i c a t i o n p l a t f o r m i n p u tb u f f e r i n p u tc o n t r o l l e r i n p u tf l o wc o n t r o l l e r o u t p u tc o n t r o l l e r o u t p u tb u 伍玎 o u t p u tf l o wc o n t r o l l e r r o u t i n gi n f o r m a t i o nb i t l i 中文释义 片上系统 片上网络 知识产权 虚拟通道 多维平面 色域跳转 片上网络仿真验证平台 输入缓存 输入控制 输入流控 输出控制 输出缓存 输出流控 路由信息位 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：兰垒l 日期：2 。7 年6 月? 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规 日期：2 驴d 彳年6 月f 日 第一章绪论 1 1 研究背景 第一章绪论 随着半导体的工艺技术和集成水平的高速发展，在单个芯片上集成几十亿个 晶体管即将成为可能【l j 。在单个芯片的集成度和片上系统的复杂程度大大提高的同 时，片上多处理器系统的设计也迎来了更多的挑战。在现有的多处理器系统中， 仍然广泛采用片上总线结构。随着芯片上集成的处理器的数量的增加，采用片上 总线结构的系统其资源复用性、适应性和扩展性等问题，成为了制约集成度提高 的重要因素，甚至会成为制约处理器间通信的瓶颈【2 】。片上网络概念的提出，就 是作为解决此问题的一种途径。由于处理器核的运算能力大大的提高，其运算速 度已经不再是片上多处理器系统发展的主要障碍1 3 j ，各个处理器核之间的频繁数据 交换成为了多处理器系统发展所亟需解决的问题。因此，本文提出研究基于片上 网络的多处理器系统的体系结构，为的是能对多处理器系统的发展做相应的技术 储备。 目前已经有一些机构或公司提出了n o c 的应用实例【4 j f 5 】f 6 】，但是这些实例还 不是真正的n o c 芯片或者系统，多数只是一些带有实验性质的系统。就目前的技 术条件看来，无论是国际还是国内对n o c 所作的研究都是在尽力解决n o c 中的 通信问题，使得当单一芯片的集成度达到可以实现一个真正的片上网络的时候， 不至于由于通信瓶颈而阻碍更复杂芯片的发展。实际上，n o c 的应用必须在芯片 设计水平、工艺级别和i p 复用技术达到一定的程度时才能实现。所以，目前对n o c 的研究还只是一种前瞻性的理论研究，所要解决的主要问题都是围绕如何提高片 上网络中的数据通信性能来提出的，这也是当前国内外n o c 研究的热点和难点。 n o c 中的通信技术研究包含了很多方面，本文主要选取了其中的片上网络拓扑结 构研究与片上网络仿真验证平台设计作为研究方向。 综上所述，本文具有现实的应用意义，其研究的内容属于国际上的相关领域中 的前沿研究和热点内容，能对我国i c 技术的发展起到积极的作用。 电子科技大学硕士学位论文 1 2 国内外研究现状 n o c 是一个崭新的话题，在国际上正处于研究的初级阶段。随着技术的不断 发展，越来越多的研究机构意识到n o c 的潜力，纷纷投入到其中并推动着它的发 展，使得n o c 已经成为一个十分活跃的前沿学术领域。据初步统计，国际上共有 3 0 多所大学、研究所以及工业界等的研究单位正积极从事n o c 研究工作。其中影 响较大的有瑞典皇家技术学院、斯坦福大学和荷兰菲利普研究实验室等。参与研 究的国家还有法国、意大利、芬兰、希腊、以色列、巴西、印度等。 虽然目前n o c 尚处于早期研究的阶段，还没有任何使用n o c 概念研制的真 实s o c 系统，但是存在一些实验性的n o c 系统，包括： 3 e t h e r e a l ：该片上网络系统是i 扫p h i l i p s 的研发小组研制的一款侧重 q o s 保证的片上网络，网络上每个路由节点都可以提供b e ( b e s te f f o r t ) 服务和g s ( g u a r a n t e e ds e r v i c e ) 服务，在o 1 3 微米工艺下，单个路由节点 面积为0 1 7 5 m m 2 ，每个端口带宽可达5 0 0 m h z * 3 2 b i t s = 1 6 g b i t s s 。网络适 配器有四个标准的s o c k e t 接口，分别针对o c p ，a x i 等标准。 n o s t r u m ：由瑞典皇家理工学院研制的n o s t r u m ，重视以目标为导向 的多应用领域在片上网络上的实现。网络通过一种l o o p e dc o n t a i n e r s 的技术 来保证服务。在n o c 设计中，他们提出了t d n ( t e m p o r a l l yd i s j o i n t n e t w o r k s ) 的概念，并基于虚电路来实现网络数据的传输。 s p i n ：s p i n 在片上实现了一个f a t t r e e 拓扑的网络，节点之间用3 2 位宽的 链路相连，包的传输以虫洞的方式进行。在o 1 3 微米的c m o s 工艺下，整 个网络面积为4 6 m m 2 ，端口总带宽达1 0 0 g b i t s s 。s p i n 网络的目标是在总 资源不增加的前提下得到最高的性能，它为非规则网络拓扑的n o c 设计提 供了重要的参考。 c h a i n ：曼彻斯特大学的c h i a n 建立在异步系统设计的基础上。系统中 采用了1 - o f - 4 编码以及b e ( b e s te f f o r t ) 服务等技术，并支持不同位宽的数 据的转换。c h a i n 的目标是异类低功耗n o c ，它为异步n o c 的设计提供 了重要的参考。 m a n g o ：丹麦大学的m a n g o 提供无连接的b e 路由方式以及有连接的 g s 服务，是一种g a l s ( g l o b a l l ya s y n c h r o n o u sl o c a l l ys y n c h r o n o u s ) 类型 的n o c 。在m a n g o 中，路由节点采取了虚拟通道以及异步延时保证技术 2 第一章绪论 来保证g s 服务。该网络也提供与o c p 兼容的网络适配器，是g a l sn o c 中的代表。 x p i p e s ：博洛尼亚大学和斯坦福大学共同研制的x p i p e s 及其附属产品 n e t c h i pc o m p i l e r 是y - - 种经典的n o c 系统【7 】o 该n o c 在路由节点设计中加 入t g o b a c k - n 协议与c r c 校验，在链路层进行纠错，以增加数据的正确 率并降低系统设计难度。 表1 1 对一些基于片上网络理论的复杂多处理器系统进行了统计，从中可以发 现，随着复杂多处理器系统的发展，其网络特点越来越明显，并已经形成了真正 的片上网络结构【8 】。但是各个研究的侧重点都不一样。在这些已有的n o c 系统中， 片上网络的拓扑结构并不复杂，因此，我们希望能够针对更加复杂的片上网络系 统进行体系结构的改进，从而提出新的高性能结构。另外，我们还打算以延时优 化为目标，改进和提高片上网络各个处理器间的互联通信技术网。 表1 - 1 国外已有n o c 系统总结 n o cm o d e l o r g a n i z a t i o nt o p o l o g yy e a r p 1 b u ss i e m e n s b u s1 9 9 4 c h a i n a p t c h a i n2 0 0 2 压t h e r e a l p h i l i p s 2 dm e s h2 0 0 3 s p n 呵 u p m cf a t 曲r e e2 0 0 3 m a n g o d t u i r r e g u l a r 2 0 0 5 n o s i t u mk t h2 dm e s h2 0 0 6 国外的一些研究成果体现出来，n o c 结构在芯片设计和实现中占有了越来越 重要的地位。一些流处理系统、多d s p 系统和复杂s o c 系统采用了片上网络的体系 结构并已经被用到实际应用中。目前国外主要的一些研究机构及其成果包括： 美国普林斯顿的n e cl a b o r a t o r i e s 的j o r gh e n k e l y , w a y n ew o l f z 和 s r i m a tc h a k r a d h a r 等人分析了多处理器系统的基本结构，通信协议和 q o s l o 】。 瑞典斯德哥尔摩的l a b o r a t o r yo f e l e c t r o n i c sa n dc o m p u t e rs y s t e m s ， r o y a li n s t i t u t eo f t e c h n o l o g y 的s h a s h ik u m a r , a x e lj a n t s c h 等人提出了一 电子科技大学硕士学位论文 种具有1 6 个通信资源的多处理器体系结构，并通过研究计算处理器模块 的互联技术，对多处理器领域中的n o c 设计中的时间延迟问题进行了深 入的研列1 1 】【1 2 1 。 美国圣地亚哥的d e p a r t m e n to f e c e 的l a h i r i 等人，主要研究了基于总线的 多处理器通信结构的协议【1 3 j 。 美国s t a n f o r d 大学h o r o w i t z 等人，和在美国u n i v e r s i t yo fc a l i f o r n i as a n d i e g o i 作的d e y 等人对多处理器体系结构中的电线问题进行了分析，对 多c p u 的网络设计和实现进行了研究【1 4 】。 英国汉诺威大学i n s t i t u t eo f m i c r o e l e c t r o n i cs y s t e m s 的m l a d e nb e r e k o v i c 和p e t e rp i r s c h 等人基于n o c 理论提出了一种可升级的分布式多线程d s p 系统f 1 5 】。 加拿大多伦多r y e r s o n 大学的l e vk i r i s c h i a r t , i r i n at e r t e f i a n , p i lw o oc h u n 和i mg e u r k o v 等人研究了一种可重配置的，具有自动恢复和自动加载 功能的并行流处理器【1 6 1 。 丹麦i n f o r m a t i c sa n dm a t h e m a t i c a lm o d e l i n gt e c h n i c a l 大学的j a nm a d s e n , s h a n k a rm a h a d e v a n , k a s h i f v i r k 等人建立了一个基于n o c 的多处理器实 时系统仿真平台，并在该平台上研究了各种不同拓扑结构的网络对多处 理器系统实时性的影响i 1 7 】。 我国一直非常重视与i c 设计相关的技术的发展和研究。实际上，自从s o c 技 术出现以来，国家的科技决策层敏锐地觉察出这是一个跟上国际发展水平的难得 机遇，果断地设立了国家自然科学基金s o c 重大专项、8 6 3 计划s o c 重大专项等 重大项目，使国内的s o c 理论研究基本同步于国际水平。n o c 作为一个崭新的集 成电路设计理论体系正处于初创阶段，国家也尽早立项支持了n o c 相关技术的理 论研究工作，使得我们的n o c 相关技术的研究能够继续保持与国际前沿同步的局 面。从这个层面看，n o c 的出现无疑为中国集成电路设计方法学的继续发展又提 供了一次很好的机遇。并为大量创新成果的出现提供一个空间。目前国内从事n o c 研究的机构和成果包括： 西北工业大学航空微电子中心荆元利，樊晓桠，张盛兵等人，通过片上 网络体系结构的研究，将模块化的测试方法应用到片上网络o s i 网络堆 栈参考模型中，引入了基于片上网络的模块化测试方法。在体系结构方 面，结合可扩展的片上互连网络和隐藏延迟的同时多线程结构，提出网 4 第一章绪论 络互连多线程( n e t w o r k e dm u l t i t h r e a d ，n m t ) 处理器结构。主要是在并 行d s p 处理器系统上进行了应用i 墙j 。 哈尔滨工业大学s o c 研究中心的周文彪、张岩、毛志刚等人，研究了片 上网络的低功耗自适应数据保护方法l l9 j 。提出了片上网络低功耗自适应 数据保护机制，根据不同片上网络通信链路错误数目自适应选择，在路 由节点之间进行数据保护，保证系统芯片功耗最优化。 中国科学院计算技术研究所先进测试技术联合实验室的张垒，王飞等 人，研究了片上网络的设计与测试方法。 合肥工业大学的周干民，高明伦等人研究了n o c 的基础理论，并重点 研究了网络分配问题和嵌入式接口问趔2 0 j 。 湖南嵌入式计算机系统重点实验室的李仁发，李肯立，徐成等人，研究 了片上网络化互连的策略。 由此可见，n o c 及其相关技术的研究在国内外都属于热点研究的内容，目前 已经有一些相关的研究成果问世【2 。但是在国内，详细的、系统的研究n o c 的机 构和个人还不是很多。在已有的一些研究中，各自的侧重点也大相径庭。本文所 做的研究，主要针对的是n o c 的体系结构和其中的处理器间的通信问题，这与国 内现有的研究有一定的区别。 1 3 本文结构和开展的工作 本文主要从n o c 拓扑结构以及n o c 仿真验证平台设计两个方面进行研究。文 章共分为五个章节，其组织如下，第二章主要讨论n o c 的拓扑结构。首先介绍n o c 拓扑的一些基本情况，并总结三种经典的n o c 拓扑结构及对应的路由算法，之后 将详细介绍我们提出的两种新的n o c 拓扑结构m d pn o c 以及c d hn o c 。第三 章详细介绍我们所设计的n o c 仿真验证平台n s v p 。第四章中将给出在n s v p 上 所进行的一些仿真验证，包括对m d pn o c 以及c d hn o c 的一些仿真及结果对比。 第五章总结全文，并提出了进一步的工作展望。 电子科技大学硕士学位论文 第二章n o c 拓扑结构研究 片上网络拓扑结构研究是片上网络研究的一个重要的方向。早期的片上网络 拓扑研究主要是借鉴并行计算中的互联拓扑。在并行计算中，每一个节点对应了 一个处理器核；各个处理器核通过路由器相互连接形成了一个板级的计算网络。 而在片上网络中，网络是芯片级的。由于芯片上资源和面积的限制，原来并行计 算中的拓扑以及对应的路由算法需要进行一些修正以满足现在片上网络的要求。 片上网络拓扑结构研究主要包括了网络拓扑以及路由算法两个方面。网络拓 扑规定了片上网络中各个节点的连接方式；而路由算法表明了在所规定的网络拓 扑中数据包的传递方式。我们以下的研究都将从这两个方面来分别讨论。 本章的组织方式如下：首先在2 1 节中，我们将给出片上网络拓扑结构的一个 简介；然后在之后的2 2 节中将介绍三种经典的片上网络拓扑以及其对应的路由算 法：接着在2 3 节与2 4 节中，我们会在总结三种经典的片上网络拓扑的基础上提 出两种新的片上网络拓扑，详细介绍其提出背景以及构成；在2 5 节中将总结本章。 2 1 n o c 拓扑结构简介 通常，完整的n o c 的体系结构，如图2 1 所示，由若干个n o c 节点，每个 节点上所连接的口核以及各个节点之间的互联组成的。在一般情况中，每个路由 节点又由三个部分组成，包括路由器( r o u t e r ) 、网络接口( n i ) 和与其相连的d 资源( pr e s o u r c e ) 。图2 1 所显示的是一个1 6 个节点n o c 的体架构图。每个路 由器都通过n i 连接着一个资源，并与其它四个相邻的路由器相连。所连接的资源， 即可能是一个处理器核，一块f p g a ，一个a s i c ，也可以是独立的i p 模块【2 2 j 。各 个路由器之间以及路由器与资源之间，是由一对输入和输出单向点对点链路连接。 6 第二章n o c 拓扑结构研究 图2 - 1n o c 总体结构 所谓的n o c 拓扑结构就是指n o c 中各个节点之间的相互连接方式。n o c 的 拓扑在n o c 体系结构中是十分重要的一个部分，它通常决定了片上网络中所采用 的路由方式，仲裁算法以及i p 资源的分布。因此这一部分是我们研究的一个重点 内容。通常n o c 拓扑结构可以分为两大类，一类是直接型网络拓扑，另一类是间 接型网络拓扑【2 3 1 。 2 1 1 直接型网络 在直接网络中，各个网络节点通过直接链路相互互联在一起。常见的直接型 拓扑包括网状拓扑( m e s h ) 、花托拓扑( t o m s ) 以及超立方体结构等。基于目前 的技术水平和应用需求情况，本论文以直接型拓扑结构为主要的研究对象。在2 2 1 中，将详细的介绍本文研究的三种经典直接型拓扑结构：2 dm e s h 结构【2 4 】、2 dt o m s 结构【2 5 】以及超立方体结构。 2 1 2 间接型网络 在间接网络中，节点处理器通过一个( 或更多) 的中间开关节点相互连接。在直 接拓扑中的网络节点是直接相连的，而在间接拓扑中各个处理节点是通过中间节 点相连，这时两者的最大区别。常见间接型拓扑包括蝶形拓扑、b a n y a n 、f a t t r e e 拓扑等。图2 2 所示就是间接型拓扑中的3 级f a t t r e e 、c l o s 和b u t t e r f l y 结构。 7 电子科技大学硕士学位论文 开关节点 口节点处理器 图2 - 2t o r u s 结构、h y p e r - - e u b e 结构、3 级c l o s 结构、b u t t e r f l y 结构 间接型拓扑由于其复杂的网络拓扑以及路由算法，在目前的研究应用中使用 的不多。我们主要以直接型网络拓扑作为我们的研究对像。 在直接型网络拓扑中，研究最多、应用最广泛的是m e s h 拓扑【2 6 1 。此外，t o m s 拓扑以及h y p e r c u b e 拓扑也因为其拓扑的规则性和相对简单的路由算法受到许多 国内外研究机构的重视。在后面的一节中，我们将简单介绍一下这三种经典的拓 扑结构。 2 2 三种经典的直接型拓扑及其路由算法 2 2 1 拓扑研究 2 2 1 1 2 dm e s h 结构 2 dm e s h 结构是一种最简单、最直观的拓扑结构，一个4 x 4 的2 dm e s h 拓扑 n o c 如图2 3 所示。每个节点连接着一个资源和四个相邻的路由器，每个资源通 过一个网络接口( n i ) 连接着一个路由器。其中的资源，可以是一个处理器核， 内存，一个用户自定义硬件模块或者是其他任何可以插入插槽并且可以和网络接 口相配的i p ( i n t e l l e c t u a lp r o p e r t y ) 模块。路由器与路由器之间，路由器与资源之 8 第二章n o c 拓扑结构研究 间是由一对输入和输出通道连接。通道是由两条单向的点对点总线组成。 图2 34 4 的u e s h 片上网络 2 dm e s h 结构是目前在n o c 中研究得最早的一种拓扑结构，它结构简单易于 实现，但是它边节点和顶点节点有相对闭塞性，极大地影响了网络性能。如图所 示，m e s hn o c 有三类不同的节点，项点、边节点和中间点。顶点节点指的是在拓 扑中四个角落的4 个节点，它们只与2 个其他节点相连；边节点指的是四条边上 除点顶点节点剩下的其他节点，它们与周围的3 个节点相连；中间节点指的是拓 扑中中部的所有节点，它们都有4 个直连节点。因此，在设计过程中，就需要对 不同的节点区分对待。在基于2 dm e s h 的n o c 扩展其网络大小时，由于规模变 化，三种节点的数量也不相同，就会为设计和实现带来不便。 2 2 1 22 dt o m s 结构 由于2 dm e s h 结构上存在着上述的缺陷，本文还研究了另外一种更具有优势 的直接型拓扑结构，这就是2 dt o m s 拓扑结构。图2 - 4 所示的是一个4 x 4 的2 dt o m s 花托结构。 9 电子科技大学硕士学位论文 图2 - 44 4 的2 dt o r u s 结构 花托结构可以看成是对2 dm e s h 所存在缺陷的一种自然扩展，即在边界的节 点上增加了一条长的环路，改善了顶点节点和边节点的闭塞性。因此，网络中的 所有节点的度为4 ，对于一个m 1 1 的t o m s 网络，其中m 、1 i 为每个维度上的节 点数，若m - - d _ 则称之为规则的t o m s 。 当将花托型n o c 进行实际布局布线之后我们会发现向对的两条边上的边界点 之间的环路就会成为一条比其他链路长的信道，这样在该链路上的延迟就会比其 他链路大，不能保证线路延时的一致性。所以，我们在设计的t o m s 拓扑结构中， 对这样的长链路信道插入了转发器( r e p e a ：t e r ) ，如图2 5 所示。在加入了转发器之 后，长链路信道被分为了多条断链路，保证了线路上延时的一致。由于转发器没 有仲裁的功能，它仅仅对达到其端口的数据往一个方向转发，所以转发器的存在 就不会对拓扑结构的通信特性造成影响。 世二二些 长信道 ( a 加转发器之前 加转发器打破长信道 ( b ) 加转岌黑插 图2 - 5t o m sn o c 中长信道实现方法 花托拓扑在物理布局形式上与2 dm e s h 相似，但由于其存在很多的环路，所 以在路由算法和路由仲裁方面都要复杂许多。但是2 dt o m s 结构在实际的应用中 范围比2 dm e s h 广很多，其性能也有很大的提高空间，由于2 dt o m s 拓扑的各个 路由节点都是规则的，每个路由节点的结构都一样，所以扩展性也要比2 dm e s h 提高很多。因此，对2 dt o m s 拓扑结构的研究，在今后的多处理器系统的具体应 l o 第二章n o c 拓扑结构研究 用中，有非常重要的意义，我们将在之后的章节对其进行着重研究。 2 2 1 3 超立方体( h y p e r - c u b e ) 结构 超立方体就是在k 元n 维立方体结构中，k - - 2 的时候所得到的拓扑图形。它 的特点是，n 维的立方体，每条边上只有两个节点。这样每一个节点就只需使用一 个n 位的二进制数就可以表示它的坐标了。如图2 - 6 ，就是一个4 维的超立方体。 0 1 1 00 1 1 1 厂、1 】1 0 厂、1 1 1 1 e 掣10 0 1 1 0 1 0 0 k 尺 0 0 0 0 1 0 1 0 1 0 1l八1 1 0 0 1 0 1 1 型掣硇匠爿) l 0 0 1 1 1 0 1 图2 - 6 一个4 维的超立方体 单看它左边的一个立方体，是一个3 维的超立方体。每个方向( 向上、向右， 向里) 是它的一个维。而4 维的超立方体就是在3 维的基础上，增加了到右边的 立方体的一个维。每个节点的坐标为n 3 n 2 n l n 0 ，其中，最低位n 0 表示的是向右的 一维；次低位n 1 表示的是向上的一维；次高位n 2 表示的是向里的一维；最高位 n 3 表示的是从左边一个立方体到右边一个立方体的一维，如图所示。 2 2 2 路由算法 拓扑结构的研究是和路由算法研究不能分开的。在进行拓扑结构研究的同时， 还需要对其对应的路由和仲裁算法进行必要的研究。研究路由算法的主要目的是 在避免死锁和活锁的同时尽可能发挥出在该网络拓扑下的最佳性能口羽。 通常路由算法分为确定路由以及自适应路由两种。如果采用确定路由算法只 要确定了路由的起点和终点，其路由线路就确定下来了。而自适应路由的路由线 路不仅与路由的起点和终点有关，还与网络中的拥塞情况有关。自适应路由考虑 到了线路中实时的情况因此性能较好。但是自适应路由消耗资源巨大，在片上网 络环境中仍然常用的是确定路由算法。在这里我们主要讨论三种经典的确定路由 算法，即2 dm e s h 中的x y 路由，2 dt o m s 中的t x y 路由以及超立方体中的e c u b e 路由算法。 电子科技大学硕士学位论文 2 2 2 12 dm e s h 拓扑中的x y 路由 在目前n o c 的研究中，最广泛研究的是确定型的路由，因为其消耗的资源最 少，这符合n o c 的自身特点【2 9 11 2 7 。在2 dm e s h 中，常采用的是x y 路由这种简 单的维序路由方法。它的路由过程是：先沿x 方向将数据包送至目的节点所在的 列；再沿y 方向将信数据包送至目的地处理器所在的行，如图2 7 所示。 图2 7 ) ( 1 路由的过程 具体的处理流程如图2 - 8 所示。当路由器开始处理一个数据包的时候，因为采 用的是x y 路由，它先判断x 方向上是否到达了目的节点所在的列。如果没到达， 就比较目的x 和当前x ，如果目的x 比当前x 大，则向东路由；如果目的x 比当 前x 小，则向西路由。如果判断出x 方向上已经到达了目的节点所在的列，再比 较目的y 和当前y ，如果相等，说明该数据包已经到达了目的地，则收包。如果 目的y 大于当前y ，则向南方路由：如果目的y 小于当前y ，则应该向北方路由。 1 2 第二章n o c 拓扑结构研究 x y 路由选径过程的流程图 图2 8x y 路由的选径流程 举例来说，一个从( 1 ，2 ) 发出的数据包，其目的地是( 3 ，3 ) ，采用x y 路 由算法的路径是： ( 1 ，2 ) 一 ( 2 ，2 ) 一 ( 3 ，2 ) 一 ( 3 ，3 ) 。 2 2 2 22 dt o r u s 拓扑中的t x y 路由 在t o r u s 中由于每一列以及每一行都存在环路，因此路由方向不再是m e s h 中 的简单的东南西北四个方向，所以传统的禁止转向技术已经不能适用。为了避免 死锁，目前比较常用的方法是通过划分虚拟网络。该方法是将物理信道逻辑上划 分为若干条虚信道，每条信道都有自己独立的缓存。由节点和虚信道组成的网络 称为虚网络p o jp 。数据包按照一定的规则在不同的虚网络中路由以避免死锁。在 多处理器系统中，虚网络的方法在使用上会遇到比较大的困难，增加很多附加的 资源消耗。另外，由于虚网络的划分，节点在仲裁和判断时的开销也会增加，使 路由节点结构更复杂【3 2 1 。因此，为了打破环