（计算机软件与理论专业论文）片上网络路由算法关键问题研究.pdf

片上网络路由算法关键问题研究摘要 论文题目：片上网络路由算法关键问题研究 专业：计算机软件与理论 博士生：唐名华 指导教师：林小拉教授 摘要 随着半导体工艺的不断发展，单个芯片上集成的晶体管数量将越来越多。届时， 它们将被组合成上千个各自独立又相互通信的处理单元。为了充分利用它们的处理能 力，需要高效的通信结构来完成它们之间的通信。传统的连接这些处理单元的总线结 构在功耗、延迟、同步、线路可靠性以及带宽等方面很难适应新的需要。为了满足片 上系统的通信需要，研究者提出了片上网络( n e t w o r k o n - c h i p ，n o c ) 的通信架构， 并从多个方面阐述了以片上网络代替总线通信结构的必要性。 片上网络与通用的计算机网络一样，也采用分层的体系结构。片上网络的设计包 括拓扑结构、路由算法、交换技术、流控制策略等方面。但是，由于片上网络是在单 个芯片上实现的微型网络，所以它的设计有区别于通用计算机网络的独特的地方。因 为片上网络结构需要与同一个芯片上的计算单元竞争空间，所以，片上网络所占的面 积必须尽可能小。同时也需要尽量减少它的功耗开销。 研究者对适用于片上网络的各种拓扑结构进行了广泛的研究。网格( m e s h ) 结构 由于具有结构简单、容易实现、可扩展性好等方面的优势得到最多的关注。在交换技 术方面，虫孔( w o r m h o l e ) 交换技术由于需要较少的缓存空间，并且数据包延迟较 小，所以适合在片上网络中应用。本论文主要研究采用网格结构和虫孔交换技术的片 上网络的路由算法相关问题。 本文具体内容分为三大部分：第一部分为第一章和第二章，主要内容为绪论和相 关研究；第二部分为第三章到第五章，主要介绍关于路由算法的三个研究成果；第三 部分为第六章、第七章以及结语部分，介绍了两种流控制策略和论文总结。 一i 片上网络路由算法关键问题研究 摘要 本文的主要研究成果如下：首先，提出了一种为特定应用计算路由的算法 ( r a b c ) 。r a b c 方法通过打破信道依赖图中所有的圈来确保得到的路由算法不会形 成死锁。由它得到的路由算法具有较高的自适应度，且性能不依赖于它打破这些圈的 顺序。同时r a b c 算法的计算复杂度仪为d ( 佗) 。 其次，提出了一种减少路由表查询次数的方法( r q r t ) 。在基于表格实现的路由 中，为了降低数据包延迟，从而提高系统性能，需要对路由表的查询方法进行改进。 由于网格结构比较规则，从而为其生成的路由表也有一定的规律可循。r q r t 方法充分 利用网格拓扑结构路由表的规律特性，减少了5 0 的路由表查询次数，极大地提高了系 统的性能。 第三，提卜h 了a n o p 选择策略。当路由算法计算出多个输出端口时就需要选择策略 从中选择一个恰当的输出端口。a n o p 选择策略能公平地选择所有由路由算法计算出的 输出端口，使流量在网络中均匀分布，从而能够充分利用网络资源，提高系统性能。 第四，提出了注入水平流控制策略( i l f c ) 。在该流控制策略中，源节点发送数 据的速率被划分成若干个水平( i n j e c t i o nl e v e l ) 。然后源节点在发送数据的时候根据 网络的状态自动选择最大且不会使网络发生拥塞的注入率水平。模拟结果表明，应用 了i j f c 流控制后，片上网络就会运行在比较平稳的状态，不再发生拥塞。 第五，提出了四分之一负载门限( q l t ) 流控制策略。通过记录网络的状态，我 们发现，为了避免片上网络进入一种恶性拥塞状态，网络的负荷存在着一个门限值 ( 具体为路由器缓存空间的四分之一) 。当网络的负载低于该门限值时，网络中就不 会出现拥塞。反之，当网络的负荷超过该门限值时，网络中就会出现严重的拥塞。而 且该门限值规律在网络的局部范围内仍然起作用。根据这个发现，我们设计t q l t 流 控制策略。它基本思想是记录路由器被占用的缓冲区的总和，如果它超过了指定门限 值，则认为该路由器所在的路径已经发生拥塞了，应该推迟向该路径发送数据。否则 认为该路径没有发生拥塞，可以继续发送数据。 关键词：片上网络、路由算法、流控制策略、路由表、选择策略 片上网络路由算法关键问题研究 a b s t t a c t t i t l e ： m a j o r ： n a m e ： r e s e a r c ho nk e yi s s u e so fr o u t i n ga l g o r i t h m si nn e t w o r k - o n c h i p c o m p u t e rs o f t w a r ea n dt h e o r y m i n g h u at a n g s u p e r v i s o r ：p r o f e s s o rx i a o l al i n a b s t r a c t a st h es e m i c o n d u c t o rt e c h n o l o g ys c a l e s ，m o r ea n dm o r et r a n s i s t o r sa r ei n t e g r a t e d i n t oa s i n g l ec h i p t h e ya r eo r g a n i z e di n t ot h o u s a n d so fp r o c e s s i n ge l e m e n t s ( p e s ) w h i c h a r ei n d e p e n d e n ta n dc o m m u n i c a t ew i t he a c ho t h e r a ne f f i c i e n tc o m m u n i c a t i o na r c h i - t e c t u r ei sn e c e s s a r yt of u l l yt a k ea d v a n t a g eo ft h e i rc o m p u t a t i o np o w e r t h et r a d i t i o n a l b u s - b a s e ds t r u c t u r ec a nn o ts a t i s f yt h en e wr e q u i r e m e n ti np o w e rc o n s u m p t i o n ，d e l a y , s y n c h r o n i z a t i o n ，s i g n a li n t e g r i t ya n db a n d w i d t h ，e t c t h er e s e a r c h e r sa l lo v e rt h ew o r l d p r o p o s e dt h en e t w o r k - o n - c h i p ( n o c ) a r c h i t e c t u r et of u l f i l lt h ec o m m u n i c a t i o nb e t w e e n t h ep e s a n dt h e ys h o ww h yi ti sn e c e s s a r yf r o md i f f e r e n ta s p e c t s n e t w o r k - o n - c h i ph a sl a y e r e da r c h i t e c t u r ea n dd e s i g n i n gi nn o ci n c l u d e sa l lk i n d s o ft a s k 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 ga n df l o wc o n t r o l ，j u s tl i k ei nt h eg e n e r a l n e t w o r k s i n c en o ci sat i n yn e t w o r ko nas i n g l ec h i p ，s o m es p e c i a lr e q u i r e m e n t sd i f f e ri t f r o mt h eg e n e r a ln e t w o r k s p e c i f i c a l l y , t h ea r e ao v e r h e a da n dp o w e rc o n s u m p t i o no ft h e n o cs h o u l db ea ss m a l la sp o s s i b l e r e s e a r c h e r sc a r r yo u te x t e n s i v es t u d yo nt h et o p o l o g yo ft h en o c m e s ht o p o l o g y i ss t u d i e dm o r et h a no t h e r ss i n c ei t i ss i m p l et oi m p l e m e n ta n dh i g h l ys c a l a b l e a sf o r s w i t c h i n gt e c h n i q u e ，t h ew o r m h o l es w i t c h i n gi ss u i t a b l et ot h en o c ，b e c a u s ei tr e q u i r e s l e s sb u f f e rs p a c ea n dd e c r e a s e st h ep a c k e tl a t e n c y t h i sp a p e rm a i n l ys t u d i e st h er o u t - i n ga l g o r i t h mr e l a t e di s s u e si nn o cw h i c hh a sm e s ht o p o l o g ya n dw o r m h o l es w i t c h i n g t e c h n i q u e t h i sp a p e ri so r g a n i z e da sf o l l o w s ：i nt h ef i r s tp a r tw h i c hi n c l u d e st h ec h a p t e r1a n d i i i 片上网络路由算法关键问题研究 a b s t r a c t c h a p t e r2 ，w em a i n l yp r e s e n tt h ei n t r o d u c t i o na n dr e l a t e dw o r k t h es e c o n dp a r tr a n g e s f r o mc h a p t e r3t oc h a p t e r5 t h r e ea l g o r i t h m sr e l a t e dw i t hr o u t i n ga r ep r o p o s e di nt h e p a r t t w of l o wc o n t r o ls t r a t e g i e sa r ei n t o d u c e di nc h a p t e r6a n dc h a p t e r7r e s p c c t i v e l y t h et w oc h a p t e ra n dt h ec o n c l u s i o nc h a p t e ra r et h et h r e ep a r to ft h ep a p e r t h i sp a p e rp r o p o s e df i v es t r a t e g i e sr e l a t e dw i t hr o u t i n gi nn o c t h ef i r s ti sr a b c w h i c hi sam e t h o d o l o g yt od e s i g nr o u t i n ga l g o r i t h mf o rs p e c i f i ca p p l i c a t i o n r a b cb r e a k s a l lt h ec y c l e si nt h ea p p l i c a t i o ns p e c i f i cc h a n n e ld e p e n d e n c yg r a p ht oa v o i dd e a d l o c k t h e r o u t i n ga l g o r i t h mr e t u r n e db yr a b ch a sh i g hr o u t i n ga d a p t i v i t y t h ep e r f o r m a n c eo f t h er o u t i n gf u n c t i o nd o e sn o td e p e n do nt h eo r d e rt ob r e a kt h ec y c l e s m o r e o v e r ，t h e c o m p u t a t i o n a lc o m p l e x i t yo fr a b c i so n l yd ( n ) s e c o n d l y , w ep r o p o s eat e c h n i q u ew h i c hi st e r m e dr q r tt or e d u c eq u e r y i n gt h e r o u t i n gt a b l e i nt h et a b l e - b a s e dr o u t i n g ，t h em e t h o dt oq u e r yr o u t i n gt a b l en e e d st ob e c a r e f u l l yc o n s i d e r e dt od e c r e a s ep a c k e tl a t e n c y t h em e s ht o p o l o g yi sh i g h l yr e g u l a r ，s oi s t h er o u t i n gt a b l ef o ri t r q r tf u l l yt a k e sa d v a n t a g eo ft h er e g u l a r i t yo fr o u t i n gt a b l ef o r m e s ht od e c r e a s eu pt o5 0p e r c e n to fq u e r y i n gt a b l e c o n s e q u e n t l y , s y s t e mp e r f o r m a n c e i ss i g n i f i c a n t l yi m p r o v e d t h i r d l y , w ep r e s e n tt h ea d v a n c e dn o p ( a n o p ) s e l e c t i o ns t r a t e g y s e l e c t i o ns t r a t e g y i sc a l l e dt oc h o o s eo n es u i t a b l eo u t p u tc h a n n e lf r o mt h es e tr e t u r n e db yt h er o u t i n g a l g o r i t h m a n o ps e l e c t i o ns t r a t e g yg i v e sf a i rc h a n c et oe a c ho u t p u tc h a n n e lc o m p u t e d b yt h er o u t i n ga l g o r i t h m i tm a k e st h et r a f f i cu n i f o r m l yd i s t r i b u t e di nt h en e t w o r ka n d t h en e t w o r kr e s o u r c ef u l l yu s e d t h ef o u r t hs t r a t e g yo ft h ep a p e ri st h ei n j e c t i o nl e v e lf l o wc o n t r o l ( i l f c ) s t r a t e g y i nt h ei l f cs t r a t e g y , t h er a t eo fi n j e c t i n gp a c k e t si n t ot h en e t w o r kb yt h es o u r c en o d ei s c l a s s i f i e di n t os e v e r a ll e v e l s t h es o u r c en o d ea d a p t i v e l yc h o o s e st h eh i g h e s tl e v e lw h i c h d o e sn o tc o n g e s tt h en e t w o r k s i m u l a t i o nr e s u l t ss h o wt h a tt h en e t w o r kr u ns m o o t h l y a n dc o n g e s t i o nd o e sn o to c c u ra n ym o r ea f t e rt h ei l f ci sa d o p t e d t h el a s to n ei st h eq u a r t e rl o a dt h r e s h o l d ( q l t ) f l o wc o n t r o ls t r a t e g y t h r o u g h t r a c i n gt h en e t w o r ks t a t u s ，w ef o u n dt h a tt h en e t w o r kp a y l o a dh a sat h r e s h o l dt oa v o i d i v 片上网络路由算法关键问题研究 a b s t r a c t s e r i o u sc o n g e s t i o ni nt h en e t w o r k s p e c i f i c a l l y , t h et h r e s h o l di st h eq u a r t e ro ft h en e t w o r k b u f f e rs p a c e n oc o n g e s t i o nw i l lo c c u ri ft h en e t w o r kp a y l o a di sl o w e rt h a nt h a tt h r e s h o l d ， o t h e r w i s et h en e t w o r kw i l lb es e r i o u s l yc o n g e s t e d f u r t h e r m o r e ，t h el a wi ss t i l lh o l di na l o c a lr e g i o no ft h en e t w o r k t h eq l tf l o wc o n t r o ls t r a t e g yi sb a s e do nt h i sl a w i t sb a s i c i d e ai st or e c o r dh o wm u c ho ft h ew h o l eb u f f e rs p a c eo fe a c hr o u t e ri so c c u p i e d i fi ti s b e y o n dt h et h r e s h o l d ，t h e nt h ep a t hc o n t a i n i n gt h er o u t e ri sc o n s i d e r e dt ob ec o n g e s t e d a n ds e n d i n gd a t at ot h a tp a t hs h o u l db ed e l a y e d o t h e r w i s e ，t h ep a t hi sf r e ea n dt h e d a t ac a nb es e n t k e yw o r d s ：n e t w o r k - o n - c h i p ；r o u t i n ga l g o r i t h m ；f l o wc o n t r o ls t r a t e g y ；r o u t i n gt a b l e ； s e l e c t i o ns t r a t e g y v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行 研究工作所取得的成果除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的作品成果对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明本人完全意识到本声明的法 律结果由本人承担 学位论文作者签名：熏鱼竺 日期：鲨! 竺：6 ：生 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版， 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、 院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以 采用复印、缩印或其他方法保存学位论文 学位论文作者签名褥 日期：沙l j 口年6 月午e t 导师签名： 批。影 、1 日期：劢脾么月卢日 片上网络路由算法关键问题研究第1 章前言 第1 章前言 片上网络( n o c ，n e t w o r k - o n - c h i p ) 是随着芯片集成度的不断提高而逐步兴起 的。本章首先分析了用片上网络替代传统总线连接的必要性，讨论论文的选题意义。 然后按照时间顺序比较详尽地总结了片上网络概念从出现到成熟的过程。并对在此过 程中各研究团体提出的一些片上网络原型进行了简单的介绍。接着提纲挈领地归纳了 本论文的研究成果。最后给出了论文的组织结构。 1 1 课题背景及其意义 根据国际半导体技术路线图( i n t e r n a t i o n a lt e c h n o l o g yr o a d m a pf o rs e m i c o n d u c t o t s ，i t r s ) 1 1 中的预测，至u 2 0 1 8 年，单个芯片上集成的晶体管数量将达至u 2 5 6 0 亿个。 为了应对这样复杂的局面，微电子设计方法学经历了从时序驱动的设计( t i m e - d r i v e n d e s i g n ，t d d ) 到基于模块的设计( b l o c k - b a s e dd e s i g n ，b b d ) 到基于平台的设计 ( p l a t f o r m - b a s e dd e s i g n ，p b d ) 的发展过程【2 1 。届时，如此众多的晶体管将被划分 成成百上千个处理元素( p r o c e s s i n ge l e m e n t ，p e ) 或者i p 模块1 。这些处理元素包 括c p u 核、d s p 核、视频芯片以及高带宽的输入输出模块等。把芯片上所有的处理元 素互相连接起来而形成一个片上系统( s y s t e m o n - c h i p ，s o c ) 。 片上系统( s o c ) 中处理元素之间的通信效率必须得到保障才能使它们能够并行运 行，从而充分利用处理元素的计算能力。因此，片上系统的设计也从以计算为中心转 向以通信为中心【3 ，4 】。常用的系统互连结构为总线结构。连接在总线上的所有处理元素 以分时复用的方式共享总线。当系统中集成的处理元素较少时，共享总结互连结构是 一种高效的通讯方式。但是，当集成电路的生产工艺进一步缩小，片上系统越来越复 杂时，总线互连在功耗、延迟、时钟同步、信号完整性以及带宽等方面已不能满足新 的需要。具体表现在： ( 一) 、全局连线增加了系统的功耗 1 p e ( p r o c e s s i n ge l c m c n t ) 矛 i i pb l o c k 这两个概念在文献中经常用到，使用时可不加区分。 1 一 片上网络路由算法关键问题研究第1 章| j 肓 功耗对于大规模的片上系统( s o c ) 有着决定性的意义。一方面，需要优化设计以 减少集成在单个芯片上的数量众多的处理元素的功耗。另一方面，互连线路的功耗也 要给予着重考虑。但是，由于总线是全局连线，所以传输单位信号穿越全局总线需要 消耗更多的功耗。所以，总线结构增加了系统中互连线路所占的功耗份额。 ( 二) 、连线延迟超过门延迟，且差距逐渐扩大 导线电阻随着半导体工艺特征尺寸的缩小而不断增大，而导线电容却相对保持不 变，结果是连线延迟不断增加。而门延迟缺有逐渐降低的趋势。因此，到达一定的临 界点后，导线延迟将会超过门延迟【5 】5 。根据国际半导体技术路线图( i t r s ) 【1 】中的预 测，它们之问的差距将会逐渐增大，形成一个剪刀差。减少连线延迟的有效方式是把 长连线分成若干段，然后在段与段之间插入中继器【5 ，6 】。虽然，连线延迟可以通过添加 中继器的方式得到一定程度的减少，但是，它和门延迟仍然有一定的距离【1 】。另一方 面，中继器增大了系统的功耗开销，这就限制了中继器的使用。 ( 三) 、全局时钟同步越来越困难 总线需要跨越整个芯片，所以全局同步信号也需要在整个芯片范围内传播。但 是，一方面，连线延迟逐渐增大；另一方面，时钟周期越来越短；同步信号通过整个 芯片需要几个甚至数十个时钟周期。在这种情况下，要实现全局同步因需要耗费较大 的面积和功耗开销而变得非常困难。 为了应对日益复杂的设计问题，新的微电子方法学要求尽可能复用已经设计好的 模块。但是，新旧模块的时钟周期是不一样的，因此，要在全局同步这些复杂多变的 模块也是很困难的。 为了克服同步难题，研究者提出了全局异步局部同步( g l o b a l l ya s y n c h r o n o u s l o c a l l ys y n c h r o n o u s ，g a l s ) 的设计方案【7 】。根据g a l s 设计方案，整个芯片被划分成 若干个模块，模块内部采用同步通信，而模块间采用异步通信。g a l s 的优点是避免时 钟歪斜( s k e w ) 问题的同时可以减少系统的功耗。 ( 四) 、不可靠线路对全局连线影响更大 在深亚微米时代( d e e ps u b m i c r o ，d s m ) ，导线间的电容和电感耦合噪声随着工 艺水平提高不断增加【6 】。增大的噪声信号极大地干扰了信号的传输，不可靠的线路降低 了信号完整性。这对长连线的影响特别严重【6 】。为了保证信号的完整性，需要特别的技 一2 - 片上网络路由算法关键问题研究 第1 章前言 术。区分信号( d i f f e r e n t i a ls i g n a l i n g ) 是一种有效的克服噪声的技术【8 】。但是，它的缺 点是增加了系统的功耗。 ( 五) 、总线提供的带宽难以满足新的需要 总线是一种共享介质的传输媒介，在一个时刻只能被一个设备独占。当连接到总 线的设备需要传输数据时均要向仲裁机构提出申请，然后由仲裁机构根据一定的规则 裁决由某一个设备获得总线的使用权。在它使用期间，总线被它独占，其它设备被阻 塞直到总线空闲，然后重新竞争总线的使用权。 从两个方面可以看出共享总线不能适应新的发展。首先，从需求方面来讲，连接 到总线并需要使用总线的设备不断增多。同时，设备需要的带宽也在提高( 由于问题 规模越来越大等原因) 。其次，从供给方面来讲，可扩展性较低的总线不能随着需 要变化提供更高的带宽。一是因为总线的宽度有一定的限制；二是因为在深亚微米 ( d s m ) 工艺下全局连线的时钟频率也受到严格限制【9 ，1 0 l 。 所以，随着半导体工艺不断进步，当越来越多的设备集成到单个芯片的时候，总 线结构就会带来两个问题。一是每个处理元素得到的有效带宽就会越来越小，甚至不 能满足需要。二是不同的通信不能并行进行，这就使得各个任务不能并行执行。等待 通信的处理单元将会出于空闲状态，这实际上降低了系统的利用率。 1 2 片上网络的提出 从上一节我们看到，总线互连结构已经不能适应新的形势发展。从2 0 0 0 年开始， 陆续有研究者提出了用新的可扩展的互联结构代替共享总线结构。一种新的片上系统 互连结构片上网络( n o c ，n e t w o r k - o n - c h i p ) 应运而生。 p g u e r r i e r 等在文【1 0 】中首先指出随着半导体工艺的发展，单个芯片对带宽的要求 可能超过5 0g b i t s 。但是，因为信道宽度和时钟频率两个方面的限制，全局总线无 法提供如此高的带宽。他们提出了一种网络结构s p i n ( s c a l a b l e ，p r o g r a m m a b l e ， i n t e g r a t e dn e t w o r k ) 作为新的片上系统互连结构。 s p i n 采用胖树( f a t t r e e ) 拓扑结构。在s p i n 结构里，节点与节点间采用两个单 向的3 2 位数据通道。接收端设立个计数器来记录它的空闲缓冲区的数量，并把该 3 - 片上网络路由算法关键问题研究第1 章i j i f 言 数量的变化情况及时通知发送方。发送端根据对方的空闲缓冲区数量来控制发送速 度。这种策略称为以基于信用度( c r e d i t b a s e d ) 的流控制策略。数据包由一系列长度 为3 2 位的字组成，字长与数据通道的宽度相同。同时，一个字就可以包含数据包的首 部信息，加快了首部处理的速度。数据包的长度是可变的，并包含一个尾部。根据胖 树的流量特点，s p i n 的路由器的缓冲区采用了特别的设计。路由器的每个输入端口有 一个大小为4 个字的私有缓冲区，除此以外，另有两个大小为1 8 个字的共享输出缓冲 区。共享输出缓冲区可以有效减少网络拥塞，同时，它比私有输出缓冲区的面积开销 小。模拟结果表明，在严格面积约束的条件下，s p i n 能满足将来片上系统对数据包延 迟和吞吐量的要求。 w j d a l l y 等首次明确提出片上网络( n o c ) 的概念【1 1 】。并指出用片上网络代替 全局总线结构能够使片上的布线结构化，优化和控制它的电子属性。从而能够使用更 好的低功耗技术并提高信号的传输速度。另一方面，使用网络作为通信架构能够使许 多通信能够并行进行，提高系统的性能。最后，在片上网络( n o c ) 的环境下可以采用 模块化设计定义一些标准接口。标准化接口可以方便模块重用以及模块之间的通信。 文【1 1 】中同时给出了一个片上网络模型。该片卜网络由1 6 个路由器以及连接路由器 的连线组成，拓扑结构采用折叠的网格( f o l d e d - t o r u s ) 结构。功能模块就放在网格的 格子里，连接到路由器并通过路由器进行通信。格子和里而的功能模块一起称为格件 ( t i l e ) 1 。格件与路由器通过标准接口与路由器的输入输出端口相连，每个端口都 包含2 5 6 位的数据域和额外的控制域。路由器结构方面，由于这个网络采用了虚通道 ( v i t u r a lc h a n n e l ，v c ) 的流控制技术，故路由器的每个端口都分成若干个虚通道， 每个虚通道都含有独立的缓冲区和状态指示器。该文估算出路由器的面积开销只占格 件的6 6 。这对片上系统的实现是至关重要的。 该文还指出片上网络的三个重要研究方向，即拓扑结构、流控制算法以及电路， 为后来的研究者提供了研究思路。 与d a l l y 同时提出片上网络概念的还有m s g r o i 等人【4 l 。他们提出的片上网络概念 是以通信为基础的片上系统设计方法。 i t i l e 本来是指网格里的格子，在斤上网络的环境里，它连同格子里的功能模块一并代指了。所以， 本文将t i l e 译为格件，意思是它是网络的一个组成部件。从侧面强调了片上网络的模块化设计。 - 4 一 片上网络路由算法关键问题研究第1 章前言 存该文中，作者首先分析了用以通信为基础的设计方法代替传统的a d - h o e 设计方法 的必要性。因为传统方法在以下四个方面不能满足将来片上系统的需要。其一，在设 计的早期不能预测最终系统的性能，这就使得必须多次迭代才能设计出最终的产品， 延长了产品问世的时间。其二，需要跨越整个芯片的长连线的片上系统将不得不面对 延迟以及同步的方面的难题，特别是系统中包含多个时钟域的时候。其三，通信结构 包括时钟的功耗在整个系统的能耗开销中占主要份额。最后，在以后的片上系统设计 中，将会有比以前更多的选择机会。互连结构方面有总线、交叉开关以及网格等可供 选择。而要解决性能和吞吐量的平衡需要考虑流水线级数、仲裁、同步、路由等方面 的设计参数。而传统的a d h o c 设计方法却不能有效应对如此复杂的局面。 为了克服传统设计方法的局限，作者提出了称为片上网络的设计方法学。这种方 法学的本质是以通信为基础，它强调，在片上系统的设计中，把通信和计算分离，通 信与计算具有同等重要的地位。在设计片上系统通信结构的时候采用分层的方法，类 似于通信网络中的o s i 参考模型。分层设计的方法在通信网络中有着广泛的应用，它能 有效地把复杂的通信系统分解成一些小的模块，简化设计。 随后，作者提出了两种基于分层思想的设计方法：m e t r o p o l i s 方法和m e s c a l 方 法。m e t r o p o l i s 方法也可以称为基于适配器的方法。如果通信双方在语法或语义上有分 歧，则设计恰当的适配器来使它们兼容。它的设计过程分为两步。第一步，设计者描 述( 或从i p 库里选择) 计算模块，第二步，用严格逐步求精的方法设计计算模块之间 的通信。它在逐步求精的过程中会得到一个分层的体系结构，但是，它并不以某种特 定的计算或通信模型为基准。根据需要，层与层之间用适配器来协调。m e s c a l 方法 的目标是建立一个编程模型和一个软件开发环境，以期可以快速在一系列充分可编程 体系结构上高效实现一组应用。它的基本思想是为一个领域实现一个可编程的解决方 案。然后就可以方便地为这个领域里的应用得到满足其性能需求的设计。它同样把整 个系统分为计算和通信两个模块。通信任务的设计是通过实现基于o s i 参考模型的通信 体系结构来完成的。 随后，l b e n i n i 和g d em i c h e l i 在文【1 2 】中指出了片上网络出现的必要性，并详 细解释了片上网络分层体系结构各层的功能及其技术难点。 随着技术的进步，系统芯片将变得越来越复杂。芯片系统设计者将面临以下一些 5 片上网络路由算法关键问题研究第1 章前言 挑战：其一，无论对性能还是功耗，物理连接都将成为制约因素。其二，很难在一个 时钟周期内同步芯片，同时，时钟歪斜也难以避免。因此，全局异步，局部同步的设 计思路也被提出。其三，全局连线跨越几个时钟域带来的i 司步错误和由电子噪音带来 的数据错误等两类错误造成不可靠的线路传输，另外，高层次抽象、粗粒度和分布式 通信控制也会带来一些不确定的因素，这使得用一些确定操作模型来描述系统的功能 更加困难。为此，作者提出了用分层的可配置的微型网络来获得高效的”上系统通 信。并可借鉴通用网络的设计方法和工具。 片上网络与普通网络不同在于它有严格的功耗限制和不同的设计规格。随着片上 设备的尺寸越来越小，全局通信却需要消耗更多的能量。所以，减少功耗是将来的设 计者要考虑的主要因素之一。而片上网络的设计者在设计的时候由于不需要考虑与现 有标准和旧版设备兼容，所以可以从零开始为一个或一组应用定制网络通信结构。因 此，作者提出了一种垂直的设计流程，整个体系结构分为若干层，每一层都可以根据 应用领域特制和优化。 作者提出的微型网络体系结构分为三个大的层次，从下到上为：物理层、体系结 构和控制层以及软件层。物理层的设计重点在于减少各种错误的同时，提高通信的速 度和减少能耗。体系结构和控制层分为两部分：体系结构和控制。体系结构指明指明 网络的体系结构，即网络的拓扑结构以及物理组织。而控制层则控制网络的运行。控 制层又分为三个小层次：从下到卜依次为：数据链路层、网络层以及传输层。数据链 路层主要是在不可靠的物理线路上提供可靠的数据传输。它的重点在于性能和功耗之 间的平衡。网络层的功能是实现源端到目的端的传输控制。它的重点在于求得可预测 性与平均性能、路由器复杂度和速度与可获得的信道利用率以及健壮性与进取性等三 个平衡。传输层的作用是在源端将消息打包，然后在目的端将数据包重新组装成消 息。它的重点在于控制好打包的粒度。软件层包括系统软件和应用软件。系统软件包 括一些操作系统例程。提供动态电源管理( d y n a m i cp o w e rm a n a g e m e n t ，d p m ) 和动 态信息流管理( d y n a m i ci n f o r m a t i o n - f l o wm a n a g e m e n t ，d i m ) 是系统软件的重点。 应用软件的重点在于能够在不同的平台之间移动以及充分考虑下层平台的分布性特 点。 p w i e l a g e 等研究者通过分析技术进步指出了片上网络结构出现的必然性 6 】o 并给 - 6 片上网络路由算法关键问题研究 第1 章前言 出了片上系统对片上网络的性能方面的要求。 该文指出摩尔定律( m o o r e sl a w ) 在相当长的时期内仍将起作用。在单个芯片上 集成的晶体管数量不断增多将导致复杂的片上系统( s y s t e m so ns i l i c o n ，s o s ) 出现。 片上系统由许多处理节点构成，处理节点本身的复杂度不会越来越大，但是，系统中 处理节点的数量却会不断增多。连接这些处理节点的互连结构在整个系统中的开销将 增大，并影响系统的整体性能。 在深距微米( d s m ) 技术时代，互连结构的设计将面对功耗、信号完整性和信号 传输延迟等三个方面的挑战。但是，流行的总线互连结构由于采用了全局连线，所以 在这几个方面均有困难。而且，总线结构可扩展性较差。随着连接到总线的节点的增 多，每个节点得到的平均带宽将减少，而总的带宽又随着负载的增多和线路的延长而 减少。因此，新的j | 上系统互连结构片上网络( n e t w o r k - o n - c h i p ，n o c ) 是 技术进步的必然选择。 作者指m 为了满足整个系统的性能要求，片上网络应该具备以下几个特征： ( - - ) 、它应该提供给计算模块通信用的一致的接口。使计算和通信分离，简化系统 设计。( 二) 、它应能高效实现多种类别的服务。这是因为系统中不同的i p 模块在数 据率、延迟以及数据粒度等方面的需求有很大的不同。( 三) 、片上网络能够提供一 定的服务质量保证。因为当网络趋于饱和时，延迟和吞吐量将会出现剧烈的波动。这 将不能满足某些实时应用的要求。 随着技术的发展，片上网络能够提供高的带宽。而它的面积主要由交换矩阵、控 制逻辑以及缓存空间占据。其中，交换矩阵的大小由端口数量决定，而控制逻辑主要 由交换矩阵的调度单元与其它一些配置模块构成。控制逻辑算法不但决定路由器延 迟，也决定着需要的缓存空间的大小。而缓存空间在路由器的面积开销中占据着主导 地位。 在文中，作者不但提出了片上网络的体系结构还给出了片上网络的设计方法。 s k u m a r 等首先解释了提出新的片上网络体系结构的三个原因。一是摩尔定律将 继续发挥作用，这使得芯片上的晶体管数量不断增加。二是单个处理器将不能利用整 个芯片上的所有晶体管，单个时钟能够同步的区域只能占芯片的一小部分。三是应用 本身也将被划分成不同的相互间通信的任务，不同的任务有不同的特点和来源。 7 片上网络路由算法关键问题研究第1 章前育 片上网络平台能够将不同的设计任务分离，提高设计效率。适用片上网络进行设 计的有以下几种情况：可配置和可编程的产品、一系列产品的设计、包含一组异质任 务的应用、面市时间紧张的产品以及适合在模块、功能以及特征等三个层次进行重用 的产品。 在体系结构方面，网络的拓扑结构为简单的网格( m e s h ) 结构，网络由信道连接 成的资源和交换机构成。一个交换机与四个相邻的交换机相连，交换机还有内部的缓 存队列以处理拥塞。每个连接的信道由两个单向的点到点连接组成。这种设计方法又 称为c l i c h i 主( c h i p - l e v e li n t e g r a t i o no fc o m m u n i c a t i n gh e t e r o g e n e o u se l e m e n t s ) 。 在片上网络中能够集成任意类型的资源，如嵌入式处理器、d s p 核、本地存储器、专 用硬件资源以及可配置的硬件资源。资源通过资源网络接口与交换机相连，并通过它 与交换机通信。片上网络定义了四层通信协议，从下到上包括物理层、数据链路层、 网络层以及传输层。资源网络接口实现所有的四层协议，而交换机到交换机之间的接 口只实现下面三层协议。 在