（计算机系统结构专业论文）片上网络的结构设计与性能分析.pdf

摘要 摘要 本世纪初，w j d a l l y 等基于大规模多处理器与分布式计算网络提出了片上 网络这一概念。片上网络互联结构州e t w o r ko nc h i p ，简称n o c ) 的提出，是为了 满足片上模块之间通信高带宽、低延时的需求，弥补传统片上总线互联结构中串 行总线通信带宽低、可扩展性差的不足。片上网络的基本特征是模块化设计片上 互联结构，各计算模块之间通过片上的微型网络进行并行通信，提供高带宽低延 时，同时提高可扩展性。片上网络跟传统计算机网络有很多相似之处，比如都有 路由器、拓扑结构等设计因素，但片上网络跟传统计算机网络有很大的不同，它 是在单芯片上实现的微型网络，要充分考虑功耗和面积限制，以及复杂连线带来 的时钟周期增长等问题。因此片上网络的设计是一种问题权衡，关于开销、复杂 度、性能等设计标准的权衡，设计目标是在尽可能不增加开销和复杂度的前提下， 提高通信性能。 由于片上网络与传统网络有上述差异，在片上网络结构设计中要考虑更多的 丌销限制。本文的研究目的就是基于这些限制，设计出更适合片上网络的拓扑结 构、路由器结构及其相关算法，从而使得片上网络得到更好地应用，使得包含片 上网络的单片多处理器等片上系统得到更优的系统性能。 本文的研究内容主要分为片上网络的结构设计与性能分析两大部分。其中结 构设计主要包括拓扑结构设计、路由器调度算法设计、路由算法设计等；性能分 析主要分析现有的经典网络设计之间的性能优劣，如调度算法、路由算法、流控 机制等。内容具体分为三大部分，第一部分主要包括绪论、研究现状及关键技术、 研究平台，即第一章、第二章和第三章；第二部分内容为片上网络结构设计，对 应第四章和第五章；第三部分是性能分析与论文总结，包括第六章和第七章。 本文的研究方法主要是：基于p o p n e t 与g o d s o n 用户级模拟器，针对现有经 典网络结构在片上应用的不足，设计性能更有的网络结构，最终分析评估它们的 性能优劣。 本文的主要研究成果如下： 首先，基于经典拓扑结构提出三种新型拓扑结构x m e s h ，s t o r u s 和r g r i d ， 其中x m e s h 在m e s h 结构基础上增加了若干互联线从而减小节点间跳数，同时增 大了网络的理想吞吐量，适用于小规模片上网络，s t o m s 以t o r u s 结构为基础， 在网络中增加了两个哈密顿圈，适合多播或广播，r g r i d 是一个可扩展的拓扑结 构，它减小了节点间平均距离又没有引入长连线，适用于中小规模的片上网络。 其次，本文针对单通道输入队列路由器提出了三种基于r o u n d r o b i n 的调度 摘要 算法，分别以三种不同的权值作为调度基准，与r o u n d r o b i n 调度算法相比较， 这些算法能够降低输入负载流的最大延时和平均延时，从而提高系统性能。 最后，本文基于蚁群算法提出了一种新的路由算法a n tr o u t i n g ，选择路由 时根据每条路径上的信息量多少来选择是否走这条路径，信息量代表该路径的负 载繁重程度，该算法可以减轻繁重负载带来的拥塞问题。 总之，本文通过结构设计对片上网络实现性能优化，为片上网络结构设计提 供了更多更好的设计选项，对传统网络的经典结构进行了评估与比较，通过性能 分析为片上网络设计提供了一些经验性的结论。 关键字：片上网络，拓扑结构，路由算法，调度算法，b u 疵r 模块，流控机 制 2 a b s t r a c t i nt h eb e g j i m i n go f21s t c e n t u 啦w j d a l i yb r i n g sf o r ，a r dt h ep a r a d i g mo fo n c h l pj n t e r c o n n e c t i o n t bm e e tt h ed e m a n d so fh j g hb a n d w i d t ha n dl o wl a t e n c v c o m m u n l c a t l o na m o n gm o d u l e so nc h i p ，n e t w o r ko n c h i pt e c h n i q u eg r o w su p ne 晰o r ko nc h i pi sc a l l e dn o c f o rs h o n t h eb a s i cp r o p e n i e so fn o c a r e ，i tp r e s e n t s am o d u l a r ，c o m p o n e n t - b a s e da p p r o a c ht oh a r d w a r ea 1 1 ds o r w a r e d e s i g n s ，u s i n gm i c r o n e t w o r kt oc o m m u n j c a t ea m o n gm o d u i e s n o cp r o v i d e sh i g hb a n d w i d t h ，i o w i a t e n c v a n ds c a i a b i l i t y n o ci ss i m i l i a rw i t hc o n v e m i o n a l c o m p u t e rn e t w o r k ，b o t ho ft h e m n e e dr o u t e r sa n dt o p o l o g y h o w e v e r ，n o ch a sm u c hd i f 凳r e n c ew i t hc o m d u t e r n e t w o r k n o ci si m p l e m e n t e do n s i n g l ec h i p ，w h i e hh a sm a n yj i m i t i n gf a c t o r ss u c ha s r e s m c l e da r e aa n dp o w e r ，a n dc o m p l e x 1 0 n gl i n kw i r ew i i lr e s u l ti ni a r g e rc p uc v c i e t i m e t h e r e f o r e ，n o cd e s i g ni s d o i n gt r a d e o f f s ，a m o n gp e r f o r m a n c e ，h a r d w a r e c o m p i e x l t ya n dc o s t ，p r o v i d i n gg o o dp e r f o r m a n c ea tt h ec o s to fl i t t l ec o m p l e x i t ya n d o t h e rc o s t b e c a u s eo ft h ed i f f e r e n c e sb e t w e e nn o ca n dc o n v e n t i o n a i n e t 的( t h en o c d e s l g ni sl i m l tt om a n yc o s tf a c t o r s ，s u c ha sa r e aa n dp o w e r t h er e s e a r c ho b i e c to f h l sd i s s e r t a t i o ni st h a t ，b a s e do nt h ea b o v e l i m i t s ，d e s i g n i n g b e t t e rn e t w o r kt o p o l o g i e s ， r o u t e r sa n dt h e i ra l g o r i h m s ，s oa st oi m p l e m e n t b e t t e rn o cs y s t e m ，p r o v i d i n g b e t t e r s y s t e mp e 怕r n l a n c ef o rc m pa n do t h e ro nc h j ps y s t e m s t h ec o n l e n to f 幽i sd j s s e r t a t i o nc a nb ed j v i d e da sn o c a r c h i t e c t l l r ed e s i 2 na n d p e r f o 咖a n c e a n a j y s i s t h ea r c h i t e c t u r e d e s i g n i n c l u d e j t o p o l o g y ， s c h e d u l i n g a i g o n t a n dr o u t i n ga l g o r i t e t c p e r f o r m a n c ea n a l y s i si se v a l u a t i n ga j l da j l a l y z i n g t h ep e r f 0 肌a n c eo fc l a s s i cn e t w o r ka r c h i t e c t u r e t e c h n o l o g i e s ，s u c ha ss c h e d u l i n g a l g o n t l u n ，r o u t i n ga l g o r i t m 1 ，a n dn o wc o n t r o lm e c h a n i s m s t h i sd i s s e r t a t i o n i s p a r t l t l o n e di n t ot h r e es e c t i o n s t h ef i r s ts e c t i o np r e s e n t st h ei n t e r n a t i o n a lr e s e a r c h s t a t u so tr e c e n ty e a r sa j l dt h er e s e a r c h p l a t f i o r mi nc h a p t e r1 ，2a j l d3 t h es e c o n d s e c t l o np r o v i d e sn o ca r c h i t e c t u f ed e s i g ni nc h a p t e r4a n d5 t h el a s t s e c t i o n2 i v e s p e r f o r m a n c ea n a l y s i sa n dc o n c l u s i o ni nc h a p t e r6a n d7 11 1 er e s e a r c hm e t h o do ft h i s d i s s e 九a t i o ni st h a t ：u s i n gt h ep o p n e ta n dg o d s o n s l m u j a t o r s ，t om a k eu pt h es h o n c o m i n g so f t h ec l a s s i cn e t w o r ka r c h i t e c t u r e ，d e s i g n a n d l m p l e m e n tn e wt o p o l o g i e sa n dr o u t e r s ， n n a l l ya n a l y z ea n de v a l u a t et h e i r p e r f o r m a n c e 1 a b s t r a c t t h ec o n t r i b u t i o n s0 ft 1 1 i sd i s s e r t a t i o na r es h o 、na sf o l l o w t h ef i r s ti m l o v a t i v ei d e ai st h a t ，t h i sd i s s e n a t i o np r e s e m st h r e en e wt o p o l o g i e s x m e s h ，s t o m sa n dr g r i d x m e s ha d d ss o m el i n k so nt h em e s ht o p o l o g y ，r e d u c i n gt h e h o p sa m o n gn o d e s ，a tt h es 锄et i m ei n c r e a s i n gt h ei d e a lt h r o u g h p u to fm et o p o l o g y ， x m e s ha d a d t st os m a l l s c a l en e t w o r k s t o r u sr o t a t e ss o m el i m ( so ft b r u s ，t h ee d g e so f s t o r 呱f 0 衄st w oh a m i l t o nc y c l e s ，s t o r u sa d a p t st om u l t i c a s ta n db r o a d c a s tt r a m c r g r i di sas c a l a b l et o p o l o g y ，i td o e s n ta d dl o n gl i n kw i r e ，i ts u i t ss m a l la n dm i d d l e s c a l eo nc h i pn e m 7 0 r k 】m es e c o n di n n o v a t i v ei d e ai s 缸e es c h e d u l i n ga l g o r i t h m s ，w h i c hu s et h r e e d i f r e r e n ti t e m sa ss c h e d u l i n gs t a n d a r d s c o m p a r e dt or o u n d r o b i n ， 也e s en e w s c h e d u l i n ga i g o r i t h m s c a nr e d u c e t h e l a r g e s t a n da v e r a g er o u t i n gl a t e n c i e s ， c o n s e q u e n t l yi m p r o v e t h es y s t e mp e r f o r m a n c e n et h i r di n n o v a t i v ei d e ai sar o u t i n ga l g o r i t h mc a l l e da 1 1 t _ r o u t i n g a n l r o u t i n g i sd e s i g n e db a s e do na n tc o l o n ya l g o r i t h m s ，w h i c hs e l e c tt h ep a t hb a s e do nt h e a m o u n to ft h ei n f o r m a 矗o ni nt h el i n k s t h ea m o u mo ft h ei n f o m a t i o nr e p r e s e n t st h e 锄o u n to ft r a m cl o a d t h i sr o u t i n ga l g o r i t h mc a na u e v i a t et h ec o n g e s t i o ni n d u c e db y h e a v yt r a m cl o a d i nc o n c l u s i o n ，t h i sd i s s e r t a t i o no p t i m i z e sn o c p e r f o n n a n c eb yt o p o l o g y ，r o u t i n g ， s c h e d u l i n ga l g o r i t h md e s i g n ，p r o v i d e sm o r e a n db e n e rd e s i g no p t i o n sf b rn o c ，g i v e s s o m ee x p e r i e n t i a lc o n c l u s i o n sb yp e r f - o m a n c ea n a l y s i s k e yw 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 i n ga l g o r i t h m ，s c h e d u l i n g a l g o r i t t m l ，b u f k rm o d u l e ，f l o wc o n t r o l 4 目录 图目录 图2 1 四通道中用虫孔流控机制发送5 f l i t 的时空图：a ) 传统方法；b ) 所 提出的新机制。1 0 图2 2ht r e e 1 1 图2 3 有6 4 个i p 块的b u t t e l 江l yf 肝t r e e 1 2 图2 4s pi d e r g o n 拓扑结构和片上布局1 2 图2 53 3m e s h 结构中的4 号路由器的路由表1 6 图2 6a ) 传统的f l a t t e n e d b u t t e r f l y 路由器；b ) 带旁路通道的路由器 ：! ：! 图4 14 4 的x m e s h 结构3 3 图4 2x m 算法的伪代码3 4 图4 33 种算法基于均衡负载的性能比较3 9 图4 43 种算法关于热点负载的性能比较3 9 图4 5 热点负载变化时的性能分析4 l 图4 64 4 的s t o r u s 结构4 2 图4 7 选择虚通道的伪码4 4 图4 8r g r i d 结构定义4 8 图4 9 三种拓扑结构的边数，直径，节点平均距离比较5 0 图4 1o 路由算法d r 相关函数m i n 5 2 图4 11 路由算法d r 5 3 图4 1 2r g r i d 拓扑结构的路由步骤5 3 图5 1r r p a t h 调度算法的伪代码5 9 图5 2 当参数r = 0 3 及g = 1 2 时，单向热点负载的平均延时6 l 图5 3 当参数r = 0 3 及g = 1 2 时，单向热点负载的最大延时6 1 图5 4 当参数r o 4 及g = 1 2 时，单向热点负载的平均延时6 l 图5 5 当参数r = 0 4 及g = 1 2 时，单向热点负载的最大延时6 2 图5 6 当参数r = o 3 及g = 1 2 时，双向热点负载的平均延时6 2 图5 7 当参数r - 0 3 及g = 1 2 时，双向热点负载的最大延时6 2 图5 8 当参数r = 0 ，4 及g = 1 。2 时，双向热点负载的平均延时。6 3 图5 9 当参数r = 0 4 及g = 1 2 时，双向热点负载的最大延时6 3 图5 1 0 当参数g 从0 0 5 变化到0 3 时，均衡负载的平均负载变化6 5 图5 1l 当参数g 从o 0 5 变化到o 3 时，均衡负载的平均负载变化6 5 图5 1 2b o r r o w d q 算法的借取过程7 1 图5 1 3b o r r o w d q 算法的b u f f e r 归还过程6 9 图6 1v o q 与5 v c 关于两种负载的平均延时和最大延时比较8 5 4 目录 表目录 表4 1 均衡负载的平均延时比较，4 5 5 表4 2白相似负载的平均延时比较4 5 表4 34 4 网络上，d e l tt = 0 2 时，以不同节点为热点的延时比较4 4 5 表4 4热点负载的平均延时比较4 4 5 表4 。5均衡负载的平均延时比较4 6 表4 6 自相似负载的平均延时比较4 7 表4 7 热点负载的平均延时比较4 7 表4 8m e s h 和r g r j d 结构上关于包总数、平均延时、i p c 的执行结果5 4 表5 1 当n = 4 时，r o u n d r o b i n 调度算法的结果5 8 表5 2 当n = 4 ，h di s t a n c e = 2 ，r r p a t h 算法的调度算法5 8 表5 3p o p n e t 模拟器的配置参数6 0 表5 4a n tr o u t i n g 算法的代码7 0 表5 ，5 模拟延时结果( 单位：c y c l e ) 7 3 表6 1b u f f e r 深度对热点负载延时的影响7 5 表6 2 虚通道个数对热点负载延时的影响7 6 表6 3 调度算法对于热点负载路由延时的影n 向7 8 表6 4 调度算法对于均衡负载路由延时的影响7 9 表6 5 流水线级数对于热点负载的路由延时影响8 0 表6 6t o r u s 上算法关于( 0 ，o ) 热节点的模拟结果8 l 表6 7 三种算法关于热点负载的性能分析8 2 表6 8 六种算法关于矩阵转置负载的模拟结果8 2 表6 9 六种算法关于b i tc o m p l e m e n t 负载的模拟结果8 3 表6 1 0 六种算法关于均衡负载的模拟结果8 3 表6 1 1 使用s p l a s h 2 测试程序，存储转发与虫孔流控机制的延时比较8 4 表6 1 2 存储转发与虫孔流控的功耗与面积比较8 4 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名：硅鳢 2 0 0 5 年 月s 日 惭扒 第l 章绪论 第1 章绪论 片上网络( n e t w o r ko nc h i p 简称n o c ) ，是实现于芯片中的微型网络，属于计算 机网络，又与传统计算机网络有很大差异。晶体管工艺集成度的快速提高引起了 片上网络研究领域的兴起。片上网络提供模块化、可扩展的、高带宽低延时的片 上互联结构，是单片多处理器以及其他片上系统实现片上通信的重要选择。 从本世纪初开始，研究者把片上网络划分为多个领域作了大量相关研究，并 且实现了具体的片上网络系统。片上网络与传统计算机网络有很多相似之处，片 上网络设计可以参照传统网络的设计方法与流程，但限于有限的片上资源，设计 时要考虑更多的开销限制，因此其设计过程又与传统计算机网络有很多差异。因 此片上网络研究需要进行更加细致的权衡考虑，针对带宽、延时、功耗、面积等 性能标准进行优化设计，为实现高性能片上系统提供高效的通信支持。 拓扑结构是片上网络各模块连接的框架，决定网络的潜在最优性能，路由器 结构的调度策略与流控机制决定数据包在网络中的传输效率，拓扑结构与路由器 结构是片上网络设计最重要的两个部分。本文主要针对片上网络的拓扑结构与路 由器结构设计提出新的设计方案，优化传统网络设计的不足，为片上系统设计者 提供新的设计选择，并针对传统网络技术进行性能分析评估，得到一些经验结论。 本章对论文的选题意义、研究现状、技术路线与本文贡献、论文结构等内容 进行介绍。其中选题意义主要说明选择片上网络这一研究方向的原因、片上网络 的特征及其研究意义；研究现状简单介绍了目前研究领域中片上网络的研究方 向：技术路线主要是采用模拟器，对现有网络结构的不足进行性能优化，研究成 果分为三点；最后列出论文的组织结构。 1 1 选题意义 据国际半导体技术蓝图预测【6 2 1 ，未来几年内，5 0 m 的晶体管工作在l v 电压 下，片上晶体管数目将会增长到数十亿，主频可以提高到l o g h z 。单片多处理器 能够有效利用片上的海量晶体管资源，成为当前高性能处理器的发展趋势 1 6 3 6 4 ，6 卯。芯片集成度的提高导致片上计算资源快速增加，片上各模块间通信对片 上系统的性能影响也随之增大。如何有效地连接片上资源，包括处理器、控制器、 存储阵列等，是影响片上系统性能的关键因素。 传统的单芯片多处理器( c m p ) 普遍采用共享总线的方式进行通信，因为其实 现简单、发展成熟。然而随着微电子技术的发展，c m p 逐渐朝着多核化( 几十或 i 第1 章绪论 上百个核) 和异构化( 包含不同类型的核) 的方向发展，共享总线结构面临以下几个 问题，逐渐成为影响c m p | 生能的主要瓶颈【6 l 】：1 ) 带宽限制：总线是一种共享介 质的互连结构，某一时刻只允许一个设备使用总线，仲裁逻辑允许高优先级的设 备获得总线的使用权，在总线被占用期间，所有其他的请求被阻塞，直到总线空 闲；2 ) 信号集成度：更低的电源电压，更小的线宽，使得整个v l s i 系统对电流 中的噪声更加敏感，而共享介质上的更多功能部件则进步加重了噪声；3 ) 信 号延迟：随着特征尺寸的下降，连线延迟成为影响信号延迟的主要因素，总线结 构是全局控制的，在1 0 亿量级晶体管时代，全局的线延迟会大于时钟周期，总线 结构的全局连线使得时钟的偏移很难管理；4 ) 全局同步：全局连线上的信号延 迟决定了系统的时钟周期，为了保持或提高系统时钟频率，需要对全局连线进行 分布流水，或者采用全局异步局部同步( g l o b a l i ya s y n c l l r o n o u sa n dl o c a l l y s y n c h r o n o u s ，简称g a l s ) 的时钟模式。 集成度的提高增加了片上资源数量，全局控制系统需要保留所有部件的状 态，通信负载的全局控制变得更加困难。全局通信更需要在几乎没有全局协作的 前提下，分布式地进行。传统的片上总线互联结构可扩展性差且无法提供高带宽， 因此有研究者提出片上网络这种新型片上互联结构1 6 6 ，6 7 】。 为满足计算集中性等超大规模应用程序的需求，应用程序分成多个线程在同 一芯片内并行执行，片上计算资源如c p u ，d s p ，专用i p 的数量增加，从而造 成计算资源之间通信量的增加。传统片上系统s o c 大多采用共享总线互联结构， 这种互联方式需要在多个申请中进行总线仲裁，保证总线串行使用，优点是开销 低实现简单，缺点是可扩展性不好且带宽低。新的通信要求互联结构能够提供可 扩展的带宽，片上包交换微型网络能够满足这一需求。 n o c 用于片上模块间通信，主要具有下列特有属性i l j ： 1 ) 模块化设计，分离通信与计算； 2 ) 避免全局性的、集中的通信控制； 3 ) 允许可变的终端数目： 4 ) 在拓扑结构支持下，具有可扩展性； 5 ) 不宜使用跨越整个芯片的全局长连线； 6 ) 用户可定制的，如线宽、b u f f e r 大小、拓扑结构等； 7 ) 允许多种电容和多种时钟频率： 8 ) 顺序传送数据； 9 ) 支持系统测试。 n o c 结构类似于大规模多处理器与分布式计算网络。过去几十年中，网络已 经形成一个成熟的研究领域，有着完整的研究体系与完备的研究成果，但对于 2 第l 章绪论 n o c ，目前常用的网络配置与实现都过于复杂或开销太大，难以在片上实现。为 了使n o c 满足经典s o c 或多核处理环境的要求，网络的基本模块化技术，如流控 逻辑，路由算法，数据包定义等都需要朝着l i 曲t 、e i 曲t e d 这一特征发展，从而使 得n o c 的v l s i 实现成为可能1 4 引。 由于n o c 与传统计算机网络有上述差异，传统计算机网络的成熟技术大多不 适合n o c ，针对n o c 的资源开销限制，设计更适合n o c 的网络结构具有重要意义， 这正是本文的研究目标。 1 2 研究现状 n o c 设计的几种关键要素有：拓扑结构、路由算法、路由器结构、流控机制 等，其中路由器结构又可以划分为b u 疵r 模块、调度模块、互联模块。 拓扑结构决定片上各i p 模块通过路由器相互连接的方式，拓扑结构的选择直 接影响布局布线的复杂度与网络的理想吞吐量，因此是片上网络设计非常重要的 一部分，常用的拓扑结构有2 dm e s h ，f a tt r e e ，t o r u s 等。m e s h 结构容易在片上实 现，但无法提供高性能：t o r u s 结构的理想带宽与吞吐量很高，但由于有长连线， 难以在二维片上实现；f a t t r e e 结构的节点间距离比较短，但容易在根部出现拥塞 现象。因此针对片上网络设计新的拓扑结构是很有必要的。 路由算法决定通信数据包在拓扑结构中从源节点到目标的路径，路由算法的 选择影响网络潜在性能能否得到发挥，主要分为确定性算法( d e t e n n i n i s t i c ) ，健忘 性算法( o b l i v i o u s ) ，自适应算法( a d a p t i v e ) 等，确定性算法和健忘算法的特征是实 现简单且容易避免死锁，如d o r ，r o m m ，0 1 t u r n ，自适应算法的实现逻辑 较为复杂，但通常性能更好，好的自适应算法能够平衡网络负载并提高吞吐量。 对于片上网络，路由算法不能太复杂，否则会导致实现时开销太大。 流控机制( n o wc o n t r o l ，o rs w i t c h i n gt e c t u l i q u e ) 决定数据包的划分方法和路由 器与连线资源的分配方式，主要分为电路交换机制和包交换机制，其中包交换机 制又包括存储转发、虫孔、虚通道交换等。流控机制主要是管理连线、b u 疏r 等 资源，对于通信性能与功耗面积等开销影响较大。 路由器结构主要分为b u 航r 模块，互联模块，仲裁调度模块。路由器b u 仃e r 类型决定路由器内存储空间的具体数量和访问方式，按照b u 能r 位置与结构不同 可以分为输入队列，输出队列，交叉点队列，共享队列等。调度算法( m a t c h i n go r s c h e d u i i n ga l g o r i t h m ) 决定各个输入端口的数据片从输出端口的离开顺序，片上路 由器的交叉开关根据自己的b u 能r 结构类型选择合适的匹配算法。目前已经存在 的n o c 实例有压t h e r e a l 【7 】，m a n g o f 4 5 1 ，x p i p e s l 4 4 】等。 3 第j 章绪论 详细的研究现状见本文第二章。 1 3 技术路线与本文贡献 研究方法主要是针对网络的各种性能标准，分别采用不同的方法解决。然后 从一些特殊问题中归纳出一些基础问题，再提出相应的理论并设计对应的技术， 具体表现为： ( 1 ) 在研究过程中，首先针对n o c 低功耗、高带宽、面积功耗限制严格的特 点，认识到在n o c 中应该严格限制硬件实现复杂度，才能降低面积和功耗开销， 对拓扑结构、路由算法、路由器b u 骶r 结构、路由器调度算法等展开了详细而系 统的研究。 ( 2 ) 将某些特定问题作为结构设计的突破口，如在网络中经常出现的拥塞现 象拥塞的原因一部分是因为网络内部的b u 艉r 容量有限，另外就是b u 艉r 和连 线的利用率问题，再者就是因为热点过分集中导致一部分节点过分繁忙，针对这 些问题的原因我们设计了自己的几种路由器调度算法与路由算法。 文中采用的研究实验平台主要是p o p n e t 网络模拟器与g o d s o n 用户级多核模 拟器。p o p n e t 模拟器实现一个k a r yn c u b e s 拓扑结构，路由器采用五级流水，可 以输入任何负载文件进行性能分析。g o d s o n 多核模拟器采用c m p 结构，它的访 存结构为分布式共享存储，各个处理器核的二级c a c h e 分别映射到不同的访存地 址空间段，增大二级c a c h e 空间，同时也带来较多的核间通信开销，每个l lc a c h e 可能包含所有l 2c a c h e 的内容，而不仅仅局限于本地l 2c a c h e ；使用基于目录的 c a c h e 一致性协议，目录包含在l 2c a c h e 中；支持路由器使用多个虚通道；使用 r - o u n dr o b i n 的仲裁策略和基于c r e d i t 的流控措施。详见本文第三章。 本文的研究内容主要分为片上网络的结构设计与性能分析两大部分。其中结 构设计主要包括拓扑结构设计、路由器调度算法设计、路由算法设计等，主要针 对现有经典网络技术在片上网络应用的不足，如过于复杂或实现开销太高等问 题，设计新的网络结构与算法弥补其缺点：性能分析主要分析现有的经典网络设 计之间的性能优劣，如调度算法、路由算法、流控机制等，从而得到一些有用的 结论，方便研究者的设计选择。 本文贡献主要包括三部分：1 ) 基于经典拓扑结构提出三种新型拓扑结构 x m e s h ，s t o r u s 和r g r i d ，适用于中小规模的片上网络，其中x m e s h 结构与t o r u s 相 比可减少延时2 0 ，s t o r u s 结构更适用于热点负载，r g r i d 结构具有可扩展性好、 带宽高、节点间平均距离小、物理实现难度低等优点：2 ) 为减轻片上网络通信 过程中的拥塞问题，设计新的调度算法和路由算法，调度算法分别是仃d i s t ， 4 第1 章绪论 仃p a i l l ，r r - a l ，分别使用不同的仲裁基准进行轮询仲裁，能够降低热点通信负载 的最大延时和平均延时，路由算法基于蚁群算法，称为a j l l m u t i n g ；3 ) 分析评估 传统网络结构与算法的优缺点，取得一些经验性的结论。 1 4 论文结构 本文主要由三大部分组成，第一部分主要包括国内外研究现状、研究背景、 研究平台，即第一章、第二章和第三章；第二部分内容为n o c 结构设计，对应第 四章和第五章；第三部分是性能分析与论文总结，包括第六章和第七章。 具体内容共分为七章。第一章为绪论，主要介绍本文的研究目标。第二章主 要介绍n o c 领域的研究内容和国内外研究现状，按照研究内容不同分为多个小 节，包括路由器结构、拓扑结构、路由算法、流控机制、性能评估与测试程序、 模拟平台、低功耗设计等。第三章介绍本论文使用的两个模拟器，一个是p o p n e t 网络模拟器，由c + + 实现，实现虚通道流控机制，可以输入通信负载流进行模拟， 模拟结束后可以得到所有输入数据包的平均延时，另外一个模拟器是由中科院计 算所微处理器中心几位同学实现的一个基于龙芯的单片多处理器用户级模拟器， 其中实现了m e s h 结构的片上互联设计，可以在该模拟器上面运行s p l a s h 2 程序并 得到详细的性能、功耗、面积等结果。 第四章内容是拓扑结构设计，包括x m e s h ，s t o m s ，r 鲥d 三种新型拓扑结构 及其路由算法，x m e s h 结构基于m e s h 结构，s t o m s 拓扑结构类似于t o l l j s ，r 鲥d 是一种可扩展低延时的拓扑结构，这三种结构与传统的m e s h ，t o r u s 结构相比， 主要特征是增加或改动了一些互联边，以适当的硬件复杂度为代价，减小了通信 延时。第五章是路由器结构内的模块设计，即仲裁调度算法模块、b u 腩r 模块、 路由模块，包括三个基于r o 姐d 。r o b i n 的调度算法、一个动态分配路由器b u 骶r 空 间的算法、一个基于蚁群算法的路由算法。 第六章对经典网络结构进行性能比较与评估，分析路由器的b u 彘r 结构及其 算法对于性能的影响，其中第一节主要分析b u 髓r 深度、虚通道个数对性能的影 响，比较多个虚通道与v o q 结构的性能差异，在多虚通道结构上实现i s l i p ，p i m ， o c f ，l q f ，l p f ，随机匹配等共六种输入输出匹配算法并分析它们性能的优劣； 第二节基于m e s h 和t o m s 结构实现了了x y ，o d d e v e n ，o l t u r n ，t x y ，m 烈a d ， g o a l 六种路由算法，并使用热点、矩阵转置、b i tc o m p l e m e n t 、均衡负载四种模 式作为输入负载模拟分析这六种路由算法的性能；第三节在我们的用户级模拟器 上分析了存储转发和虫孔两种流控技术的性能与功耗开销，结果显示虫孔流控技 术能够在损失很少性能的前提下节省大量的功耗。第七章对本文作出总结。 5 第2 章国内外研究现状 第2 章片上网络研究现状及关键技术 与传统计算机网络相似，n o c 也有路由器、路由器问链路、路由机制与协 议、流控机制等基本组成部分。n o c 与计算机网络的区别首先在于规模，计算机 网络的规模可以是一个房间，也可以扩展到整个地球，而n o c 的规模则受限于 一个狭小的硅片，因此n o c 的计算和存储限制要严格得多。由于占用面积限制， 片上的存储空间是十分珍贵的，因此n o c 只能拥有有限数量的b u m r 。在计算机 网络中，每个处理器都会安装一个n i c m e 似o r ki n t e r f a c ec a r d ) ，用来实现一部分 协议栈，对于n o c ，这种实现是不可能的，因为它的维数是受限的。n o c 经常用 于便携设备，它的功耗限制也十分严格。为了减少功耗，n o c 设计应尽量避免 或完全杜绝复杂的计算逻辑和通信部件。 另外一个显著的区别是，n o c 的连线比较充足，一个典型的点到点的n o c 可以用3 0 0 - b i t 的连线来提供大量的带宽。同时n o c 的连线足够短，方便部件间 同步。另外n o c 的通信协议可变性比较强，因为在n o c 上实现t c p 那样复杂的 机制是不太可行的。 近年来n o c 的研究热点主要集中于：功耗评估与低功耗设计【6 8 ，6 9 ，7 0 1 、路由 器结构设计【7 1 ，7 2 1 、实现与测试方法【7 3 ，7 4 1 、容错机制3 1 ，3 6 ，7 5 1 等，与n o c 设计相 关的关键技术有路由器设计、拓扑结构设计、路由算法设计、路由器间连线的布 局布线等。这些技术以前主要应用于大规模并行系统，但片上系统与大规模并行 系统的设计标准差距很大，设计时要考虑功耗，面积，物理实现难度等等。由于 数据线更细，片上系统可以在同样面积内布置更多线，得到更高的带宽；片上系 统要求通信延时跟时钟周期处于同一数量级，需要更低的通信延时，同时路由器 结构不能过于复杂，拓扑结构的设计要充分考虑布线的实现难度。 由于目前的成熟网络技术不太适合n o c 这种新生概念，设计一个适用于 n o c 特征，能够提供低延时、高带宽，物理实现难度不高的n o c 系统有重要意 义目前n o c 的研究内容可以分为如下几个方向。 本章主要介绍了当前片上网络的研究现状与结构设计的关键技术，片上网络 的研究内容可以分为拓扑结构、路由算法、路由器结构、性能分析、功耗评估与 设计等几个大方向，其中路由器结构设计又包含调度算法、流控机制、b u 艉r 结 构等。本章的每个小节对应一个研究方向，对这些研究方向的研究进展作了详细 介绍。 第2 章国内外研究现状 2 1 路由器结构 路由器( r o u t e ro rs 嘶t c h ) 是网络互连的基本部件。主要由三部分构成：i ) 输 入输出端口之间的互联模