（通信与信息系统专业论文）mpsocs互连仿真软件设计.pdf

摘要摘要随着芯片集成度不断提高，低频率、多核芯片结构( m u l t i p r o c e s s o rs y s t e m o n c h i p s ，m p s o c s ) 将逐渐取代高频率、单核芯片结构。片上网络( n e t w o r k o n -c h i p ，n o c ) 作为解决m p s o c s 互连问题的新思路，是将计算机网络技术移植到芯片设计中来，从体系结构上彻底解决总线架构带来的一系列问题。为了有效验证m p s o c s 芯片结构体系的合理性，需要在软件环境下对m p s o c s 的新型互连结构进行仿真。利用m p s o c s 新体系结构与已有的网络互连的相似性以及o p n e t 在网络仿真方面灵活性高的优点，本文建立了一种新的基于o p n e t 的多内核互连仿真平台，该平台可对n o c 的拓扑结构、路由算法、交换机制等关键技术及功耗进行网络性能仿真分析。本文首先阐述了m p s o c s 的发展现状及趋势，详细介绍了n o c 中的各种关键技术；接着详细说明了建立多内核互连仿真平台的过程，实现了典型的鼬n g 、m e s h 和t o r u s 等拓扑结构的4 2 0 4 8 多内核互连、x y 路由算法和存储交换技术的性能仿真，同时结合功耗仿真模型对n o c 的功耗进行了仿真；最后以f f t 算法对该仿真平台进行了验证，证明了该平台的有效性，为实际系统的验证提供了理论和仿真支持。关键词：m p s o c s 片上网络o p n e t 仿真平台并行f f ta b s t r a c ta b s t r a c tw i t ht h er a p i dd e v e l o p m e n to fi n t e g r a t e dc i r c u i to c ) ，l o w - f r e q u e n c ym u l t i p r o c e s s o rs y s t e m - 0 1 1 - c h i p s ( m p s o c s ) w i l lg r a d u a l l yr e p l a c et h eh i g h - f r e q u e n c ys i n g l e - c o r ea r c h i t e c t u r e a st h en e wi n t e r c o n n e c t i o ns t r u c t u r ef o rm p s o c s ，n e t w o r k -o n - s h i p ( n o c ) u s e st h et h e o r yo fc o m p u t e rc o m m u n i c a t i o nn e t w o r kt os o l v et h ep r o b l e m so fm p s o c si n t e r c o n n e c t i o nb a s e do nb u s a n di ti sn e c e s s a r yt os i m u l a t et h ep e r f o r m a n c eo ft h en e wi n t e r c o n n e c t i o na r c h i t e c t u r eo fm p s o c sw i t hs o f t w a r es i m u l a t i o np l a t f o r m a sm p s o c si n t e r c o n n e c t i o ni ss i m i l a rt ot h ee x i s t i n gn e t w o r ka r c h i t e c t u r ea n do p n e th a st h ea d v a n t a g eo ff l e x i b i l i t yi nn e t w o r ks i m u l a t i o n ，a nm p s o c si n t e r c o n n e c t i o ns i m u l a t i o ns o f t w a r ep l a t f o r mi sd e s i g n e db a s e do no p n e t f i r s t l y , t h ep a p e rm a i n l yd i s c u s s e st h ep r e s e n td e v e l o p m e n to fm p s o c sa n dt h ek e yt e c h n o l o g yo fn o c s e c o n d l y , t h ep r o c e s so fs i m u l a t i o np l a t f o r mb u i l d i n gf o rm p s o c si n t e r c o n n e c t i o ni sp r e s e n t e di nd e t a i l t h ep l a t f o r mi se x t e n d i b l ea n df l e x i b l e ，w h i c hs i m u l a t e st h ek e yt e c h n o l o g yi nn o ci n c l u d i n gr i n g ，m e s ha n dt o m st o p o l o g y , x yr o u t i n ga l g o r i t h m s ，s t o r e a n d - f o r w a r ds w i t c h i n gs t r a t e g ya n dp o w e r f i n a l l y , t h ea p p l i c a t i o no fp a r a l l e lf f ta l g o r i t h mi st e s t e do nt h ed e s i g n e dm p s o c ss i m u l a t i o np l a t f o r ma n dt h er e s u l t sc o n f i r mt h ee f f e c t i v e n e s so fs i m u l a t i o np l a t f o r m a n dt h es i m u l a t i o np l a t f o r mp r o v i d e st h e o r ya n ds i m u l a t i o ns u p p o r tf o rt h er e a ls y s t e m k e y w o r d ：m p s o c sn o co p n e ts i m u l a t i o np l a t f o r mp a r a l l e lf f t创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在文中作了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：经逢蛆日期：趁f 二：! ：!关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后遵守此规定)本学位论文属于保密，在年解密后适用本授权书。本人签名：琛嬖朔日期：2 - o 夕1 俘一一导师签名：；灶日期：立骂处上。l第一章绪论第一章绪论1 1 引言随着集成电路工艺水平的发展，计算机和通信设备对芯片运算能力的需求迅速膨胀，芯片集成度不断提高。在现有的材料基础、工艺水平和制造能力等条件下，低频率、多核芯片结构( m u l t i p r o c e s s o rs y s t e m o n c h i p s ，m p s o c s ) 逐渐取代高频率、单核芯片结构，以解决小于6 5 n m 工艺水平下、超大规模集成电路芯片在超深亚微米效应、全局同步性、功能扩展和功率损耗等方面出现的一系列问题【l 】。目前，i n t e l 和a m d 等主流芯片设计和制造公司，在下一代通用和专用芯片中普遍采用了m p s o c s 结构，取代现有的单核结构，有效提高芯片运算能力。同时，将每瓦效能取代传统的工作频率，作为衡量芯片整体性能的主要技术指标。集成电路制造工艺水平的迅速提高和m p s o c s 结构的广泛应用极大提高了大规模芯片的集成度，降低了系统成本和功率损耗。因此，m p s o c s 结构和相关技术的研究成为芯片设计的研究热点。m p s o c s 结构的迅速发展同时也带来了一系列新的技术问题，多核处理器的共享存储技术是其中一个重要问题。与传统单核芯片结构显著不同，m p s o c s 中存储器需要进行结构改变，适应多核处理器对于存储空间灵活分配和访问的需要，达到有效减小存储器占用芯片面积和降低芯片整体功耗的目的【1 2 。15 1 。s o c ( s y s t e mo nc h i p ) 结构芯片集成功能多，存储器占用面积大。现有单核芯片r a m 所占面积通常占整个芯片面积的3 0 。5 0 ，如i n t e l 公司的p 4c p u的片上存储器占用比例约为3 0 ，网络处理器i x p l 2 0 0 的r a m 占用比例约芯片的5 2 ，x i l i n xv i r t e x 一4f p g a 的r a m 占用比例约为芯片的3 0 。存储器已经成为超大规模芯片的重要组成部分。同时，随着运算速度提高，s o c 结构向m p s o c s 结构发展，芯片存储器所占的比例呈迅速增加趋势。以i n t e l 双核多线程x e o n 处理器( t u l s a 结构) 为例，为了满足多核处理器协同工作和高运算速度等要求，芯片在1 m bl 2c a c h e 的基础上增加了双核共享1 6 m bl 3c a c h e ，使存储器所占面积超过芯片总面积的6 0 t 1 2 】。利用多核处理器的共享存储器动态分配技术，可以有效提高多核结构下共享存储器的利用率，减小存储器所占芯片的面积，达到降低芯片制造成本的目的【1 6 - l9 1 。同时，m p s o c s 结构芯片中内核数量呈迅速增多的趋势。根据芯片核心处理器功能和结构的不同，多核处理器可以分为同构多核结构和异构多核结构。典型的同构多核结构芯片包括通用c p u ，i n t e l 、s u n 和a m d 等公司的c p u 正从2内核结构向4 8 内核结构过度【m 】。在i n t e l 下一代c p u 中更是采用8 0 内核处理2m p s o c s 互连仿真软件设计器结构实现万亿次每秒( t f l o p s ) 运算能力。典型的异构多核结构芯片包括移动终端中采用的信号处理平台，如1 r i 公司o m a p 芯片和s t 公司n o m a d i k 芯片，这些芯片集成了d s p 、a r m 、视频编解码、音频编解码、信号协处理等数十个异步结构内核，实现无线和视( 音) 频信号处理的单芯片设计。随着业务需求的不断提高，在已有的架构基础上可以增加具有特定功能的硬件单元，满足芯片结构设计的可扩展性。根据m p s o c s 的存储器面积增加和内核数量增多的发展趋势，动态最优化的存储器分配和交换技术是m p s o c s 共享存储技术研究的重点和难点。m p s o c s结构的基本出发点是将目前多芯片系统级设计用单芯片实现，因此可以将在系统结构设计中已有技术和新技术用于芯片结构的设计。m p s o c s 片上网络结构是有线网络结构的一种特殊类型，具有节点数少、传输带宽高、网络拓扑结构固定等特殊性。大规模集成电路正从高频率、单核结构向低频率、多核结构发展。采用网络结构和共享存储器技术的m p s o c s 结构已经成为下一代超大规模芯片的设计主流。该技术的研究对我国新一代多核处理器的设计具有重要的理论意义和实用价值。随着芯片内核的增多和内核之间协同工作要求的提高，传统的互连总线已经不能满足m p s o c s 内核的数据交换需求，以内核为节点的网络化结构和数据交换技术片上网络( n e t w o r k o n c h i p ，n o c ) 被认为是下一代互连总线的一种可行的解决方案【1 0 。引。1 2 国内外研究现状及分析在芯片产品方面，国际主流芯片公司开始普遍采用m p s o c s 结构和共享存储器技术。在通用处理器方面，i n t e l 、s u n 和a m d 将下一代c p u 架构定格为低频率、低功耗、同构多核结构。采用共享l 2 l 3c a c h e 结构，有效提高片上存储器的利用率。a m do p t e r o n 处理器采用“巴塞罗那 结构建立4 核c p u ，同时使用共享方式的2 m bl 3c a c h e ，实现了功耗为6 8 1 2 0 w 的4 核高性能处理器【l7 1 。i b m 在3 2 线程s p a r c 处理器中采用8 核处理器结构，共享2 m b ( 4b a n k s )l 2c a c h e l 3 1 。i n t e l 更是在新一代的c p u 中采用了8 0 核处理器结构，在6 5 w 的功耗下可以达到t f l o p s 运算能力。在专用处理器方面，t i 和s t 等公司研究采用n o c 技术，实现下一代异构多协处理器的移动终端平台架构，可以根据用户的功能需求进行设计，提高了芯片设计的灵活性。我国m p s o c s 架构芯片处于研制过程中，中国科学院龙芯3 号芯片将会采用6 4 核同构处理架构，国防科技大学也正在研究4 核同构高性能d s p ，西安电第一章绪论子科技大学正在研制基于4 核网络协处理器结构的高性能网络处理器。在技术研究方面，m p s o c s 共享存储器技术主要体现在两个方面，即数据交换技术和共享存储器分配技术。在数据交换技术方面，主要集中在n o c 技术上。它将各功能内核作为网络节点，通过互连网络结构实现分布式的数据交换和多线程协同处理功能【1 0 , 1 8 - 2 3 】。国外i n t e l 、斯坦福大学、普林斯顿大学等公司和研究机构提出了多种n o c 解决方案，并在实际芯片中进行了验证。其中，美国斯坦福大学采用n o c 技术研制的s i m d 处理器芯片，采用1 5 v 、0 1 5 u m 的c m o s工艺，单芯片集成度为2 1 0 0 万晶体管，最高工作频率可达2 9 6 m h z ，功能密度可达2 0 g f l o p s c h i p ，功耗密度可达6 1 g f l o p s w 。国内，合肥工业大学、西北工业大学等院校核科研院所也在进行相关技术的研究。目前，对于m p s o c s 互连仿真平台有以下几种：( a ) w i s c o n s i n 大学开发的g e m s ( g e n e r a le x e c u t i o n d r i v e nm u l t i p r o c e s s o r ) 模拟器，该模拟器以商业化的s i m i c s 虚拟机上实现的全系统m p s o c s 模拟器。该系统较为复杂，采用虚拟机方式使模拟速度降低，同时灵活性较差【。1 j4 、( b ) s e s c ( s u p e r e s c a l a rs i m u l a t o r ) 模拟器【2 j 。该模拟器目标是模拟目前大多数的处理器结构，包括单核乱序器结构、多线程处理器结构、c m p 、p i m ( p r o c e s s o ri nm e m o 巧) 以及线程级猜；涣l j ( t h r e a dl e v e ls p e c u l a t i o n ，t l s ) 等多种体系结构。该模拟器能够有效地模拟多线程并行的结构和线程级猜测的结构，但是对于c m p 结其片上互联网络的模拟比较简单，不太适用于模拟分片式c m p 及其片上互联网络的结构。( c ) 以s i m p l e s c a l a r 为基础的s i m g o l d s o n 模拟器【3 1 。该模拟器主要针对多内核结构处理器的c a c h e 性能进行分析。对于互连结构修改较为困难。( d ) 欧洲航天局r e s p 仿真平台1 4 。该平台支持l e o n 等开源多内核仿真平台，主要支持m p s o c s 体系结构的仿真。( e ) 基于n s 2 网络仿真软件的m p s o c s 仿真平台【5 】。该仿真平台可以支持任意路由方式的多内核互连仿真。1 3 本文的研究背景和结构安排本文是国家自然科学基金重大研究计划项目“多核处理器芯片中共享存储器互连技术 研究工作的一部分。为了有效验证m p s o c s 的新型体系结构的性能，我们提取了m p s o c s 系统中主要的时间和功耗参数，建立了在o p n c t 仿真软件环境下的m p s o c s 互连仿真环境。本文内容全文共分六章，章节安排如下：- 第一章简要介绍片上多核处理器的研究背景，当前片上多核处理器的发展状4m p s o c s 互连仿真软件设计况，阐明本文的组织结构。第二章详细介绍了片上网络涉及到的主要关键技术。主要介绍了片上网络中的各种拓扑结构、交换策略和路由算法等。第三章详细介绍了在o p n e t 仿真软件上搭建m p s o c s 系统仿真平台的实现过程。以m e s h 结构为例，说明了拓扑结构、存储转发交换和x y 路由算法的具体实现。第四章主要介绍了在搭建的m p s o c s 仿真平台的基础上得到的一些关键技术的仿真数据，并对这些数据进行分析。第五章搭建了基于o p n e t 的f f t 并行计算平台模型，对m p s o c s 实现并行f f t 算法进行了初步研究和实现，同时验证了改仿真平台的有效性。最后主要是总结本文的研究工作。第二章n o c 关键技术5第二章n o c 关键技术根据摩尔定律预测，未来十年中单芯片上晶体管数量将达到上百亿，工作频率达1 0 g h z 。研究表明，传统的基于总线的结构已成为一个通信瓶颈。因此v l s i 研究人员提出了m p s o c s 的新体系结构一片上网络互连结构州咖o r k o i lc h i p ，n o c ) ，其最初的想法源于采用网络互连的多c p u 计算机，其核心的思想是将计算机网络中的技术移植到芯片中来。n o c 是一种片上功能核基于包交换的通信结构。n o c 结构的各个核之间也采用与o s i 参考模型相似的计算机网络和片上通信的概念。本文建立的m p s o c s 互连模型就是基于n o c 结构的模型，因此本章对n o c 的关键技术进行了介绍。到目前为止，虽然对n o c 的研究刚刚起步，但世界上有近9 0 家研究机构对n o c 的各个层次问题进行了研究。片上网络的提出最早借鉴于并行计算机的互连网络，所以片上网络与并行计算机网络有很多的相同点。但是由于片上网络的资源所限，在路由器结构、路由算法、缓存资源、网络协议等方面与并行机又有一些不同。下面主要对n o c 中的拓扑结构、交换技术、路由算法等关键技术进行介绍。2 1 拓扑结构拓扑结构体现了n o c 中的通讯节点是如何在芯片中分布和连接的。n o c 拓扑结构的选择对系统性能和芯片面积具有明显的影响。拓扑结构除了要考虑普通网络中所关心的节点数量、边的数量、网络维度、网络直径、平均距离、对分宽度之外，还要考虑通信模式的嵌入属性，例如消息吞吐量，传输延迟，功耗，芯片面积【。这些对设计策略和内核到网络节点的映射起着重要的作用。为了有效分析n o c 多节点互连模型的性能，对一些参数进行定义：( 1 ) 节点的度( d e g r e e ) 一个节点可以直接连接的节点数量；( 2 ) n ：芯片内部所有互连节点数量；( 3 ) 网络直径( d i a m e t e r ) ：两个距离最远的节点之间互连的最小跳步数；( 4 ) 节点平均距离( a n e r a g ed i s t a n c e ) ：两节点之间的平均跳步数；( 5 ) n e t w o r kc o s t ：归一化的平均互连长度；( 6 ) b ：互连总线带宽；( 7 ) t o t a lb a n d w i d t h ：传输总带宽；( 8 ) b i s e c t i o nb a n d w i t h ：分段传输带宽。6m p s o c s 互连仿真软件设计2 1 1 全互连网络全互连结构网络是指所有节点采用电路交换方式，不经过路由直接互连的结构，s o c 中采用的总线互连就是其中的一种方式。目前采用全互连网络结构的方式有两种：总线结构和c r o s s b a r 结构。( 1 ) 传统总线结构( b u s )图2 1 总线结构总线结构是目前s o c 中普遍采用的互连总线方式。在这种结构中，当某个i p 需要占用总线时，首先需要向总线仲裁器申请总线占用；然后总线仲裁器根据不同i p 的申请要求进行总线分配；被分配总线的一对i p 之间通过共享总线进行通信，其它i p 之间的通信需要在下一个周期进行新一轮的竞争。共享总线结构的拓扑性能如表2 1 所示。表2 1 共享总线拓扑性能s w i t c hd e g r e end i a m e t e rld i s t a n c e1n e t w o r kc o s to t o m lb a n d w i d t hbb i s e c t i o nb a n d w i d t hb( 2 ) 交叉开关矩阵( c r o s s b a r )c r o s s b a r 结构是一种交叉开关矩阵方式，所有的功能i p 和交叉开关矩阵相连。与共享总线互连结构不同的是，当互相通信的内核不冲突时，c r o s s b a r 可以同时工作。图2 2 是典型的c r o s s b a r 互连结构图，其拓扑性能如表2 2 所示。第二章n o c 关键技术7f卜一i - -一c r o s s b a r卜+一卜一-一：c o n t r o i( r o u t i n g , s c h e d u l i n g )图2 2c r o s s b a r 互连结构表2 2c r o s s b a r 拓扑性能s w i t c hd e g r e end i a m e t e r1d i s t a n c eln e t w o r kc o s to ( m 2 )t o t a lb a n d w i d t hn bb i s e c t i o nb a n d w i d t hn b结论：从共享总线和c r o s s b a r 的拓扑性能比较可以看到，共享总线的n e t w o r kc o s t 是o ( n ) ，c r o s s b a r 的n e t w o r kc o s t 是o ( n 2 ) 。然而c r o s s b a r 的总线带宽为n b 远远大于共享总线带宽b 。2 1 2 线形排列结构和环网线形互连结构和环网结构，每个功能i p 不与其它i p 全部互连，只和邻近的两个i p 互连。在这种结构中，通过多级互连和转接，任意两个i p 可以进行通信。目前常用的互连结构有两种：( 1 ) 线形排列结构( l i n e a ra r r a y )l i n e a ra r r a y 结构如图2 3 所示。任意一个i p 只与相邻的两个i p 互连，两端的i p 只与相邻的一个i p 互连，任意两个i p 之间可以采用固定路由方式，通过多跳实现互连。其网络拓扑性能如表2 3 所示。图2 3l i n e a ra r r a y 互连结构8m p s o c s 互连仿真软件设计表2 3c r o s s b 盯拓扑性能s w i t c hd e g r e e2d i a m e t e rn 1d i s t a n c e砣3 nn e t w o r kc 0 s to ( n )t o t a lb a n d w i d t h2 ( n - i b i s e c t i o nb a n d w i d t h2 b( 2 ) 环形结构( r i n g )r i n g 结构是l i n e a ra r r a y 结构的一种改进，其特点是任意一个i p 只与相邻的两个i p 互连，两端的i p 也互相连接，式，选择最短路径，通过多跳实现互连。表2 4 所示。任意两个i p 之间可以采用双向路由方其结构如图2 4 所示，网络拓扑性能如2 1 3 多维m e s h 结构图2 4 r i n g 互连结构表2 4r i n g 拓扑性能s w i t c hd e g r e e2d i a m e t e rn 2d i s t a n c e1 3 nn e t w o r kc o s td ( )t o t a lb a n d w i d t h2 n bb i s e c t i o nb a n d w i d t h4 b多维结构是一种两维空间以上的互连结构，典型的结构有m e s h 结构、t o m s结构和c u b e 结构。和一维结构不同，多维结构中一个功能i p 可以和2 个以上的内核直接互连，这样可以提高更多的路由策略，从而数量众多的内核互连。目前，在1 6 内核以上的芯片中，通常采用的2 维m e s h 和t o r u s 作为互连结构。多维结构可以用k - a r y 和d c u b e 来表示，其中d 是互连维数，k 为表示每一维空间中的节点数。对于这种互连结构，其拓扑性能可以归纳为表2 5 。第二章n o c 关键技术9表2 5k - a r y rd - c u b e 网络拓扑性能s w i t c hd e g r e edd i a m e t e rd ( k 一1 )d i s t a n e e- 4 ) 5d ( k 1 )n e t w o r kc o s td ( )t o t a lb a n d w i d t h2 n bb i s e c t i o nb a n d w i d t h2 k ( d - i ) 6( 1 ) 2 - dm e s h 网络图2 5 是典型的1 6 节点2 维m e s h 结构。s k u m a r s 提出了基于该结构的互连方案c l i c h 6 结构。其d = 2 ，k = 4 ，网络拓扑性能如表2 6 所示。图2 52 - d m e s h 互连结构表2 61 6 节点2 - dm e s h 网络拓扑性能n u m b e ro fn o d e sn1 6s w i t c hd e g r e e2d i a m e t e r2 ( 万一1 1d i s t a n c e2 3 x nn e t w o r kc o s t2 ( n 一瓜1t o t a lb a n d w i d t h2 n bb i s e c t i o nb a n d w i d t hn b( 2 ) 2 - dt o r u s 网络和l i n e a ra r r a y 结构与t o r u s 结构类似。为了有效减小路由长度，在2 - dm e s h 网络的基础上，提出了改进的2 - dt o r u s 结构。t o r u s 拓扑虽然在物理形式上与m e s h 相似，但由于其存在很多环路，因此在路由算法和路由仲裁方面要复杂许多。t o m s 结构的路由节点更规则，且路由节点的结构都一样，因此扩展性得1 0m p s o c s 互连仿真软件设计到了加强。图2 6 是典型的1 6 节点2 dt o r u s 互连结构图，其性能如表2 7 所示。( 3 ) 3 - dc u b e 网络叫刖州yil t j1 一一ti、广 九yyl上上_ jl 。一k ， ￥l r jl 一一乜曲nj 爿图2 6 2 d t o r u s 互连结构表2 71 6 节点2 dt o r u s 网络拓扑性能n u m b e ro fn o d e sn1 6s w i t c hd e g r e e4d i a m e t e r丽d i s t a n c el 2 f f - nn e t w o r kc o s t2 t o t a lb a n d w i d t h2 n bb i s e c t i o nb a n d w i d t hn b图2 73 - dc u b e 互连结构3 - dc u b e 结构是一种3 维立体结构，图2 7 是一种3 - c u b e 的网络互连结构。在这种结构中，每一维空间中有2 个节点，共有3 维，其网络拓扑结构如图2 7所示，网络拓扑性能如表2 8 所示。多维互连结构是一种有效的片上众核互连方式，目前多数采用2 - dm e s h 和2 - dt o r u s 结构解决数量小于6 4 的多内核互连。第二章n o c 关键技术2 1 4 树形结构表2 83 - c u b e 网络拓扑性能n u m b e ro fn o d e sn8s w i t c hd e g r e e3d i a m e t e r6d i s t a n c e- 3n e t w o r kg o s td ( )t o t a lb a n d w i d t h1 6 bb i s e c t i o nb a n d w i d t h6 b树形结构是一种典型的分层互连结构，典型的树形结构有胖树( f a tt r e e ) 正f 连结构和蝴蝶( b u t t e r f l y ) 结构。( 1 ) 胖树结构( f a tt r e e )根据每个交换节点所包含i p 数量k ，可以定义k - a r y 胖树结构，根据其节点层数d ，可以定义其空间维数，其网络拓扑性能如表2 9 所示。表2 9k - a r yf a tt r e e 网络拓扑性能n u m b e ro fn o d e snk dn u m b e ro fs w i t c h七ds w i t c hd e g r e e后+ 1d i a m e t e r2 dd i s t a n c ed + 2n e t w o r kc o s tn ( 1 0 9 2n 1 )t o t a lb a n d w i d t h2 k ( u 1 ) bb i s e c t i o nb a n d w i d t hk b以典型的2 - a r yf a tt r e e 为例，在每个节点上有两个叶子，其网络拓扑结构如图2 8 所示，其网络拓扑性能如表2 1 0 所示。1 2m p s o c s 互连仿真软件设计图2 82 - a r yf a tt r e e 互连结构表2 1 02 - a r yf a tt r e e 网络拓扑性能n u m b e ro fn o d e sn2 dn u m b e ro fs w i t c h2 ds w i t c hd e g r e e3d i a m e t e r2 dd i s t a n c ej + 2n e t w o r kc o s tn ( 1 0 9 2n 一1 )t o t a lb a n d w i d t h4 ( n 1 ) bb i s e c t i o nb a n d w i d t h2 b( 2 ) 蝴蝶( b u t t e r f l y ) 结构b u t t e r f l y 结构是一种增强的树形结构，在这种结构中，i p 之间通过交换节点进行互连。与f a tt r e e 结构不同，k - a r yb u t t e r f l y 结构中每一级交换节点采用的是全互连结构，如图2 8 ，这种结构可以采用c r o s s b a r 结构，也可以采用总线结构，这样可以增强路由性能，其网络拓扑性能如表2 1 1 所示。第二章n o c 关键技术2 1 5 拓扑结构比较图2 82 - a r yb u t t e r f l yt r e e 互连结构表2 1 l2 - a r yb u t t e r f l yt r e e 网络拓扑性能n u m b e ro fn o d e sn2 dn u m b e ro f s w i t c h2 d - ! ds w i t c hd e g r e e2d i a m e t e rd + 1d i s t a n c ed + 1n e t w o r kc o s to ( u d )t o t a lb a n d w i d t h2 dd bb i s e c t i o nb a n d w i d t hn b | 2目前在互连i p 内核数量多的情况下，通常采用的拓扑结构有2 dm e s h 、t o r u s 和胖树结构三种，针对这三种结构从d e g r e e 、d i a m e t e r 、a v e r a g ed i s t a n c e和n e t w o r kc o s t 四个技术指标进行比较，表2 1 2 是针对1 6 内核和6 4 内核的比较结果。，从表2 1 2 可看到，f a tt r e e 结构在d i a m e t e r 、d e g r e e 、a v e r a g ed i s t a n c e 和n e t w o r kc o s t 等方面的指标要高于其它两种结构。而且当内核数量n 增加时，三种结构的d i a m e t e r , a v e r a g ed i s t a n c e 和n e t w o r kc o s t 指标会迅速增加，尤其是n e t w o r kc o s t 指标直接关系到芯片网络的布线资源。因此当内核数量大时( 如超过1 0 2 4 ) ，单纯的f a tt r e e 结构不再适合于片上网络的互连。432lo1 4m p s o c s 互连仿真软件设计表2 1 21 6 内核和6 4 内核网络拓扑性能愁n = 1 6n = 6 4淤、m e s ht o m sf a t t r e em e s ht o r u sf a t t r e ed e g r e e2 ，3 ，443443d i a m e t e r6481 481 0a v e r a g ed i s t a n c e2 625 55 349 2n e t w o r kc o s t2 43 24 81 1 21 2 83 2 0m e s h 和t o m s 结构具有相似的性质。m e s h 结构的边沿和顶点位置节点相对闭塞，而t o m s 结构是在m e s h 结构的边界节点上增加了一条长的环路。因此，t o r u s 的性能比m e s h 有很大的提高。m e s h 结构规则、简单易于实现；t o u r s 结构由于存在许多环路，所以在路由算法和仲裁方面要复杂很多。2 1 6 几种新型拓扑结构尽管二维网格和和环形网实现起来比较简单，但是在连接大量的处理机时，网络延迟将会严重地影响系统的性能。下面介绍几种提出的几种新型拓扑结构。1 反图拓手b ( i n v e r t e d - g r a p ht o p o l o g y )为了能连接更多的结点，可以把传统互连网络中的点与边的功能互换，从而得到一种新的结构，称为反图拓手b ( i n v e r t e d g r a p ht o p o l o g y ) 。在这种结构中，节点的位置由原来的交叉点换到边上，使得在同样的k 和刀的网络中，反图拓扑互连网络比常规网络能连接更多的结点。虽然反图拓扑可以连接更多的节点，但是与传统的网格相比，节点可使用的通信带宽降低，网络吞吐率降低。图2 94 元2 维反图拓扑互连网络图2 1 04 元2 维n i n为了减少远程通信的网络延迟，论文1 2 1 提出一种将反图拓扑和交叉开关相结第二章n o c 关键技术合的新型互连网络n i n 烈o v e li n t e r e o n n e c t i o nn e t w o r k ) 。该结构用交叉开关分别把水平方向和垂直方向的寻径器相连，从而减少了点到点的网络通信延迟。2 基三分层互连网络 1 0 l ( t r i p l e b a s e dh i e r a r c h i c a li n t e r c o n n e c t i o nn e t w o r k ，t h i n )t h i n 是一种能够降低节点度、减少网络链路数和缩短网络直径的新型片上网络互连网络。它是一种层次化的、可扩展的互连拓扑结构。该结构的第0 层是单个节点，如图2 1 1 ( 1 ) 所示。通过3 条通信链路将3 个节点彼此互连形成一个三角形，从而构成该结构的第1 层。如图2 1l ( 2 ) 所示，1 层网络是构造t h i n 的基本构件。在基本构件的基础上将每个节点用一个基本构件网络代替，就会得到更高层的一个三角形网络结构，重复这一过程，可以构造出满足应用需求的任意层次的t h i n 。仿真结果表明，t h i n 网络具有较低的网络延迟和较高的平均吞吐量，适于用来构建核间互连的片上网络。o入o o( 1 ) 0 层t h i n ( 2 ) l 层t h i n( 3 ) 2 层t h i n3 w k r e c u r s i v e 结构1 4 1图2 1 1 基三分层互连网络w k - r e c u r s i v e 中四个节点组成一个全互连的网络，而每个全互连网络中的每个节点分别与其相邻的全互连网络的节点相连接。w k r e c u r s i v e 具有高度的对称性，通信效率较高。1 6m p s o c s 互连仿真软件设计( a ) w k ( 4 , 0 )( b ) w k ( 4 ，i )( c ) w 4 , 2 )图2 12w k - r e c u r s i v e 结构3 蜘蛛网形拓手b ( s p i d e m e t )温东新等人【6 】在2 0 0 8 年提出一种介于m e s h 和t o m s 之间的结构。如图所示，s p i d e m e t 是以一个正，z 边形为中心向外扩展的结构，相邻多边形的对应点相互连接。该结构有很好的扩展性，在平均最短路径和可平面化方面具有很大优势。图2 1 3s p i d e m e t 拓扑结构g o c t a g o n 结构为了解决s o c 系统中总线结构存在可扩展性差的缺陷，2 0 0 2 年，k a r i m 等提出了o c t a g o n 结构，该结构中每个节点可扩展成一个基本的o c t a g o n 结构并可无限扩展。其缺点是该结构会明显增加布线的复杂性，而且随着结构的不断扩展，连接两个o c t a g o n 结构的交换节点很容易变成通信的瓶颈，对网络的延时和吞吐量有很大的影响。第二章n o c 关键技术1 7( a ) o c t a g o n( b ) 级联o c t a g o n图2 1 4o c t a g o n 结构5 s t o r u s 结构朱晓静等人【7 】提出一种类似楼梯( s t a i r s ) 、和t o r u s 拓扑相似的s t o r u s 结构，如图2 1 5 所示。该结构域同等规模的t o r u s 具有相同的连接数，但在不同模式的负载下，s t o r u s 的平均延时比t o r u s 约小2 0 一1 5 0 。尤其是在热点负载条件下，s t o r u s 的饱和吞吐量是t o r u s 的1 3 倍左右。( 0 ，3 )夕形rb弋，毯弋( 3 ，3 )( 0 ，o )( 3 ，o )图2 1 5s t o r u s 结构6 基于最优化模型的结构刘政等人提出了一种基于最优化模型的结构。仿真结果表明，在同等网络规模下，该网络拓扑的吞吐量与m e s h 相似，但比o c t a g o n 和r i n g 的要好，主要原因在于该网络拓扑和m e s h 的链路数比o c t a g o n 和r i n g 要多，网络阻塞减少了，从而使网络时延和吞吐量具有较好的性能。m p s o c s 互连仿真软件设计图2 1 6 最优化模型结构2 2 基于包的交换技术包交换技术关注的是数据包是怎样从输入通道交换到输出通道的，即交换机制定义了分组通过交换结构的方式。采用的包交换技术不同，所产生的延迟就不同，网络的延迟与包交换技术直接相关。交换技术主要有三种：存储转发交换( s t o r e a n d f o r w a r d ，s & f ) ，虚切通交换( v i r t u a lc u t t h r o u g h ，v c t ) 和虫孔交换( w o r m h o l es w i t c h i n g ，w s ) 。( 1 ) 存储转发交换( s t o r e a n d f o r w a r d ，s & f )存储转发是计算机网络以及交换结构中广泛采用的一种交换机制。其基本原理是当节点将一个数据包完整接收存储在缓存中后，再将该数据包进行转发出去。因此存储转发对路由器缓存要求比较高，特别是在数据包长度比较大的时候。消息被切割成分组，每个分组都包含路由信息，因而可以独立选路，绕开故障或者拥塞区域。在发往下一跳结点之前，当前结点要把分组整个接收并存储在本地，这使得平均时延与源节点和目的节点间的跳数成正比。对于规模大的网络结构，这将导致较大的时延，因而不能很好的满足扩展性要求。假设一个长度为三的数据包采用存储转发方式，由源节点经过日个节点到达目的节点，则该数据包的延迟可由下式决定：t = ( b 矿+ z ) h，1