（微电子学与固体电子学专业论文）片上网络拓扑结构与通信方法研究.pdf

摘要 摘要 半导体工艺技术进入深亚微米时代后，基于总线系统芯片s o c ( s y s t e mo nc h i p ) 的体系结构在物理设计、通信带宽以及功耗等方面无法满足未来多m 体系发展的需 求。片上网络n o c ( n e t w o r ko nc h i p ) 是一种新的系统芯片体系结构，其核心思想 是将计算机网络技术移植到系统芯片设计中来，从体系结构上彻底解决总线架构 带来的问题。在n o c 系统中，拓扑结构和通信方法是影响片上系统性能的重要因素。 本文对n o c 的拓扑结构和通信方法进行了深入研究，提出了一些新的解决n o c 关键问题的方法，并通过建模仿真和软硬件验证对提出的新方法进行了验证。论 文的主要研究成果如下： 1 对n o c 的拓扑结构进行了研究。提出了两种适合二维片上网络的拓扑结构， 即广义p e t e r s e n 图( g e n e r a l i z e dp e t e r s e n ，g p ( 2 m ，1 ) ) 和网格环形( m e s h c o n n e c t e d - c y c l e s ，m c c ) 片上网络互连结构。详细分析两种拓扑结构的性质。分别 设计了两种拓扑结构的确定性路由算法，对两种拓扑结构进行了模拟分析，并与 典型片上网络的m e s h 拓扑结构进行了比较。在综合考虑网络直径和节点度之积的 情况下，g p ( 2 m ，1 ) 和m c c 拓扑结构更适合构建片上互连网络。 2 对n o c 的交换机制进行了研究。通过分析总结现有的片上网络交换技术， 提出了一种缓冲式快速虫孔交换技术。对该交换机制进行了模拟分析并与典型的 虚通道虫孔交换技术进行了比较，表明是一种高性能、低成本的交换技术。 3 总结片上网络路由器的基本结构和设计，设计了一种基于缓冲式虫孔交换 技术的通用片上网络路由器结构，并对该路由器结构进行了详细设计、功能仿真 和性能评估。结果表明该种结构的路由器是一种低延迟的片上网络路由器。 4 分析总结了系统级评估的性能指标和评估流程，建立了系统级仿真平台。 该平台是一个模块化、可扩展的系统级仿真平台。 5 设计了一个网络规模为8 x 8 、基于m e s h 的片上网络系统。并用a l t e r a f p g a 开发板验证了其功能，其中的核心模块片上网络路由器和流量产生接收器已 经s m i co 1 3 p m i 艺下流片，工作频率3 0 0 m h z ，等效逻辑门为5 1 5 5 k ，在3 0 0 m h z 工作频率下功耗约为3 0 8 5m w 。 6 通过分析，提出了基于平台的片上网络设计方法，根据该方法建立了一个 片上网络开发验证平台。该平台和系统级仿真平台结合可以形成一个集片上网络 系统分析、功能仿真、硬件验证和性能评估的完整的片上网络开发验证环境。 7 针对片上网络的发展趋势，对三维片上网络拓扑结构进行了分析和探索， 提出了三种适合三维片上网络的拓扑结构，即三维超立方体双环拓扑结构、三维 片上网络拓扑结构与通信方法研究 t o r u s 连接的p e t e r s e n 图拓扑结构、三维长方形扭花环网格拓扑结构。三种拓扑结构 都具有高连接度、短直径、简单的路由策略、常数节点度以及良好的可扩展性， 适合构建三维片上网络。 关键词：片上网络拓扑结构交换技术路由器建模验证 a b s t r a c t a b s t r a c t a st h em i c r o e l e e t r o n i c s t e c h n o l o g ye x p a n d i n g ，t h et r a d i t i o n a l l y i d e ao f s y s t e m - o n - c h i p ( s o c ) t oi n t e g r a t et h ew h o l es y s t e mo nas i n g l ec h i pw h i c hw i t ho n l y o n ec p ui si nt h eb u sa r c h i t e c t u r e ，u n a b l et om e e tt h en e e do fm u l t i - i pa r c h i t e c t u r e d e v e l o p m e n t s os e v e r a lr e s e a r c hg r o u p sp r o p o s e daw h o l en e wi d e ao fi n t e g r a t e d c i r c u i ta r c h i t e c t u r e ，n e t w o r k - o n - c h i p ( n o c ) t h ec o r ei d e ao fn o ci st ot r a n s p l a n tt h e k n o w l e d g e o fn e t w o r k t e c h n o l o g y o f c o m p u t e r i n t ot h ed e s i g no fc h i p st o s y s t e m a t i c a l l ys o l v et h ep r o b l e m so fb u sa r c h i t e c t u r e i nn o cs y s t e m , t o p o l o g i c a l s t r u c t u r e sa n dc o m m u n i c a t i o np a r a d i g ma r ei m p o r t a n tf a c t o r si ns y s t e mp e r f o r m a n c e a f t e ri n - d e p t ha n a l y s i sa n dr e s e a r c hi nk e yp r o b l e m so fn o c ，w ep r o p o s e ds o m e n e ws o l m i o n st os o l v et h en o cp r o b l e m s t h es o l u t i o n sh a db e e nv a l i d a t e db y m o d e l i n g - s i m u l a t i o n , s o f t w a r ea n dh a r d w a r ev e r i f i c a t i o n 1 1 把m a i nr e s e a r c hr e s u l t so ft h i st h e s i sa r es h o w na sf o l l o w s ： 1 r e s e a r c ho nt h et o p o l o g i c a ls t r u c t u r e so fn o c t w os u i t a b l en e t w o r k - o n - c h i p t o p o l o g i e s ，t h a ti s ，g e n e r a l i z e dp e t e r s e ng r a p h ( g p ( 2 m ，1 ) ) a n dt h em e s h c o n n e c t e d c y c l e s ( m c c ) i n t e r c o n n e c tn e t w o r ks t r u c t u r e sa r ep r o p o s e d w e m a d ed e t a i l e da n a l y s i so ft h ec h a r a c t e ro ft h et w ot o p o l o g i e s ，d e s i g n e dt w o d e t e r m i n i s t i cr o u t i n ga l g o r i t h m so ft h en e wt o p o l o g i e s ，a n dm a k eac o n t r a s t b e t w e e nt h eg p ( 2 m ，1 ) a n dt h em c ct o p o l o g i e sa n dt h et y p i c a lm e s ht o p o l o g y t h er e s u l t ss h o wt h a tm c ca n dg p ( 2 m ，1 ) h a v eb e t t e rp e r f o r m a n c e ，e s p e c i a l l yi n l o c a lt r a f f i c sa n dl o wl o a d s ，a n dl o w e rc o s t 2 r e s e a r c ho nn o cs w i t c h i n gm e c h a n i s m an e wb u f f e r e de x p r e s sw o r m h o l e s w i t c h i n g ( b e w s ) t e c h n o l o g yo fh i g hp e r f o r m a n c ea n dl o wc o s ti sp r o p o s e d a l s oac o n t r a s ti sm a d eb e t w e e nb e w sa n dt y p i c a lv t r t u a lc h a n n e lw o r m h o l e s w i t c h i n g ( v c w s ) t e c h n o l o g yb ys i m u l a t i o na n a l y s i s ，w h i c hd e m o n s t r a t e b e w sa c h i e v e sl o w e rl a t e n c yt h a nv c w s 3 a f t e rm a k i n gas u m m a r yo fs t r u c t u r ea n dd e s i g no ft h en o cr o u t e r s ，an e w r o u t e rs t r u c t u r eb a s e do nb e w sf o rn e t w o r k - o n c h i pi sd e s i g n e d a n dd e t a i l e d d e s i g n , f u n c t i o n a ls i m u l a t i o n , a n dp e r f o r m a n c ee v a l u a t i o na r ed o n et ot h en e w r o u t e rs t r u c t u r e t h er e s u l t ss h o w sb e w sr o u t e rh a sl o w e rl a n t e n c y 4 a n a l y z e dt h en o cs y s t e m l e v e lm o d e l i n gs i m u l a t i o n , s u m m e du ps y s t e m - l e v e l p e r f o r m a n c ee v a l u a t i n gp r o c e s s ， a n dt h e na n a l y z e da n d d e s i g n e d 片上网络拓扑结构与通信方法研究 s y s t e m l e v e l - s i m u l a t i o nn e t w o r km o d e la n dt r a f f i cm o d e l ，f m a l l ys e tu pa s y s t e m l e v e ls i m u l a t i o np l a t f o r m 1 1 l ep l a t f o r me x p l o r e st h en o cd e s i g ns p a c e i na ne x p a n d a b l ew a y 5 a nn o cs y s t e m ，6 4n o d e s ，i sd e s i g n e da n dv e r i f i c a t i o n 谢也f p g a a n d s y n t h e s i sa n dl a y o u ta r ec a r r i e do u tb ys m i c0 13 1 x r ns t a n d a r dc m o sp r o c e s s a n di tsh a r d w a r es c a l ea n dp o w e rd i s s i p a t i o ni s515 5kl o g i cg a t ea n d3 0 8 5 m w 3 0 0 m h zf o rt h er o u t e r , t r a f f i cg e n e r a t o ra n dt r a f f i cr e c i e v e r 6 耶1 en o cd e v e l o p m e n ta n dv e r i f i c a t i o np l a t f o r mi ss e tu pa c c o r d i n gt oan e w d e s i g nm e t h o d 1 1 1 ep l a t f o r mu n i t e d 、 ，i ms y s t e m l e v e ls i m u l a t i o np l a t f o r m c o m e st oa l li n t e g r a t e dn o cd e v e l o p m e n t & v e r i f i c a t i o ne n v i r o n m e n tw i t h s y s t e ma n a l y s i s ，f u n c t i o n a ls i m u l a t i o n , h a r d w a r ev e r i f i c a t i o na n dp e r f o r m a n c e e v a l u a t i o nf u n c t i o n s 7 a c c o r d i n gt o t h ed e v e l o p m e n tt r e n do fn o c ，t h r e ek i n d so ft o p o l o g yt h a t s u i t a b l ef o rt h r e e d i m e n s i o n a ln o ca r e p r o p o s e d t h e y a r e h y p e r c u b e - c o n n e c t e dd o u b l e - l o o pt o p o l o g y , t o m sc o n n e c t e dp e t e r s e ng r a p h t o p o l o g y , r e c t a n g u l a rt w i s t e dt o m sm e s h e st o p o l o g y a n dd e t a i l e da n a l y s i si s m a d et o t h et h r e et o p o l o g i e ss h o wt h a t t h ep r o p o s e dn e t w o r k si sab e t t e r i n t e r c o n n e e t i o nn e t w o r ki nt h ep r o p e r t i e so ft o p o l o g ya n dt h ep e r f o r m a n c eo f c o m m u n i c a t i o n k e y w o r d s ：n e t w o r k - o n - c h i pt o p o l o g i e s s w i t c h i n gt e c h n i q u e r o u t e r m o d e l i n g v e r i f i c a t i o n 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：参俐 、j l 日期 d 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 本人签名： 导师签名： 声俐 h 盼口，l j 以 日期 日期 第一章绪论 第一章绪论 1 1 研究背景 片上系统s o c ( s y s t e mo nc h i p ) 是2 0 世纪9 0 年代出现的概念。随着半导体工 艺的不断发展和s o c 技术的不断完善，现在的s o c 中可包含一个或多个处理器、存 储器、模拟电路、数模混合电路以及片上可编程逻辑等i p 核i l 。3 1 。目前出现的s o c 可以称为第一代s o c ，其主要思想是设计的重用，把i p 核( 虚拟部件) 用片上总线 连接起来。尽管人们对于片上总线作了很多改进和标准化的工作，但是，随着s o c 中所包含的i p 核数目增至成千上万的时候，现有的以总线结构为通信基础的s o c 技 术面临着在性能、功耗、延迟和可靠性等方面的巨大挑划删孓4 7 】。在2 0 0 1 年左右， 一些研究机构借鉴和吸收了通信网络中的一些思想，提出了以通信为核心的复杂 s o c 的i p 核的集成方法，即片上网络( n e t w o r ko nc h i p ，n o c ) ，以解决复杂s o c 面 临的各种问题【1 ，4 1 4 4 8 4 9 】。n o c 采用基于包交换的方法和分层方法来替代原先的传统 总线，实现了处理单元( i p 核) 与通信结构( 网络) 的分离【_ 7 。1 0 】。 近几年来，人们逐步认识到片上网络( n o c ) 将代替片上总线成为第二代s o c 的片内通信基础设施”】。n o c 的主要特点是采用比较规则的拓扑结构，避免全局 布线( 长线) 和全局的同步，预先设计的通信设施具有已知的性能和可预见的物 理和电气特性。其优势是降低s o c 的功耗、减少s o c 制造费用、提高s o c 性能、 减少s o c 上市时间、减少s o c 量产时间和降低设计风险。 n o c 是指一个芯片内集成了大量的计算资源、存储资源以及连接这些资源的通 信网络，片内的通信网络用来实现这些资源之间的高速通信【5 0 1 。随着微电子技术 向纳米级发展，要充分发挥一个芯片内数十亿晶体管的计算能力，利用网络连接 的高度并行的多处理器阵列结构是新一代复杂计算体系结构的必然选择【明。它不 仅涉及到通信基础结构、中间件、操作系统和提供的计算服务等一系列概念的革 新，也涉及n s o c 设计方法学的变革以及n o c 工具的创新 1 2 , 5 0 。 采用n o c 的主要优势包括： 1 有利于提高通信带宽【1 2 , s 2 1 。总线结构是现有芯片架构的通信脉络，随着电 路规模的扩大，总线结构将成为芯片设计的瓶颈，虽然总线可以有效地连接多个用 户进行通信，但总线地址资源并不能随着计算单元的增加而无限扩展，一条总线无 法支持一对以上的用户同时通信，即串行访问机制导致了通信的瓶颈。而网络拓扑 结构提供了良好的可扩展性，互连网络提供了良好的并行通信能力，从而使得通 信带宽增加几个数量级。 2 片上网络拓扑结构与通信方法研究 2 有利于降低功耗。在基于总线的s o c 中，片上通信是功耗的主要来源，庞大 的同步时钟网络与总线的功耗占据芯片总功耗的绝大部分。在n o c 中，将用短线代 替长线通信，可以有效地降低功耗，解决深亚微米工艺下所谓“红墙砖”的问题【5 3 。 此外，n o c 借鉴了通信协议中的分层思想，为从物理级到应用级的全面功耗控制提 供了可能。 3 有利于提升重用设计。总线架构可扩展性和可重用性差，为此，在芯片计 算能力演变时，必须根据芯片的处理能力需求而变更设计，如更高的内存宽度、更 高的频率、更灵活的同步或异步设计等等。每一代芯片的推出都伴随着程度不等 的设计变更，这对于开发人员而言是相当大的负担。若是将通信架构独立设计，并 且运用更具弹性的技术，对于缩短设计周期、减少开发成本都有不小的帮助。由于 所使用的通信协议层本身属于独立的资源，因此，n o c 支持高效率可重用设计方法 学的体系结构。通信和计算完全分离的技术将重用范围从计算单元可重用扩展到 计算与通信单元皆可重用的层次，从而大大提升了重用设计的层次。通过统一的网 络接口，可以将系统所需要的i p 核采用“即插即用”加入到系统中。 4 有利于解决全局同步的难题【5 1 1 。纳米工艺所带来的各种物理效应使得片上 全局同步越来越困难。当采用全局时钟时，全局线延迟将达一个时钟周期，时钟歪 斜变得难以控制，而全局的时钟树是影响芯片功耗和成本的一个主要因素。随着集 成器件尺寸越来越小，时钟频率越来越高，这些问题将变得越来越突出。 片上网络的体系结构将使计算资源之间通过短线互连，采用全局异步局部同 步时钟策略，将是解决深亚微米工艺下集成电路设计所面临问题的有效途径。 在数据通信领域，局域网和广域网技术已经成功地解决了世界范围的通信问 题。和总线的情况相反，通信网络利用o s i 模型的开放的分层结构和协议，能够独 立于传输和应用业务的发展，使通信技术在底层和高层都能适应新的变化。例如 在物理层从以太网的多心同轴电缆、双绞线、到a d s l 、光纤以及无线传输等，发 展变化日新月异。事务处理层的音频流，在服务层产生的对等网( p e e r - t o - p e e r ) 、 安全电子商务等新业务层出不穷，而老式的l o m b s 甚至1 m b s 以太网设备仍然连 在局域网上。由此可以看出网络结构的生命力和适应能力。实际上网络已经开始 代替总线，例如p c i e x p r e s s 就是板上网络。随着深亚微米和纳米工艺的发展， 将有各种功能的大量i p 集成在s o c 单片上。用n o c 代替片上总线已经被公认是s o c 发展的必然趋势。 在此背景下，基于网络概念的n o c 研究与开发成为片上系统研究的热点。全世 界已有多所大学和研究机构正在进行n o c 研究。我国学术界非常重视这个方向的研 究，在国家8 6 3 计划，国家自然科学基金等国家级研究计划中资助n o c 相关研究。 本文受国家“8 6 3 ”计划，国家自然科学基金资助。 第一章绪论 1 2 片上阿络关键问题 3 一 不能把n o c 简单地理解为把通常的计算机网络集成在芯片上。n o c 的通信网络 在链路长度、链路位宽、通讯协议等方面和通常意义上的通信网络都有着很显著 的区别，但n o c 又借鉴和吸收了通常通信网络的一些设计思想。n o c 在单片上集成 了大量的计算资源、存储资源以及连接这些资源的通信网络。计算资源包括异构 多核，并行处理器、协处理器、可重构硬件等，n o c 用来实现这些资源之间的高速 通信。要适应高层应用的变化，采用大量可重构资源是n o c 的一个显著特征。 与传统计算机网络相似，n o c 也有路由器、路由器间链路、路由机制与协议、 流控机制等基本组成部分。n o c 与计算机网络的区别： 1 规模不同。计算机网络的规模可以是一个房间，也可以扩展到整个地球； 而n o c 的规模则受限于一个狭小的硅片，因此，n o c 的计算和存储限制要严格得多。 由于占用面积限制，片上的存储空间是十分珍贵的。在计算机网络中，每个处理 器都会安装一个n i c ( n e t w o r ki n t e r f a c ec a r d ) ，用来实现一部分协议栈，对于n o c ， 这种实现是不可能的。n o c 可能用于便携设备，它的功耗限制也十分严格。 2 互连线资源不同。一个典型的点到点通信的n o c 可以用3 0 0b i t 的连线来提 供大量的带宽。 3 通信线长短不同。n o c 的连线足够短，方便部件间同步。 4 通信协议。n o c 的通信协议随着应用不同而不同，在n o c 上实现t c p 那样复 杂的机制是不太可行的。 近年来n o c 的研究热点主要集中于：功耗评估与低功耗设计f 5 4 , 5 5 】、路由器结构 设计5 6 4 9 、实现与测试方法【删、容错机铝l j 6 1 , 6 2 1 等。与n o c 设计相关的关键技术有 路由器设计、拓扑结构设计、路由算法设计、路由器间连线的布局布线等。这些 技术以前主要应用于大规模并行系统，但片上系统与大规模并行系统的设计标准 差距很大，设计时要考虑功耗，面积，物理实现难度等等。 由于目前成熟的网络技术不太适合n o c 这种新生概念，设计一个适用于n o c 特征，能够提供低延迟、高带宽，物理实现难度不高的n o c 系统有重要意义。本节 主要介绍了当前片上网络的研究与设计的关键技术，片上网络的研究内容可以分 为拓扑结构、路由算法、路由器结构、性能分析、功耗评估与设计等几个方面， 其中路由器结构设计又包含调度算法、流控机制和b u f f e r 结构等。 1 2 1 片上网络的结构 l - n o c 的基本结构 一个n o c 的基本结构应该包括如图1 1 所示的几个部分 2 , 4 - 6 ，： 1 ) 网络适配器：实现了i p 核和n o c 网络之间接口，分离网络通信和i p 核的计 4 片上网络拓扑结构与通信方法研究 算功能。 2 ) 路由节点：通过路由协议进行路径选择，实现路由策略。 3 ) 链路：实现节点连接，包含了一个或多个逻辑、物理信道。 4 ) i p 核：i p 核可以是同质的，也可以是非同质的；可以是细粒度的，也可以 是粗粒度的。 图1 1 给出的4 x 4 的2 dm e s h 结构包含了一个n o c 基本组成，该结构没有采用总 线和专用点对点的链路，而采用了一般网格拓扑结构，通过一定的路由算法可以 实现任意两个口核之间的通信，可采用包交换、电路交换或其它的路由方式，也可 使用同步、异步或其它逻辑实现。 图1 1 一个4 x 4 n o c 拓扑结构 内校 网络适配器 路由节点 链路 2 n o c 中的层次结构 n o c 借鉴网络中的分层思想，每一层和相邻层之间都有接口，较低层通过接口 向它的上一层提供服务，服务的实现细节对上层是屏蔽的。较高层又是在较低层 提供服务的基础上实现更高级的服务。关于n o c 层次结构在不同的n o c 实现中有不 同的描述，各层的功能略有差异，各层的名称和数目也不尽相同。尽管如此，图 1 2 给出n o c 层次和o s i 层之间对应关系得到较大程度的认可，每个层次都对应着 n o c 的不同研究问题 1 6 , 1 9 - 2 2 。 1 2 2 网络拓扑结构 n o c 网络传输消息的能力主要依靠其拓扑结构，它对网络延迟、吞吐量、面积、 容错、功耗有很大影响外，对设计策略和内核到网络节点的映射起着重要的作用。 选择合适的n o c 拓扑结构是n o c 设计中非常关键的问题之一。 第一章绪论 一r 二二。垂s 三i # 至 星二二二i i 5 一 k 一一一一一一一一一 ：流控物理单元! 图1 2n o c 分层与o s i 参考模型对应关系 目前，大部分的n o c 研究和设计借鉴了并行计算机体系结构中的静态网络结 构，包含规则和不规则两种结构。常见规则结构如k t hn o s t r u m 的2 dm e s h ，3 d m e s h 结构，t o m s 结构，u p m cs p i n 的扁平树结构，八角形结构和p r o t e o 的环形结构 等。多家研究机构采用了2 dm e s h 或者其变形的t o r u s 结构为网络的拓扑结构。不 规则的结构是由规则结构组合而成的 4 , 1 1 - 1 7 , 2 2 , 2 6 , 2 7 。 目前，理论上还不能证明可以用最优的拓扑结构来实现任何一个给定的应用。 虽然专用的网络结构能提高性能、降低功耗、减小面积，但采用不规则的网格拓 扑结构会引起版图设计、不均匀的线长等设计问题。因此，决定有效的拓扑结构 以平衡高层性能与细节的实现方法受到了微米或纳米级工艺的制约。 1 2 3 路由问题 路由是确定一个消息从源节点到目的节点的路径机制。区别于总线结构的n o c 的一个重要特征就是采用包交换的路由。包交换既可以在源节点上实现路由也可 以在每一跳节点上实现路由，相应称为源路由和分布式路由。路由算法可以分为 两类，即确定性路由和自适应路由，无论是那类路由算法都应该有效地解决死锁、 活锁以及饥饿问题。 1 死锁。当两个包彼此等待路由转发时，由于保留了部分资源并等待对方释 放资源，因此产生死锁。通过流量控制可以避免死锁。 2 活锁。当一个包在它的目的地环绕但无法到达目的节点时就产生了活锁。 该问题存在于非最短路由算法中。 3 饥饿。使用不同优先级可能出现高优先级的包始终占有资源，而一些低优 先级的包永远不能到达其目的地，发生饥饿现象。使用公平路由算法或为低优先 6 片上网络拓扑结构与通信方法研究 级的包预留一些资源可避免饥饿现象。 目前，大多数研究机构都是根据具体的研究重点不同而采用不同的路由策略， 其中确定性x y 路由和自适应性d y a d 路由在n o c 的设计中既不会产生死锁，也不 会产生活锁口8 捌。 1 2 4 交换技术问题 交换技术决定交换节点什么时间，如何连接其输入与输出端口。交换技术包 括两种主要类型：包交换和电路交换。 1 电路交换。交换网络是一组由全双工点到点链路连接在一起的交换单元。 交换网络包括基于总线和基于开关两种类型。基于开关的网络包括c r o s s b a r , 单级 交换网络和多级交换网络。交换的方法分为时分( t i m ed i v i s i o n ) 和空分( s p a c e d i v i s i o n ) 两种。交换单元通过在其终端建立物理连接实现空分交换，典型的空分交 换是c r o s s b a r 。时分交换利用缓存，以不同的读写顺序对数据进行交换。电路交换 的优势是在整个数据传输过程中保留一定的网络带宽，交换节点结构简单，延迟 固定并能有效避免死锁现象。其中采用t - s t 结构的电路交换被认为是n o c 电路交 换很好的实现【3 0 】。 2 包交换。在包交换时，发送数据前不需要建立链路。包通过最优路由算法 原则，选择最优路径到其目的地。目前主要的包交换技术有存储转发、虚直通和 虫孔等交换技术【3 l 】，在n o c 设计中，不同的硬件资源需要不同的性能，因此，应 该根据具体的硬件资源，选择具体的包交换技术，尽力减少开销。 1 2 5 服务质量问题 服务质量被定义为网络提供给i p 核需要的服务数量。因此它包含两方面内容： 1 定义了某一数量的服务；2 服务协商。服务应该具有高吞吐量，低延迟，低功 耗等特点。协商是指在i p 核需求的服务与网络提供的现有服务之间实现平衡。 服务质量分为两种基本类型：尽最大努力服务( b e ，b e s te f f o r t s ) 和保证服 务( g s ，g u a r a n t e es e r v i c e ) ，它们提供不同层次的许诺服务，并且对通信行为有潜 在的影响：1 结果的正确性；2 事务的完成；3 性能要求。总之，保证服务具有 可预测性，用于期望服务质量高的业务，例如实时系统。尽最大努力服务则能提 高平均资源利用率【2 5 3 4 。 1 2 6 流量控制问题 在n o c 领域，流量控制被特定用于交换节点间、端到端之间的传输协议的业务 量。通过避免缓冲区溢出及丢包，这些协议提供了平滑通讯量的策略。目前大多 数n o c 采用的是虚通道或者限制数据包注入网络速度的方法 3 4 1 ，然而通过限制注 第一章绪论 7 一 入网络包的方式进行流量控制限制了网络中同时传输包的数量，虚通道流量控制 增加了硬件开销。 1 2 7 资源网络接口问题 资源网络接口( 鼢汀) 是资源( i p 核) 与网络间的接口，通过r n i 接 1 i p 核可 以用最小的代价使用网络，同时i p 核和网络资源都可以重用。r n i 在功能上可以 分为两个个部分，一部分是连接网络的部分，与口核无关，另外一部分连接到口 核，和资源相关。前一部分因为和资源无关，因此对于任何资源都可以重用。和 资源相关的部分连接具体的资源信号，例如控制信号，地址信号，主要是信号的 打包和解包，数据的编码检测等消息，这部分还要考虑定时，同步等问题【2 0 】。 1 2 8 性能评估问题 性能评估是n o c 设计的一个重要方面。为了比较不同的n o c 结构，必须使用一 套标准的性能评价指标。评估一个n o c 的的主要性能包括以下几个方面【6 3 】： 1 吞吐量。数字通信网的性能是以每秒多少b i t 数的带宽来衡量的，在n o c 中， 以单位时间内数据包消息通过网络的数量定义吞吐量。 2 延迟。指在n o c 从源节点发送数据包头部消息开始，到目标节点接收数据 包尾部消息为止所经历的时间( 以时钟周期为单位) 。流控单元( f l i t ) 从源节点到 达目标节点，必须经过由交换节点和网络互连所组成的一条路径。每一个消息根 据源节点和目标节点以及路由算法，会产生不同的延迟。 3 面积。评价n o c 的面积主要有三个部分：一是实现路由和流量控制所需要 的存储缓冲区和逻辑电路占用的面积。二是为了保证互连线延迟不超过一个时钟 周期而插入中继( b u f f e r ) 所占用的面积。三是芯片中布线对面积也有影响。 4 功耗。n o c 动态功耗主要有两个来源：节点功耗和网络功耗。每一个节点 内部的操作产生节点功耗。网络功耗是指当包在网络上传输时，互连线和每个交 换节点内部逻辑门的功耗。因此，当我们估计网络功耗时，需要计算线和逻辑门 的功耗。 1 2 9 定时问题 在一个片上网络中，包含了众多的i p 核模块，每个i p 核都有自己的定时信息， 如何实现整个n o c 的全局定时问题是n o c 物理设计需要解决的一个关键问题。已经 公认全局异步局部同步( g a l s ) 是解决定时问题的方法【2 0 】。从目前的n o c 研究来 看，不同的设计有着不同的解决方法，没有一个统一的标准。c h a i n t l 3 1 和 m a n g o t 3 6 1 两i n o c 都采用了g a l s 定时方式来解决全局定时问题。 8 片上网络拓扑结构与通信方法研究 1 2 1 0 映射问题 映射是在给定任务图、设计约束( 延迟和功耗等) 和i p 库的基础上，将每个任 务分配到合适的i p 核上以及安排每个i p 核上的任务执行顺序，然后再决定每个i p 核 在n o c 拓扑结构中的位置。在映射时，搜索空间随着网络尺寸的增长呈阶乘递增， 对于一个包含2 5 个i p 核的n o c ，映射有2 51 种可能结果。因此，映射问题是n o c 设 计中的一个n p 问题【9 】。目前，映射可以采用启发式的算法进行【3 7 1 ，也是n o c 研究 中非常重要的问题。 1 3 国内外研究现状 1 3 1 国外相关研究 最早出现的n o c 之一是法国巴黎的p i e r r e 大学【删研制的，该n o c 利用扁树( f a t t r e 圮) 的拓扑结构，以包交换的方式进行通信。实验结果是不同情况下延迟的变化 很大，有0 1 的发送消息的延迟超过1 5 0 个周期。 s t a n f o r d 大学的d a l l y 教授采用环形交换网络和虚拟信道传输【4 】，利用数据报格 式和本地缓冲器避免死锁。一个交换单元的存储器为4 0 k b i t 。该n o c 用于一般的消 息交换，如果对于实时性要求高的数据流，需要进行预调度( p r e s c h e d u l e ) 。 k t h 开发了一个n o s t r u m 的模拟环境，可以进行m e s h 和t o n m 结构网络性能评估 并可以给出相应的分析结果暖7 1 。p r i n c e t o n 大学开发了可以进行详细功耗估计的 o r i o n 动态功耗模拟器和周期精确链路功耗估计的l u n a 功耗性能模拟器，它们嵌 入在p o p n e t 网络模拟器中l 1 2 4 5 】。 麻省理工学院于2 0 0 2 年研制的称为r a w 处理器，属于一种基本的n o c l 4 1 。r a w 采用0 1 5 9 x n 的c m o s i 艺，集成度1 亿2 千万晶体管，工作频率2 2 5 m h z ，功耗2 5 w 。 从主存储器到芯片上的s r a m 存储器，从s r a m 存储器到a l u 的数据带宽分别为 2 5 g b y t e s s 与5 7 g b y t e s s ，直接地支持数据流计算。r a w 用全双工的连接实现可编 程路由器和计算资源( c o r e ) 之间的通信。r a w 的主要应用是作为一个超级计算机进 行多媒体处理。不同的研究机构对n o c 的研究重点不同，比较有影响的n o c 项目有 k t hn o s t r u m l 2 7 ，b o l o g a n - s t a n f o r dx p i p e s l 2 9 1 ，p h i l i p s 歪t h e r a l t 3 0 l ，u m a n c h e s t e r c h a i n l 3 ，u p m cs p i n 3 2 1 ，n 丌p r o t e o 3 4 1 ，s t n o c t m 3 6 1 ，p r i n c e t o no r i o n 3 9 1 等等。 1 n o s t r u m 工程 n o s 仃u m 是一个由瑞典k t h 研发的n o c 体系结构，它主要研究从物理层到应用 层的通信问题，n o s t r u m 是通过将每个路由节点连接到另外四个路由节点而形成一 个规则的2 dm e s h 拓扑结构，一个资源( i p 核) 连接到一个路由节点。口核之间的 通信通过在交换网络上发送的包来实现，交换网络采用了同频不同相的伪同步时 钟，每个i p 核使用不同甚至任意的时钟实现。采用有效地时钟策略和规则拓扑结构 第一章绪论 9 一 保证了性能和功耗的可预测性。n o s t r u m 网络采用了自适应反射路由策略和很小的 缓冲避免了拥塞并具有自适应容错能力，采用保留通信资源来提供保证延迟的流 量并提供尽最大努力流量。该研究组也研究了n o c 的协议、映射技术、时钟策略。 n o s t r u m 是一个通用的适合任何复杂s o c 的应用，但在特定的应用必须进行优化， 因此，他们研究网络处理器和多媒体应用的n o c 平台。他们开发了一个具有图形用 户界面( g u i ) 的基于s y s t e m c 的n o s t l l 蛐仿真环境n n s e ，通过g u i 配置n o s t r u m 网 络的节点数量、拓扑结构、路由策略、流量模式等进行仿真，仿真结果可以采用 不同的图形方式显示【2 7 ，2 舯。 2 x p i p e s 工程 x p i p e s 是由意大利b o l o g n a 大学和美 雪s t a n f o r d 大学联合研发的一个可综合的、 高性能、不同i p 核互连的n o c 基础结构，通过对可定制的路由节点、通信链路和网 络接口的配置可以得到任意的拓扑结构，采用了虫孔交换技术和静态路由算法。 网络接1 2 1 采用o c p 2 o ( o p e nc o r ep r o t o c o l2 o ) 协议进行i p 核信号和网络流控单元 信号之间的转换，主要由请求处理、响应处理和循环缓冲电路组成，支持网络和i p 核不同的时钟。路由节点根据源节点发送包的第一个f l i t 所走的路径消息执行路由 功能，应用了确定性源路由和虫孔交换技术，主要由缓冲、产生控制信号的分配 器和c r o s s b a r 组成。链路可以分级产生流水线。他们开发了s u n m a p 和 x p i p e s c o m p i l c r 两个开发x p i p c s 的工具。s u n m a p 是根据应用自动在拓扑结构库 ( m e s h , t o m s ，h y p e r c u b e ，b u t t e r f l y , c l o s ) 中选择最佳拓扑结构，并根据约束条件( 延 迟、面积、功耗等) 和i p 核之间的流量模型映射i p 核到选定的拓扑结构，选择合适 的路由策略( 维序路由、最小路径路由等) ，它的输出作为x p i p