（微电子学与固体电子学专业论文）片上网络路由节点的设计及性能分析.pdf

上海大学硕士学位论文 摘要 技术的飞速发展把芯片设计带入了十亿级晶体管的领域，这意味着单个芯 片中可集成更多的m 核。而随着芯片中口核的增多，以片上总线为通讯方式 的片上系统( s o c ) 设计方法将不再满足设计要求。这时，片上网络( n e t w o r k o nc h i p ，n o c ) 作为一种新的解决途径被提出来了。片上网络的可升级性 ( s c a l a b l e ) 和易扩展性很好地满足了新设计的要求。片上网络逐渐发展成为片 上总线之外的一种新的通信结构。总的来说，片上网络的复杂程度( c o m p l e x i t y ) 是由三方面的因素所表征，也即网络拓扑结构、路由算法以及交换技术。而这 一切将体现在片上路由节点中，本文正是围绕着片上路由节点的设计做了以下 工作： ( 1 ) 阐述了片上网络设计中所要考虑的各方面，对各种不同应用的策略进 行了分析比较，得出适合片上网络设计的方案，规划出本文的设计方向。 ( 2 ) 设计并实现2 级流水线的基于2 dm e s h 拓扑结构、x y 维序路由机制 的虚拟通道路由节点。在讨论分析拓扑结构、路由技术，流控机制的基础上， 构建了设计架构，阐述了设计细节。 ( 3 ) 搭建了一个用于网络验证的测试平台。n o c 是一个弹性的、可延展 性的芯片微网络，网络的吞吐率和延迟是两个主要性能指标。在分析片上网络 的特点的基础上，搭建了网络性能测试的平台，用此平台对本文设计的路由节 点进行了验证及性能分析。 通过验证，得出本文所设计路由功能设计的正确性。同时搭建一个针对有 本文所设计的路由节点组成的片上网络的验证平台，通过此平台，验证了网络 的稳定性以及描述出所设计片上网络的性能特点曲线。本文的工作虽然还不全 面，但为后续的诸如片上网络的资源及功耗分析，以及设计更复杂的功能( 如 q o s ( q u a l i t yo fs e r v i c e ) 和容错) 做了些前期准备和探索，为后续的研究打下了 坚实的基础。 关键词：片上网络，拓扑结构，路由节点，网络验证 v 上海大学硕j ：学位论文 a b s t r a c t r a p i dd e v e l o p m e n to ft e c h n o l o g yb r i n g sc h i pd e s i g ni n t ob i l l i o n - t r a n s i s t o re r a i ti sp r e d i c t e dt h a ta tt h ee n do ft h i sd e c a d e ，i tw i l la l l o wm o r et h a no n eb i l l i o no f t r a n s i s t o ri n t e g r a t e do nas 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 p i n c r e a s e d ，t r a d i t i o n a ls o cd e s i g nm e t h o d o l o g yw i l ln o tf i tt h eb i l l i o n t r a n s i s t o rf i e l d d e s i g nr e q u i r e m e n t a tt h i st i m en o c ，a san e ws o l u t i o n ，i sp r e s e n t e d t h es c a l a b l e a b i l i t yo fn o c w e l lm e e t st h ec h a l l e n g eo fn e w d e s i g nr e q u i r e m e n t 。n o cg r a d u a l l y b e c o m e san e wc o m m u n i c a t i o ns t r u c t u r eb e s i d e st r a d i t i o n a lo n - c h i pb u s i ng e n e r a l ， t h ec o m p l e x i t yo fn o ci sc h a r a c t e r i z e db yt h r e em a i nf a c t o r s ，t h en e t w o r kt o p o l o g y , r o u t i n ga l g o r i t h ma n ds w i t c ht e c h n i q u e a l lo ft h e s ef a c t o r sw i l ld e t e r m i n et h e d e s i g no fr o u t e ra r c h i t e c t u r ef o rn o c ，a n dt h et h e s i sf o c u s e so nt h ed e s i g no fr o u t e r w i t ht h ef o l l o w i n gw o r k 1 ) d i s c u s sa n da n a l y z et h ev a r i o u st e c h n i q u e ss u c ha st o p o l o g y , r o u t i n g ， s w i t c h i n gt h a tn e e d e db yn o c ，a n da d o p tt h es u i t a b l et h e m ef o rn o c 2 ) b a s e do nt h ea n a l y s i so ft h er o u t e rw o r kf l o w , t h et h e s i sd e s i g na n d i m p l e m e n tar o u t e rw i t h2 - s t a g ep i p e l i n et oi m p r o v et h ep e r f o r m a n c ea n dd e c r e a s e t h el a t e n c y 3 ) a f t e rv e r i f yt h ed e s i g no fr o u t e r , s e tu pat e s t b e n c hf o rt h en o cw h i c hi s c o m p o s e do ft h er o u t e rw ed e s i g n e ds oa st oa c h i e v et h ep e r f o r m a n c em a t r i c e so f n o c t h r o u g ht h er e s u l t so ft h ev e r i f i c a t i o na n ds i m u l a t i o n ，w ec a l lk n o wt h a tt h e d e s i g no fr o u t e ri sr i g h ta n dp r a c t i c a l t h ew o r ki nt h et h e s i si sn o tp e r f e c tw i t h o u t c o n s i d e r i n gt h ep o w e r a n da r e ao f n o c ，b u tt h et h e s i sp a v eap a t hf o rt h ef u t u r ew o r k s u c ha sd e s i g no fq o sa n df a u l t - t o l e r a n t k e y w o r d s ：n e t w o r ko nc h i p ，t o p o l o g y , r o u t e ra r c h i t e c t u r e ，n e t w o r kv e r i f i c a t i o n v l 上海大学硕：七学位论文 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：啤日期：当业矽 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) n 日期：2 1 竺! ：兰：7 上海人学硕士学位论文 1 1 引言 第一章绪论 随着半导体器件制造工艺的发展，可以集成到单个芯片上的晶体管的数目 与日俱增。技术的进步为在单一芯片上集成系统铺平了道路。s o c ( s y s t e m o n c h i p ) 正是在这种背景下产生的，由于s o c 可以充分利用已有的设 计积累，显著地提高a s i c 的设计能力，因此发展非常迅速，引起了工业界和 学术界的关注。 但是，随着深亚微米超大规模集成电路工艺技术的成熟及进一步发展，芯 片设计业面临着严峻的问题：随着对芯片功能和性能的需求不断增加，芯片规 模越来越大，工作速度越来越高，开发周期越来越长，设计质量越来越难于控 制，设计成本也越来越高。根据预测，半导体器件的特征尺寸在2 0 1 5 年左右将 达到2 2 纳米，时钟频率将达到1 0 g h z 以上【1 1 。这些要求使得以总线结构为主 要特征的s o c 设计方法越来越难以满足要求【2 1 ，面临了一些不能忽视的问题： 1 ) 可扩展性问题 随着电路规模越来越大，片上集成的单元越来越多，数据处理量也越来越 大，总线结构的可扩展性差的问题就越来越突出：虽然总线可以有效地连接多 个通讯方，但地址资源总是有限的。有限的地址资源将成为扩大电路规模的瓶 颈。另外，虽说总线由多用户共享，但一条总线无法支持两个以上用户同时通 讯，传统总线结构的时间资源利用率很低。另外，为了解决s o c 复杂性日益提 高的问题，传统的片上总线架构必须不断改进。这意味每个口模块的总线接口 必须经常修改，而这会造成新的s o c 解决方案上市时间延长。 2 ) 互连延迟问题 尽管深亚微米技术提高了金属层的数量，但是典型金属连线的阻容延时也 跟随制造工艺而提高。因为阻容延时、芯片工作频率、裸片大小和普通互连线 的共同影响，s o c 延时、功率和面积等各项要求中对片上总线的影响最大。随 着特征尺寸下降，连线延迟成为影响信号延迟的主要因素。因总线结构是全局 上海大学硕士学位论文 控制的，而在1 0 亿晶体管时代，全局的线延迟会大于时钟周期，甚至达到6 到 1 0 个周期【3 1 。进而，总线结构的全局连线使得时钟的偏移很难管理。 3 ) 单一时钟同步问题 总线结构要求全局同步，但是随着工艺特征尺寸越来越小，工作频率迅速 上升，达到1 0 g h z 以后，互连线延时造成的影响将严重到无法设计全局时钟树 的程度。而且由于时钟网络的庞大，其功耗将占据芯片总功耗的大部分。由单 一系统时钟同步全芯片的工作将极其困难。 因此，提供新的设计方法和工具，满足日益提高的系统复杂性、优异的性 价比和产品上市时间短的需求，是摆在电子设计自动化业者面前的一个巨大挑 战。 在1 9 9 9 年，就有人提出了一种全新的集成电路体系结构片上网络 ( n e t w o r ko nc h i p ，n o c ) ，其核心思想是将计算机网络技术移植到芯片设计中 来【4 】，从体系结构上彻底解决总线架构带来的问题。一方面，n o c 不仅具有良 好的空间可扩展性，还提供了很好的并行通讯能力，势必将成为替代总线通讯 方式的一种理想的解决方案；另一方面，n o c 以分组交换作为基本通讯技术， 可以采用全局异步- 局部同步( 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 ， g a l s ) 的通讯机制【5 】【6 1 ，每一个资源节点都工作在自己的时钟域，而不同的资 源节点之间则通过通讯节点进行异步通讯，从而很好地解决了单一时钟同步的 问题。再者，片上网络架构通过路由节点来通讯，而路由节点的连线比较短， 这样消除了全局的r c 延迟，进而有效地解决了互连延迟问题，同时又具有更 好的扩展性。 1 2 国内外研究概况 1 2 1 国外研究概况 国外对片上网络的研究开始于本世纪初，2 0 0 0 年3 月，法国p i e r r ee tm a r i e c u r i e 大学的p i e r r eg u e r r i e r 等人提出可升级、可编程的集成网络( 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 ，s p i n ) ，将并行计算( p a r a l l e lc o m p u t e r ) 中 2 上海大学硕一l 学位论文 的分组交换( p a c k e t s w i t c h e d ) 的方法引入系统芯片内，以实现数据通讯，并 建立了周期精确的路由器性能模型7 1 。同年末，瑞典皇家技术学院等单位首次 提出“n e t w o r ko nac h i p ”概念，把n o c 定义为在一块芯片上实现的、由交换 开关网络互连的计算资源、存储资源以及i o 资源。资源节点之间的通信通过 交换开关将自带寻址信息的数据包从源地址传送到目的地址【8 】。虽然此次对 n o c 的定义尚有争议，但是n o c 的初步设计已经在各个国家的科研工作头脑里 产生了影响。接着于次年，瑞典皇家技术学院与芬兰v t t 大学联合启动 “n e t w o r k o n c h i pa r c h i t e c t u r e ，n o c a r c 计划，研究n o c 的基础架构【9 1 。 2 0 0 1 年6 月，斯坦福大学的w j d a l l y 等发表论文【1 0 】，提出使用片上互连网络 的数据包通讯方式替代各式各样连线结构的构想，将研究重点转移到n o c 上 来。接着，b e n i n i 等人发表概念性论文，他们提出“n o c 是s o c 的新范例的 论断，并论证了将计算机网络的层次化协议结构移植到芯片中的可能性【1 1 1 。后 来k u m a r 等人则提出了一种基于二维网格的片上网络结构，这种结构允许集成 大型资源，如大面积存储单元、f p g a 器件以及高性能多处理器等 1 2 】。 在随后几年，人们从未间断对片上系统的研究【l3 1 。而且随着时间的推移， 对片上系统的研究已经涉及各个方面。2 0 0 4 年2 月期间e l s e v i e rs c i e n c e 在 ( ( j o u m a lo f s y s t e m s a r c h i t e c t u r e ) ) 组织了n o c 专题，该学术期刊介绍了包括 互连、n o c 数据打包与路由交换、n o c 通讯协议的服务质量以及n o c 设计探 索的结构建模等。还有2 0 0 4 年8 月期间，( ( i n t e r c o n n e c t c e n t r i cd e s i g nf o r a d v a n c e ds o ca n dn o c ) ) 一书中介绍的总线连接结构作为n o c 的基本单元、多 处理器仿真系统的基于网络的建模等。在2 0 0 5 年i e e et r a n s a c t i o n so np a r a l l e l a n dd i s t r i b u t e ds y s t e m 组织了名为“o n c h i pn e t w o r k s 专题，会议间就设计方 法，拓扑结构，前沿技术、相关算法、嵌入式系统、专用电路或者应用程序接 口，以及可靠性与可重构等问题展开了一系列的讨论。 目前对于片上网络的研究已经成为研究的热点问题之一，越来越多的研究 机构纷纷投入到其中并推动着它的发展。2 0 0 7 国际上首次组织了以n o c 为主 题的国际会议( n o c s 0 7 ) ，n o c s 2 0 0 8 近期也将在德国召开。国内国外的科学 家都在试图从各个方面解决n o c 所面临的问题。据初步统计，国际上共有3 0 上海大学硕上学位论文 多所大学、研究所以及工业界的研究单位正积极从事n o c 研究工作【9 1 。其中影 响较大的有瑞典皇家技术学院、斯坦福大学、m i t 和荷兰菲利普研究实验室等。 参与研究的国家还有法国、意大利、芬兰、希腊、以色列、巴西、印度、澳大 利亚等。 表1 1 国际上部分研究n o c 机构及研究内容 为通讯系统开发一种片上网络设 k t hr o y a li n s t i t u t eo f n o c a r c 2 】【1 2 】【1 4 】计平台，可同时对系统物理层和 t e c h n o l o g y 结构层提供支持 研究基于网络通讯方式的动态可 i m e ca m d r e l l l 5 】 重构芯片架构 n e x tg e n e r a t i o no n c h i p研究片上多处理器系统通讯协议 m i tc o m m u n i c a t i o n 内容、信号传输技术，减少时延 n e t w o r k s 1 6 】 和降低功耗 研究基丁通讯的设计，异类i p 互 t a m p e r eu n i v e r s it yo f h i b i 1 n 连( h i b i ) n o c ，通讯测试基准， t e c h n o l o g y 体系结构探索，低功耗设计等 t a m p e r eu n i v e r s i t yo f p r o t e o i l 8 】 研究基础通讯元件库的o c n 设计 t e c h n o l o g y 以异步共享总线未研究起点，研 u n i v e r s i t yo f m a r b l e t l 9 究s o c 中异步通信方式，转而研 m a n c h e s t e r 究o c n 中的建模。o o s 以及g a l s 等方面 t e c h n i o n ，i s r a e l以o c n 中的服务质量( q u a l i t yo f i n s t i t u t eo fq n o c 2 0 s e r v i c e ，q o s ) 为着眼点，研究不 t e c h n o l o g y 规则o c n 结构 研究使用电路交换与报文交换的 u n i v e r s i t yo f a s o c 2 1 1 融合问题，研究提高吞吐量的方 m a s s a c h u s e t t s 法 研究n o c 设计过程中的自动综合 s t a n f o r du n i v e r s i t y n e t c h i p 2 2 】 过程，面向特定应用而自动进行 的复杂设计步骤 研究目标基于通讯的s o c 设计并 c a r n e g i em e l l o n s li c n e t s 【2 3 】为片上通信体系结构研究提供形 式化分析和优化方法。 k o r e aa d v a n c e d 研究o c n 的系统结构优化、物理 i n s t i t u t eo fs c i e n c eb o n e 2 4 设计、原型设计 a n dt e c h n o l o g y 目前，该领域中的研究成果日益增多，表1 1 选取了一些有代表性的学术 机构和企业结构及其项目，并简单介绍了各个机构的研究方向与内容。 4 上海人学硕士学位论文 1 2 2 国内研究概况 自2 0 0 6 年度开始，在国内也有大学开展了对片上网络的研究【2 5 - 2 8 1 ，并获得 国家自然科学基金的资助，具体如表1 2 所示。 表1 2 国家自然科学基金在n o c 方向上的资助情况 高性能片上网络及可测试性研究 2 0 0 7 1 2 0 0 8 1 2 清华人学 超低功耗片上网络系统模型及异 2 0 0 7 1 2 0 0 9 1 2 西安电子科技大学 步互连技术 中国人民解放军国防科技大 有界延迟服务片上网络研究 2 0 0 7 1 2 0 0 9 1 2 学 无线通信自重构容错n o c 研究 2 0 0 7 1 2 0 0 8 1 2 西安邮电大学 集成电路n o c 低功耗通信协议栈基 2 0 0 5 合肥工业大学 础研究 1 3 论文主要研究工作 1 3 1 课题背景 笔者所在课题组，近年来正在从事机器视觉处理器芯片的研究。机器视觉 处理器需要处理的任务多，算法复杂。在完成复杂任务时，可使用多个微处理 器共同完成一个系统单元的任务，以数量的优势来弥补低端微处理器在性能上 的不足，因此课题组设计的机器视觉处理器采用了一种单芯片多处理器的结构 【2 9 】【3 0 1 。在这种结构中，各个子处理器之间需要进行命令、状态、数据的传递、 交换，传统的方法是采用某种片上总线诸如w i s h b o n e ，a m b a a h b 等为通讯手 段。而随着技术的发展以及未来要求的增长，以片上总线为核心的设计方法将 因受其不易扩展性以及总线信号延迟等因素的影响，从而使其在未来的应用中 受到局限。而片上网络将为解决当前设计所面临的问题提供一个新的途径。本 文的工作是为课题组将片上网络引入单芯片多处理器中，最终能取代片上总线 所做的理论探索和技术储备。 5 上海人学硕士学位论文 1 3 2 本人工作 本文的主要工作和研究成果如下： ( 1 ) 阐述了片上网络设计中所要考虑的各方面，对各种不同应用的策略进 行了分析比较，得出适合片上网络设计的方案，规划出本文的设计方向。 ( 2 ) 设计并实现2 级流水线的基于2 dm e s h 拓扑结构、x y 维序路由机制 的虚拟通道路由节点。在讨论分析拓扑结构、路由技术，流控机制的基础上， 构建了设计架构，阐述了设计细节。 ( 3 ) 搭建了一个用于网络验证的测试平台。通过分析片上网络的特点的基 础上，搭建了网络性能测试的平台。用此平台对本文设计的路由节点进行了验 证及性能分析。通过功能测试，证明了设计的正确性和可行性。通过性能测试 得出了由所设计的路由节点组成的网络的性能特点曲线。 本文的工作虽然还不全面，但为后续的诸如片上网络的资源及功耗分析， 以及设计更复杂的功能如q o s ( q u a l i t yo fs e r v i c e ) 、容错控制等工作做了些前期 准备和探索，为后续的研究打下了坚实的基础。 1 4 本文架构 本论文按照整个片上网络的分析和设计的过程进行组织和编排，从系统整 体架构设计到具体的模块设计，以及系统的仿真验证实现，到最后的设计中的 不足与展望都进行了较为详细的阐述。全文共分为五章，安排如下： 第一章中阐述了课题研究意义以及国内外研究的现状。概述了本文主要研 究的内容和实现方法； 第二章阐述了片上网络的概念以及设计中着重考虑的因素，包括架构，路 由策略，流控机制。综合各种考虑，折中选定了本文的设计方向； 第三章结合了上章提出的各种概念，对片上网路路由节点的架构及各部分 功能单元的设计进行了详细的解析，完成了设计； 第四章给出了本文设计的片上网络的验证方案以及具体的测试方法，接着 给出了验证结果和性能分析。 6 上海大学硕上学位论文 最后第五章总结了全文以及对今后的工作的进行了展望。对本设计中有待 进一步研究和展开的工作进行了阐述，并对本课题未来的研究方向进行了探讨。 7 上海大学硕十学位论文 第二章n o c 的背景知识及设计要求分析 自上个世纪9 0 年代末片上网络的概念被提出以来，片上网络各方面的研究 都在迅速进行中。片上网络的提出最早是借鉴并行计算机的互连网络，所以片 上网络与并行计算机网络有很多的相同点。不同的是并行计算机的互连网络是 一个板级的网络，而片上网络是一个芯片上的网络，特别是在路由算法方面， 几乎所有的片上网络路由算法都在并行计算机网络中找得到它对应的算法。但 是它们又有一些不同，主要表现在以下两个方面： ( 1 ) 片上路由器结构简单，不宜采用较复杂的路由算法和交换机制。 由于面积所限，片上路由器都是由较简单的逻辑元件组成的。所以，片上 网络所采用的路由算法通常都为较简单。而较复杂的路由算法，类似于并行机 中静态维数翻转自适应算法和动态维数翻转自适应算法【3 1 1 ，虽然可以取得较好 的路由性能，但是由于片上网络的资源所限，一般都没有采用。此外，在片上 网络中缓存是最宝贵的资源，片上路由器的缓存通常都很小，因此一般对缓存 要求比较高诸如存储转发交换机制，也仅仅是在理论分析时会用到，而在实际 设计时很少采用。 ( 2 ) 片上网络的网络协议。 与并行机不同，在片上网络中没有专门的协议处理机，所有的协议都必须 由硬件处理，这就要求片上网络的网络协议不能太复杂。这样，许多在并行机 中的流控协议( 如g o b a c k n 等) 在片上网络中都不能应用。所以通常都要 求n o c 中的路由算法将数据包完整、无损、顺序地投递。可以看出，上面的 两点差异都是由片上网络本身的特点造成的。也正是由于片上网络与并行机有 着这些差异，所以有必要单独整理和总结片上网络中的路由算法及路由技术 3 2 1 3 3 。 2 1n o c 结构概述 一个典型的片上网络结构如图2 1 所示。从图中可见，一个基于片上网络 上海大学硕上学位论文 的系统由以下几个部分构成： 路由节点 处理单元 资源嗍络接口 网络连线 图2 1 典型的2 - d m e s h 网络结构 处理单元( p r o c e s s i n gc o r e ) ，也可称为资源节点。这里可以是一个微处理 器，一个d s p 处理器，一个专用模块，一个存储单元或者一个i 0 处理器，也 就是具有一定处理功能或存储功能的系统或模块。 资源网络接口( n e t w o r ki n t e r f a c e ) ，它主要负责处理单元和路由节点之前 的数据传输。主要具有两个功能，一方面负责把从处理单元发出的数据打包成 具有网络协议格式的数据包，然后注入进网络。另一方面，负责从网络接受数 据包，然后对之进行解包，还原成普通的数据格式，再送给处理单元。这些功 能促使了计算( 处理单元) 与通讯( 网络) 相分离。 互连网络( i n t e r c o n n e c tn e t w o r k ) ，互连网络的拓扑定义了网络节点的连接 方式，规定了节点传输的各种路径，定义整个设计的通讯架构。 路由节点( r o u t e r ) ，路由节点用来决定数据流向。一个路由节点首先在它 的输入端口接受数据包，然后在经过一定的路由计算和仲裁后，再从其相应的 输出端口送出数据包。 从以上的阐述，我们了解到基于片上网络为通讯架构的系统的基本组成元 素。进之，对于一个片上网络通讯架构设计来说，主要由以下几个元素构成， 分别是拓扑结构，所采取的路由策略，流控制策略，交换技术，仲裁技术以及 缓冲区的设计方案以下将介绍各种概念并分析比较，在分析对比的基础上，选 9 o口圈西 上海火学硕上学位论文 定本文的设计方向和目标。 2 2n o c 的拓扑结构 n o c 的拓扑结构就是指n o c 中各个节点的连接方式。不同拓扑结构的网络 其信道的访问技术，利用率以及信息的延迟、吞吐量、设备开销都各不相同， 直接影响了路由策略和交换机制的设计以及最终n o c 的性能。所以，在片上网 络设计中，拓扑结构的选择非常重要。目前，片上网络的拓扑结构形式多样， 最常用的网络拓扑结构有2 dm e s h 、2 dt o r u s 、胖树( f a t t r e e s ) 以及o c t a g o n 等。 一般网络拓扑可分为两类，一类是规则性结构( r e g u l a r a r c h i t e c t u r e s ) ，另 一类是非规则性专用结构( i r r e g u l a ra p p l i c a t i o ns p e c i f i cn o cs t r u c t u r e s ) 。在这 里我们将以片上网络设计需求的视角介绍几种，并分析适合片上网络设计的拓 扑结构。 为了描述的方便，我们用黑色的方框表示路由节点，而白色的方框表示资 源节点( m ) ，也即处理单元。 2 2 1 2 dm e s h 结构 2 dm e s h 结构是一种最简单的拓扑结构【1 2 】【3 4 1 ，如图2 2 。它具有良好的对 称性，扩展性，可以支持很多路由协议、流控技术和交换算法，允许设计者根 据不同的资源节点或者应用模块来调节节点数。在这里，每个节点有四个端口， 分别为东、西、南、北和本地端口，分别连接着一个资源节点和四个相邻的路 由节点，每个资源通过一个网络接口( n i ) 连接着一个路由器。其中的资源， 可以是一个处理器核、内存、一个用户自定义硬件模块或者是其他任何可以插 入并且可以和网络接口相配的i p ( i n t e l l e c t u a lp r o p e r t y ) 模块。路由器与路由器 之间，路由器与资源之间是由一对输入和输出通道连接。通道是由两条单向的 点对点总线组成。 1 0 上海人学硕士学位论文 图2 2 2 d m e s h 网络拓扑结构 相对后面所提到的t o m s 结构，2 dm e s h 结构具有更多的平均节点数和更 少的连接通道，同时能耗也比f o l d e dt o m s 的小1 们，加之，二维结构更容易映 射到硅表面。据此，在本文n o c 架构设计中，我们采用2 dm e s h 网络拓扑结构。 2 2 2 2 0t o r u s 结构 l_一 一 弋 惑 惑 匹 l- 一 弋 电 电 电 l - 一 弋 惑 惑 匹 i-一-一一 r 一 j 一 广， 图2 34 x 4 的2 d t o r u s 结构 图2 3 是一个4 x 4 的2 d t o r u s 结构0 0 j 。2 d t o m s 结构可以看成是对2 dm e s h 的一种扩展，即在边界的节点上增加了一条长的环路。因此，网络中的所有节 点的度为4 ，对于一个m n n 的t o m s 网络，其中m 、n 为每个维度上的节点数， 若m - - n 则称之为规则的t o r u s 。2 dt o r u s 拓扑在物理形式上与2 dm e s h 相似， 但由于其存在很多的环路，所以在路由算法和路由仲裁方面都要复杂许多。另 外，由于其不均匀的连线长度，所以不太适合应用在片上网络的设计中【3 5 】。 上海大学硕上学位论文 2 2 3 胖树结构 如图2 4 所示，胖树( f a t t r e e s ) 结构【7 】【3 6 】比较简单明了，每个处理单元( 口) 位于f a t t r e e s 的一个树叶节点上，同一层的路由节点不相互连接，而是通过上 层节点来和同层的其他节点通讯。每个路由节点只把数据包传向上一层节点( 父 节点) 或者下一层节点( 子节点) ，这样使路由算法实现起来比较简单。但从图 中又可以看出，随着层次的增加，对越上层的节点来说，需要更长的互连线和 更大的带宽反映到芯片上就是面积，这种局限性严重阻碍了胖树结构的扩 展能力。所以说，胖树结构不太适合应用于片上路由网络。目前在s p i n 网络 结构 3 刀互连设计中采用了经过改进的胖树拓扑结构。 i ，e v e 】 2 2 4 八边形拓扑结构 图2 4 胖树( f a t t r e e ) 拓扑结构 2 o 八个型结构( o 比喀o nt o p o l o g y ) 3 8 1 是将八个节点组成一个局部环，并通过3 条直径连接这八个节点，同时每个节点连接一个处理单元，如图2 5 ( a ) 所示。 k - - i 。k ( a ) 又入尺力 。匕漱淑p r*漱力 k y k汐 图2 5 八边形网络拓扑 1 2 上海大学硕士学位论文 从环内的任节点出发，最多经过两跳，也即经过一个中间节点，即可达 到环内任意节点。八边形网络是可升级的。如果将环内的一个节点用作桥节点， 更多的八边形可以连接在一起，组成网络结构，如图2 5 ( b ) 所示。 2 2 5 立体环形拓扑结构 立体环形连接( c u b ec o n n e c t e dc y c l e s ，c c c ) 拓扑网络作为一个直角拓扑结 构的折中而被提出，为了减少每个节点的度数【3 9 】。c c c 网络具有鲜明的层次性， 立方体每个角的3 个节点构成一个局部环，每个环又可以与相邻的环连接，从 而组成了网络结构。 ( 1 0 0 ) ( 0 0 0 ) 2 2 6 蝶形拓扑结构 图2 6 立体环形网络 0 1 1 ) 在蝶形结构( b u t t e r f l y ) 之内，每条源一目的路由使用一个专门的数据路径； 在任何的两个处理器节点之间的延迟是一样的，而且延迟由开关网( s w i t c h f a b r i c s ) d ：的中间阶段数目所决定的。 上海大学硕士学位论文 2 2 7 b f t 结构 图2 7 蝶形拓扑结构 b f t 拓扑结构【删是一种蝶形( b u f f e r f l t y ) 结构和胖树( f a t - t r e e s ) 结构相 混合的拓扑形式，如图2 7 所示。 2 2 8 非规则性结构 图2 8b f t 结构 l e v e l ，) o 1 o b e n i n i 等人提出了用于建立专用的基于网络的s o c 系统的不规则性网络结 构( i r r e g u l a ra r c h i t e c t u r e s ) 【4 1 1 。 1 4 上海大学硕七学位论文 2 3 路由算法 图2 9 非规则性网络结构 正如前面所说，n o c 拓扑结构决定了路由节点之间的连接方式或路径，保 证每个节点可以发送数据包到其他节点。路由算法则是在网络拓扑的基础上决 定数据包从源节点到目的节点传输路径的选择，而网络的延迟又和路径的选择 息息相关，所以，有效的路由算法对n o c 网络性能的好坏是至关重要的。路由 算法包含在路由节点结构中，故在设计一个路由节点之前，有必要分析和选择 路由算法。 路由算法可以按照不同的标准分为不同的几类。比如说源路由( s o u r c e r o u t i n g ) 和分布式路由( d i s t r i b u t e dr 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 ) 3 1 】。这里的讨论基于后一种分类方法。 2 3 1 确定性路由( d e t e r m i n i s t i cr o u t i n g ) 确定路由是一种常见的路由，它的路由路径只与起点地址和终点地址有关， 给定起点和终点地址，路由路径就被确定了，与当前网络的状态无关。而在确 定路由中，使用的最多的则是维序路由( d i m e n s i o n o r d e r e dr o u t i n g ) ，因为它 有着非常简单易实现的路由逻辑。 在维序路由中，每个数据包一次首先只在某一维上路由，当在这个维上到 达了恰当的坐标之后，才按由低维到高维的顺序在另外的维上路由。因为数据 包是严格按照单调的维数变化顺序在通道内路由，所以维序路由是没有死锁的。 1 5 上海大学硕：l 学位论文 根据在不同拓扑结构的网络中路由，维序路由包括了2 d m e s h 中的x y 路由和 在超立方体( h y p e rc u b e ) 中的e - c u b e 路由【4 2 1 。 2 3 1 1x y 维序路由 2 dm e s h 中的x y 维序路由是最简单的一种路由算法【4 3 1 ，它的路由过程是： 先x 方向将数据包包送至目的节点所在的列；再沿y 方向将信数据包送至目的 地处理器所在的行，如图2 1 0 所示。 jl 一 一l 心l 电i 电 一 回 一 l 电i 电i 电 一一 l 回 一 一 - o 一 - 一i 电 曰曰团 晒晒晒晒 l 图2 1 02 dm e s h 拓扑结构x y 维序路由图形展示 具体的工作流程见图2 1 1 ，当路由器开始处理一个数据包的时候，因为采 用的是x y 路由，路由节点将自己的坐标( x ，y ) 同数据包的目的地址( m ，n ) 相比较。如果x a ，则将数据包向西转发；如 果x = a ，y b 则将数据包向南转发；如 果x = a ，y = b ，那么说明数据包到达了目的地，这样路由节点就把数据包发往与 之相连的处理单元。 那么，对照图2 1 0 举例说明，一个从节点( 1 0 ) 发出的数据包，其目的地 是( 3 ，3 ) ，则它采用x y 路由算法的路由路径是： ( 1 0 ) - - ( 2 0 ) - - ( 3 0 ) - - ( 3 1 ) - - ( 3 2 ) 一 ( 3 3 ) 。 1 6 上海大学硕j ：学位论文 2 3 1 2e c u b e 路由 图2 i ix y 维序路由的路径选择过程 e c u b e 路由和x y 路由很相似，都是先在一个方向( 维) 上路由，然后再 在其它方向( 维) 上路由。具体来说，前面提到了在n 维立方体中，每个节点 是用一个nb i t 的二进制编号表示的。每个节点1 1 条输出的通道，其中第i 条通 道就对应的第i 维。在e c u b e 路由算法中，数据包的头部携带了目的节点的地 址d 。当n 维立方体中的一个节点v 收到一个数据包时，e c u b e 路由算法计算 路由向量c = do v ，其中。是逻辑运算中的异或运算。如果c = 0 ，说明数据包 已经到达了目的地，则传向口。否则，数据包将被送往第k 维的输出通道，其 中k 是c 里面最右边( 或者最左边) 的1 的那一维。 举例来说，如图2 1 2 ，一个由s = 0 1 1 0 产生的数据包要传向目的地为d = 1 1 0 1 的节点。首先计算路由向量e l = d os = 1 1 0 10 0 1 1 0 = 1 0 1 1 。取最右边的不 为零的一位为k ，则k = 1 ，说明这时的数据包将会被送往第1 维上的通道。然 后到达了v l = 0 1 1 1 ，再计算路由向量c 2 = d o v l = 1 1 0 10 0 1 1 1 = 1 0 1 0 ，得出k = 2 ，然后送到第2 维的通道上。随即到达v 2 - - 0 1 0 1 ，再一次计算e 3 = dov 2 = 1 1 0 1o0 1 0 1 = 1 0 0 0 ，得出k = 4 ，接着把数据包送到第4 维的通道上。最后到 达了目的地d = 1 1 0 1 。最终，得出的路由过程是： 0 1 1 0 一 0 1 11 - - 0 1 0 1 - - 11 0 1 。 1 7 上海大学硕上学位论文 撩：$ ：0 1 1 0 目的：d = 1 1 0 1 路径： o i l 0 - - - 0 1 1 1 - - * 0 1 0 1 一1 1 0 1 l o l 图2 1 2e c u b e 路由过程 从上面的路由过程可以看出，虽然e c u b e 路由与x y 路由是在不同维数的 网络中路由，但是它们都有很相似的共同点：即一次只在一个方向( 维数) 上 路由，直到在该方向( 维数) 上当到达了与目的地址相同的节点，再按照单调 的顺序改变方向在其它维上路由，x y 路由是由x 方向改变到y 方向的顺序， e c u b e 路由是从低维到高维( 或者从高维到低维) 的顺序。而这正是维序路由 算法的典型特征。 确定性路由优点是，路由算法简单，在网络低拥塞环境下能获得较低延迟。 但是由于其不能响应动态的网络状态变化，所以当网络拥塞增加时，性能迅速 降低。 2 3 2 自适应路由( a d a p t i v or o u t i n g ) 所谓的自适应路由，就是指数据包的路由路径不仅与起点地址和终点地址 有关，还和网络的实时状态有关。也就是说，有同一对起终点地址的数据包， 在不同的网络状态下，它们的路由路径也可能不同。相对于确定性路由来说， 自适应路由的优点是采用自适应路由的路径，避免了网络拥塞，可以得到更高 的网络带宽饱和值；但是它的路由逻辑较复杂，在网络低拥塞的情况下开销较 大，而且还存在死锁问题。 对比确定性路由，自适应路由确实有优点，它通过动态的改变路径从而达 上海大学硕士学位论文 到避免网络阻塞，提高了网络性能。然而，确定性路由通常更适合n o c 的设计， 原因在于： ( 1 ) n o c 的资源有限性和更紧的时延要求 在n o c 中应用确定性路由最主要优点在于在路由节点设计简单实现，因为 简单的逻辑，确定性路由可以在网络不拥塞时获得很好的时延性能。另一方面， 实现自适应路由算法需要消耗更多的资源，而且，自适应路由可能使数据包到 达目的节点时顺序不一致，需要很大的缓冲区去重新调整顺序。这些都将导致 确定性路由算法需要更大的时延，更多的资源，也即更大面积，而面积的增大 对于芯片设计来说就是成本的提高。 ( 2 ) 传输可预测性 大部分片上网络的设计开发基本针对某种应用或者某类应用。因此，只要 设计者很好地理解