（计算机应用技术专业论文）片上网络拓扑结构及其路由机制的研究.pdf

南京邮l u 人学硕f 研究生学位论文摘要 摘要 随着芯片制造技术的发展，单个芯片中可以集成更多的i p ( i n t e l l e c t u a lp r o p e r t y ) 核， 片上系统的总线结构已经不能适应系统芯片的发展，因此一种全新的集成电路体系结构 n o c ( n e t w o r k s o n c h i p 片上网络) 应运而生，它的核心思想是将计算机网络技术移植到芯片 设计当中。由于片上网络具有良好的空间可扩展性，提供了并行通信能力，以分组交换作 为基本通信技术，采用全局异步局部同步的通信方式，因而能从体系结构上彻底解决 总线架构带来的问题。 片上网络的复杂度体现在拓扑结构和路由算法这两部分，本文正是对这两个方面进行 了研究，重点介绍了直接型网络结构和间接型网络结构，以及常用的路由技术和算法。在 研究拓扑结构的基础上，本文对2 d m e s h 结构做出改进，将改进后的拓扑与2 d m e s h 、2 d t o r u s 进行理论上的分析；针对m e s h 结构中常用的防死锁路由算法x y 路由算法，提出 与其相对应的路由算法，并证明了该路由算法的无死锁性。 最后，在o p n e t 上建立2 d m e s h 、2 d t o r u s 和改进后的拓扑的模型，对它们进行仿真， 并对仿真结果进行了分析，验证了文中理论分析的正确性。 关键词：片上网络，拓扑结构，路由算法，长边，性能分析 南京邮电大学硕士研究生学位论文 a b s t r a c l a b s t r a c t w i t ht h ed e v e l o p m e n to fc h i pm a n u f a c t u r i n gt e c h n o l o g y , as i n g l ec h i pc a l li n t e g r a t e m u l t i p l e i pc o r e s ，s ot h et r a d i t i o n a ld e s i g no fb u sa r c h i t e c t u r ec a n n o tb es u i t a b l ef o r t h e c o n t i n u o u sd e v e l o p m e n to fs y s t e m o n - c h i p t h e r e f o r e ，n o ct h a ti sn e wi n t e g r a t e dc i r c u i t a r c h i t e c t u r ea r i s e sa tt h i sm o m e n t ，w h o s ea r c h i t e c t u r ea d o p t sd e s i g nc o n c e p t sa n dm e t h o d o l o g i e s f r o mc o m p u t e rn e t w o r k s n o ch a st h eg o o ds p a t i a le x t e n d i b i l i t y , a n dp r o v i d e st h ec a p a c i t yo f p a r a l l e lc o m m u n i c a t i o nb a s e do np a c k e ts w i t c h i n g ；i tu s e st h eg l o b a l l ya s y n c h r o n o u s - l o c a l l y s y n c h r o n o u sc o m m u n i c a t i o n ，s oi tc a ns o l v et h ep r o b l e m sb r o u g h tb yb u s f l a m ea r c h i t e c t u r e t h ec o m p l e x i t yo fn e t w o r k o n - c h i pi si n c a r n a t e di nt h et o p o l o g ya n dr o u t i n ga l g o r i t h m ，t h i s p a p e r d i dr e s e a r c ho nt h e s et w oa s p e c t s i ti n _ 仃o d u c e dt h ed i r e c ta n di n d i r e c tn e t w o r k a r c h i t e c t u r e ； e x p o u n d e dp o p u l a rr o u t i n ea l g o r i t h m s o nt h eb a s i so fr e s e a r c ho nt o p o l o g y , i m p r o v e dt h e 2 d - m e s h , a n dc o n d u c t e dt h e o r e t i c a la n a l y s i so np e r f o r m a n c ec o m p a r i s o na m o n gt h ei m p r o v e d t o p o l o g y , t h e2 d m e s ha n d2 d - t o m s ；t h i sp a p e rb u i l tt h ec o r r e s p o n d i n gr o u t i n ga l g o r i t h mf o r i m p r o v e dt o p o l o g yb yx yr o u t i n ga l g o r i t h m ，w h i c hi su s u a l l yu s e di nm e s h ，a n dh a sp r o v e nt h a t o u rr o u t i n ga l g o r i t h mi sn o n d e a d l o c k f i n a l l y , t h i sp a p e rb u i l tm o d e lf o r2 d m e s h ，2 d - t o r u sa n dt h ei m p r o v e dt o p o l o g yo n o p n e t , t h e nd i ds i m u l a t i o no no p n e ta n da n a l y z e dt h er e s u l t s i ti sc o n f i r m e dt h et h e o r e t i c a l a n a l y s i si sc o r r e c t k e y w o r d s ：n e t w o r k s - o n - c 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 ，l o n ge d g e s ，p e r f o r m a n c ea n a l y s i s i i 南京邮电大学学位论文原创性l 声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 卤蒴同期：坐咝蛆坦墨 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。 论文的公布( 包括刊登) 授权南京邮电大学研究生部办理。 研究生签名： 叠垄 导师签名： 南京l i i l 5 l u 人学坝i 研究生学位论义第一章绪论 1 1 片上系统 第一章绪论 随着芯片制造技术的发展，单一芯片可以提供的逻辑资源越来越丰富。集成电路的设 计人员不再受限于芯片的资源，可以在芯片内部集成多个异构的计算单元，从而形成片上 系统( s y s t e mo nc h i p ，s o c ) 。s o c 通常指在单一芯片上实现的数字计算机系统。该系统 应包含两个基本部分：硬件部分和软件部分。硬件部分包括u p 、b u s 、r o m r a m 、i op o r t 等计算机系统的基本部件；软件部分主要指操作系统，也可以包括重要的应用软件。由于 s o c 可以充分利用己有的设计积累，显著地提高a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e d c i r c u i t ) 的设计能力，因此发展非常迅速，引起了工业界和学术界的关注。当今主流的s o c 设计中都采用全局同步的设计方法，把多个知识产权核i p 通过总线结构集成到芯片上，这 种基于片上总线( o c b - o n c h i pb u s ) 的s o c 设计可以提供高性能的互连，因具有结构简单、 易综合的特点而被广泛应用。 在s o c 芯片中一般可以集成一个或几个处理器，还有大量内存、总线结构、外部设备、 协处理器以及i o 通道等。这些芯片己具有独立完成某项功能的能力，甚至可以将电子整 机的功能也集成在单一芯片上。现代工业所拥有的巨大的集成能力，使早期尚处于研究阶 段的尖端科技，迅速的应用于各个方面【l 】。 片上系统由于不仅可以带来高处理，高可靠性，而且还因为其占用空间有限带来的优 势，越来越受到集成电路设计者的关注，在芯片上集成尽可能多的相关功能部件，是集成 电路设计者所追求的目标。目前利用片上系统的设计技术已经可以在单一芯片上完成某一 特定的功能。例如，p h i l i p ss e m i c o n d u c t o r 公司采用规模是3 5 0 0 万晶体管，大小为1 0 4 m m 2 的设计的m p e g 编码解码芯片，就是完整的片上系统。 s o c 的发展方向离不开实际应用领域的需求牵引，它不仅是要在单一的芯片上集成一 个处理器，更主要是在片上集成大量内存、外部设计、协处理器以及i o 通道等。这种集 成单一处理器的片上系统由于同时集成了内存，i o 通道等设备，不仅满足系统的处理计 算能力，更主要的是满足系统的实时存取、交互需求。从某种意义上来说，具有单一处理 器的片上系统是具备某一特定功能的整机系统，是为了满足人类对片上系统某一特定方面 的需求。 片上系统另一发展方向则是希望在单一芯片上集成两个甚至更多的处理器的片上系 统。具有多核处理器的片上系统类似于并行计算机系统，可以提供更快速计算，更高效协 1 塑墨业! ! 叁兰丝! ! 型壅竺兰丝堡兰笙二至笪丝 统。具有多核处理器的片上系统类似于并行计算机系统，可以提供更快速计算，更高效协 调通信能力，成为片上系统同后发展的另一重要方向。 目前，s o c 主要应用在嵌入式设备中，利用i c 并行处理数值计算、通讯、图像及多媒 体等任务，这样可以大大提高系统性能，减小系统的体积和功耗。根据摩尔定律，单芯片 上集成的逻辑单元数量将会成倍增长。根据国际半导体技术蓝图i t r s ( i n t e r n a t i o n a l t 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 r s ) ，i c 厂商将能制造出线宽小于5 0 n m ，且工作主频 超过1 0 g h z 的芯片，届时制约s o c 发展的将不是制造工艺，而是深亚微米技术条件下的时 钟偏移、抖动、高功耗以及开发周期等问题。 1 2 片上系统面临的挑战 随着深亚微米超大规模集成电路工艺技术的成熟及进一步发展，芯片设计业面临着严 峻的问题：工作速度越来越快，开发周期越来越长，设计质量越来越难于控制，设计成本 也越来越高。虽然s o c 的设计规模已达到一定的程度，并且功能也比较强大，但也存在以 下问题，这些问题使它越来越难以满足以上设计要求： ( 1 ) 可扩展性面临的问题 总线结构是s o c 的主要特征，但随着电路规模越来越大，片上集成的单元越来越多， 数据处理量也随之变大，总线结构的可扩展性差的问题就越来越突出：虽然总线可以有效 地连接多个通讯方，但地址资源是有限的，有限的地址资源将成为扩大电路规模的瓶颈； 总线由多用户共享，但一条总线无法支持一对以上的用户同时通讯，并且资源的利用率很 低，不能提供很好的并行处理能力。 ( 2 ) 单一时钟同步问题 总线结构要求全局同步，但是随着工艺特征尺寸越来越小，工作频率迅速上升，达到 1 0 g h z 以后，连线延时造成的影响将严重到无法设计全局时钟树的程度。而且由于时钟网 络的庞大，其功耗将占据芯片总功耗的大部分。由单一系统时钟同步全芯片的工作将极其 困难。 综上所述，全局同步片上总线设计的s o c ，其复杂度会随着系统规模呈指数增长。因 此有必要将设计中全局问题分散到局部去处理，也就是降低全局通讯模块和局部计算模块 设计的相关性【2 1 。所以在1 9 9 9 年，一种全新的集成电路体系结构- n o c 就被提出来了， 其核心思想是将计算机网络技术移植到芯片设计中来，从体系结构上彻底解决总线架构带 来的问题【引。 2 南京邮i u 人学硕i 研究生学位论义 第一帝绪论 1 3s o c 的发展片上网络 集成电路制造技术仍然在按着摩尔定律发展，单芯片系统中将可容纳更多的i p ，多达 上百个【4 】。面对如此大规模的系统芯片，无论从集成电路系统芯片的设计方法学角度出发， 还是从系统芯片本身的系统结构出发，都需要发展一种新的片上通信架构来适应未来大规 模的芯片，这种新的片上通信架构需要具有更高的灵活性，更强的可扩展性，能够在深亚 微米工艺下避免过长连线的出现而不带来信号的衰减，而且能够从本质上带来系统的并行 性，提高系统的吞吐率，这种新颖的片上通信架构就是片上网络n o c 。n o c 用基于网络设 计的技术来分析和设计已有的s o c s ，即将每一个s o c 看作微型网络的一个组件，可以设计 一种微型网络层次结构来实现各个s o c 间的互联。所谓的微型网络层次结构实际上是协议 栈的一个延伸。基于此，对于s o c 互联的电子、逻辑以及功能特性都可以较好地进行抽象。 n o c 技术的出现，顺应了集成电路技术的发展趋势。 首先，随着半导体技术的进步，在单块芯片中已经可以集成数千万计的晶体管，这就 允许设计者在系统芯片中集成多个处理器核，组成更加复杂的系统来满足电子产品对功 能、体积和处理速度越来越高的要求。 其次，当前多系统芯片多采用总线作为通信架构，虽然总线结构简单，协议简明，相 对比较容易实现，但是总线结构要求多个处理器共享系统带宽，这就限制了通讯效率的提 高。n o c 不仅具有良好的空问可扩展性，还提供了很好的并行通讯能力，使用类似网络的 通讯方式，可以支持多对处理器同时通讯，能极大提高通讯效率。 最后，在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 1 ，每一个资源 节点都工作在自己的时钟域，而不同的资源节点之问则通过通讯节点进行异步通讯，从而 很好地解决了单一时钟同步的问题。 片上网络因其规则的物理布局和通信网络结构，使得通信性能变得可预测。同时片上 网络规则的通信结构为高层模型到最终的实现两者性能上的对比提供了依据。从物理性能 的角度分析，片上网络结构决定了其版图物理性能的可预测性。除时钟、电源布线外，交 3 塑墨业! 皇叁兰婴! ：竺! ! ! 竺兰! 兰笙塞笙二童笙堡 换单元i 日j 的互连长度以及带宽都是固定不变的。而设计的不确定性和不规则性都限制在资 源单元内部，对于其它资源单元没有造成影响；从设计和验证时间角度分析，片上网络基 于模块以及通信模块的可重用性使得设计和验证的时间都可预测，由于片上网络结构的规 则性，限制了设计空间探索的自由度，将任务分配等设计问题划分到了资源单元内部，进 而将整体应用划分为更为独立的任务。上述特点使得片上网络系统的设计在很大程度上独 立于具体的实现阶段，能够更好的进行模块化设计。 n o c 不同于一般网络的特点，就在于高度的本地化以及可决定性。n o c 作为一个本地 的高性能网络与现有的大范围分布、由多处理器所构成的网络一样具有相同的需求和局限 性。 n o c 的另一个特点是设计的特定性。在常见的网络通信中强调的是通用目的通信以及 模块化设计，而在n o c 中，通信网络的构造是设计在硅片上的，因此只有在为组件指定某 一个抽象网络接口时，才需要进行标准化工作。而在其他的情况下，网络体系自身就应该 能够裁减，以适应特定的某个或一类应用需求。 片上网络是在多核时代倍受注目的技术，它能够支持基于数据包的通信，有能力为任 何的i p 元件提供传输功能。n o c 是一个弹性的和可扩展性的片上微网络，由大量的异步处 理单元组成，它能比传统的芯片传输方式提供更高的效率，具有模块化和资源共享的特色， 更重要的是，它能让基于i p 及处理器核心的s o c 设计更简单快速，i p 也能够在不同的设计 方案中重复被利用。 1 4 国内外研究动态 1 4 1 国外研究动态 随着技术的发展和应用的深入，在多核时代，越来越多的研究机构认识到片上互连网 络的巨大潜力，纷纷参与其研究中，因而也推动了它的发展，让片上互连网络研究成为活 跃的学术前沿领域。目前国际上有超过3 0 个研究单位正在积极从事片上互连网络的工作【6 】， 其中影响较大的有瑞典皇家技术学院、斯坦福大学和荷兰菲利普研究实验室等。从2 0 0 0 年 起，有关片上互连网络的研究论文大量涌现【7 8 一】，研究课题包括片上互连网络系统结构、 多任务映射、网络系统路由及通信协议设计、路由节点与网络接口设计、多时钟处理与网 络功耗研究、物理布局布线设计等方面。并且很多科学研究所提出了各种各样的创新的芯 片上网络架构，i ：匕女h m a n c h e s t e r 、s t a n f o r d 、t a m p e r e 、t e c h n i o n 、以及飞利浦、意法半导 4 南京邮l 巳大学顾i ：形f 究生学位论文第一章绪论 体；手1 v t t 技术研究中心等产业研究实验室。目前有许多n o c 构架被提出，包括r i n g 、 s p i d e r g o n 、2 d m e s h 、t o m s 等等，会对多处理器片上系统的效能和成本产生重大影响。 1 4 2 国内研究动态 国内在n o c 方面的研究滞后于国际先进水平约两年的时间，中国集成电路产业的整体 水平落后国外约1 0 年时间，但n o c 作为一个崭新的集成电路设计理论体系正处于初创阶段， 如尽早立项支持n o c 相关技术的理论研究工作，一定能够继续保持与国际前沿同步的局面。 中国若能够全面开展n o c 学术领域的前沿工作，将为大量创新成果的出现提供一个空间。 因此自2 0 0 5 年开始，国内一些研究型大学和研究所也陆续开展了片上网络方面的研究工 作，研究内容主要集中在流量分析，拓扑结构【1 0 1 2 】路由算法【1 3 】、通信协议【1 4 】，低功耗 和网络时钟【l5 】等方面。总体来说，国内对于片上互连网络方面的研究尚处于起步阶段，与 国外相比存在较大的差距，需要快速的开展这方面的深入研究。 1 5 论文的主要研究内容 本文对片上网络做了探索性的分析和研究工作，论文的主要工作和取得的成果如下： ( 1 ) 对n o c 的理论基础进行了研究，分析了n o c 的节点结构、拓扑结构、设计流程、设计 方法以及路由机制等。 ( 2 ) 着重对片上网络的拓扑结构进行研究，并在此基础上，提出基于2 d m e s h 结构的改进 后拓扑及其路由算法，并将改进的拓扑结构与现有的经典拓扑进行性能分析与比较。 ( 3 ) 分析并实现了改进的拓扑结构的免死锁路由算法，确保在免死锁的前提下实现最短路 径的选择，使系统的执行代价最小。并在o p n e t 建立仿真模型，验证理论分析的正确 性。 1 6 论文结构及内容安排 第章：绪论。主要介绍了论文的背景，研究该课题的意义，目前国内外的研究现状，论 文的主要研究内容和组织结构等。 第二章：片上网络的相关概念。介绍并分析t n o c 的结构，阐述了n o c 的通信协议，设计 流程和实现n o c 的关键技术及设计过程中需要考虑的因素。 第三章：片上网络的拓扑结构。建立n o c 拓扑数学模型，阐述了内部互连网络的分类，重 南京邮l u 人学坝l ：研究生学位论文第一章绪论 点讲述了直接网络拓扑，对两种直接网络2 d m e s h 结构和2 d t o r u s 结构进行了深 入研究，并将各种拓扑的性能进行了比较，提出在2 d m e s h 基础上改进后的拓扑， 并将该拓扑与2 d m e s h 干1 1 2 d t o m s 这两种拓扑进行性能比较。从理论上分析改进 后拓扑的性能优于2 d m e s h 和2 d t o m s 。 第四章：片上网络的路由机制。介绍了交换机制、虚通道等概念，提出了改进后的拓扑结 构最短路径路由算法，并在o p n e t 上进行了仿真模型的建立，从而验证理论分析 的正确性。 第五章：总结与未来工作。主要对全文进行了总结，并提出了未来的研究工作。 6 南京邮电人学颂上研究生学位论义第二章片上网络相关概念 第二章片上网络相关概念 片上网络中很多概念与技术都是借鉴并行计算机的互连网络，所以片上网络与并行计 算机网络有很多的相同点：都支持包通信、可扩展、提供透明的通信服务等，不同的是并 行计算机的互连网络是一个板级的网络，而片上网络是个芯片上的网络，在片上网络中 没有专门的协议处理机，所有的协议都必须由硬件处理，这就要求片上网络的网络协议不 能太复杂。这些差异都是由片上网络本身的特点造成的，也正是由于片上网络与并行机有 着这些差异，所以有必要单独的整理和总结并且研究片上网络中的拓扑结构与路由算法和 路由技术，这些都是本文中研究的内容。 2 1 片上网络节点结构 n o c 由资源节点( r e s o u r c en o d e ) 、交换节点( s w i t c hn o d e ) 以及通道( c h a n n e l ) 三部分组 成，通道是交换节点和交换节点之间，或是交换节点和资源节点之间的两条单向的点到点 总线，如图2 1 所示。 s 交换节点 r 资源节点 通过 图2 1n o c 原型芯片系统结构图 片上互连网络中允许存在各种类型的资源节点，它完成广义的计算任务，典型的资源 节点可以是一个处理器核、内存、个用户自定义硬件模块或者是其他任何可以插入插槽 并且可以和网络接口相匹配的i p 模块。资源节点在结构上和功能上相异的，因此需要考虑 映射问题。资源节点的映射主要解决不同的资源节点放置什么组件的问题。资源节点的映 射过程需要将片上网络各节点间的通信量，以及通信时的功耗、时延等进行建模，然后由 7 南京邮电人学硕j j 研究生学位论文第一二章片 二阳络相关概念 这些模型结合具体的映射要求，如功耗优先或时延优先，得到最终的映射结果。 资源节点不能直接与网络相连，需要通过网络接口与交换节点相连接入网络，在图2 1 中网络接口未画出，网络接口负责完成数据拼接与协议转换，它将资源节点内的通信数据 封装到片上互连网络传输协议后送入网络，接收片上互连网络中的数据并转换为资源节点 可用的数据。 网络接口在结构上可以分为资源节点无关部分和资源节点相关部分，如图2 2 所示【l6 1 。 资源节点无关部分主要用于完成片上网络通信协议，以及与交换节点的数据交互，需要处 理片上网络的时序、数据缓冲和传输同步等问题，资源节点无关部分具有很好的可重用性。 而资源节点相关部分主要完成和资源节点的数据交互，可重用性较差。为增强网络接口的 可重用性，可以在资源节点和网络接口间采用相同的互连结构。 图2 - 2 网络接口结构示意图 交换节点又称通讯节点或者是路由器，是片上网络的重要组成部分，其核心是一个交 换开关，图2 3 所示的是一种通用的交换开关结构，图中的输入通道( i n p u tc h a n n e l s ) 和输 出通道( o u t p u tc h a n n e l s ) 用于和相邻交换节点的相应通道相连，而注入通道( i n j e c t i o n c h a n n e l ) 和弹出通道( e j e e t i o nc h a n n e l ) 用于和本地的资源节点相连，每个数据通道都配有缓 冲区以及链路控制器( l i n kc o n t r o l l e r ，l c ) 。各部件描述： 缓存器。硬件结构为先进先出的缓冲器，用来存储传输中的消息，每个输入物理 通道和输出物理通道都有相应的缓冲器。 交叉开关。交叉开关将路由器内部的输入缓存器连接到输出缓存器，相对一个输 出通道而言，如果路由器有n 个输入通道，那么此输出通道就有n 条输入数据线， 任意时刻只有一条输入数据线有效，数据线选择信号由路由和仲裁单元给出。 路由和仲裁单元。路由和仲裁单元实现了路由算法，为输入消息选择输出链路和 相应的位置开关。如果多个消息同时请求同一输出链路，该部件则对它们进行仲 8 南京邮电大学硕上研究生学位论文第二章片- 网络相关概念 裁。如果请求的链路正忙，则将输入消息先保存在输入缓冲器，当链路释放，并 且输入消息经过仲裁成功获得链路后，才能重新路由，所以说其中路由单元用于 决定将输入通道的信息发送至某一输出通道，而仲裁单元用于决定当多个输入信 息竞争同一输出通道时的优先级。 链路控制器。其作用是实现相邻路由器之间物理通道上的流量控制，并协调报文 的传输，处理通道阻塞等问题。 图2 3 通用交换开关结构框图 每个交换节点使用通道或者说是链路和相邻的交换节点直接相连，交换节点中内置队 列来处理拥塞。交换节点采用路由和分组交换技术，将信息从其输入通道传输到其中一个 或多个输出通道，实现资源节点之间的数据通信。在传输数据的过程中，交换节点需要完 成路由功能以及多路竞争一个通道时的仲裁功能。交换节点按照一定的拓扑结构互连，构 成片上网络的物理框架。 每个资源节点都有一个唯一的地址，资源节点与交换节点、交换节点与交换节点之间 都利用通道互连成一个微型网络，并在通道中发送消息实现通信。这样，任何资源只要配 置与芯片上槽兼容的接口并且具有网络接口，就能够连入网络。 片上网络中资源节点和交换节点之间的通信可以通过消息传递( m e s s a g ep a s s i n g ) 和 共享内存( m e m o r ys h a r i n g ) 两种方式来实现。在消息传递方式中，节点之间传输数据需 要显式调用a p i s ，例如s e n d o 和r e e e i v e o 。这些a p i 命令的实现，需要相应的协议来支持， 因此产生了额外的传输消耗，可能降低系统效率：相比较而言，共享内存方式只需要对存 储器进行存取操作，不需要额外的传输消耗，因此，共享内存的通信方式被广泛应用于如 今的高性能多处理器系统中。一个典型的n o c 结构如图2 - 4 所示【1 7 1 。它通过个片上互联 9 南京邮电人学硕 j 研究生学位论文 第二章片f ：网络相关概念 网络来连接多个资源节点，每个节点有其独立的c p u 和缓存结构，当从一级缓存l l 中没 有读取到数据时，会进入二级缓存l 2 ，如果二级缓存中也没有所需数据，则会进行存储器 的读操作，从存储器中读取数据，当l l 和l 2 进行数据更新时，两者都可以采取写通或写 回的方式。 图2 - 4n o c 节点结构 每个节点之间通过共享内存相互联系，在物理上所有节点统一编址，并通过存储器目 录可对存储器进行访问。当从l 2 不能读取到所需数据时，l 2 通过片上网络发送请求以表 明要进行存储器读操作，当存储所需数据的存储器接受到请求后，将发送应答给请求节点， 应答中包含所请求的数据。当进行缓存的写通或写回操作时，需要更新的缓存内容将被封 装在一个数据包内，发送到相应的存储器所在的位置，完成更新。 在使用共享内存方式的n o c 中，保持缓存一致性是一个关键问题，因为一个数据可能 有多份拷贝在不同的节点缓存中，当存储器中的数据更新时，相应节点中的这些陈旧数据 都需要被更新，通常有两种方法解决这种一致性问题：1 ) 缓存更新法即当存储器内的数 据更新时，更新所有在缓存中的相应拷贝；2 ) 缓存无效法将缓存中相应的数据标记为无 效，当下一次读取这些数据时，将会产生一个读取存储器的请求，从而会从存储器中取到 更新后的数据。 2 2 片上网络的拓扑结构 n o c 的拓扑结构就是指n o c 中各个节点的连接方式，网络是否能够有效地散布信息在 很大程度上依赖于网络的拓扑结构。通常说来，在理论上很难有办法来针对给定的应用来 对拓扑结构进行优化。虽然通过体系结构的定制可以提高性能，降低功耗和减少面积，但 难以对规则网格结构进行修改的问题，使得需要开发能够对高层事务和在微米或纳米级实 1 0 南京邮 乜人学硕i 研究生学位论文 第二章片一 ：刚络相关概念 现的具体限制之间进行有效折中的拓扑结构。 由于不同的性能需求和成本要求，很多n o c 网络拓扑结构是为特别应用量身定做的。 n o c 中的节点分为资源节点和交换节点，资源节点负责对数据的处理，交换节点负责对数 据流的仲裁和路由转发，交换节点既可以被集成在资源节点内部，也可以在外部实现，可 以根据不同需求进行不同的物理实现。有关拓扑结构的内容将在第三章中详细介绍。 2 3 基于通讯的n o c 设计 基于通讯的n o c 设计方法的目的是为了使得n o c 工作得更加有序，减少网络通讯的 拥堵现象，保证网络通讯的畅通，从根本上提高n o c 执行任务的效率。 2 3 1n o c 设计方法 n o c 设计最终的目的就是希望把更多的微处理器集成到芯片设计中。在n o c 设计中主 要采用基于b p s ( b a c k b o n e p l a t f o r m s y s t e m ) 的方法【1 8 1 。所 胃b p s 方法就是把n o c 系统的开 发过程分成了三个阶段，分别是通信框架设计( b a c k b o n e ) 、系统硬件平台设计( p l a t f o r m ) 和应用系统开发设计( s y s t e m ) 。 ( 1 ) 通信框架设计( b a c k b o n e ) 在通信框架设计中，主要任务是根据系统的具体需要选定n o c 的拓扑结构和通信机制。 其中通信机制包括通信协议、信道、路由开关、网络接口等。在定义好通信协议后，设计 主要集中在开关和接口的逻辑和物理设计上。线的数量、长短及开关中缓冲器大小等的物 理设计都会直接影响系统性能。 ( 2 ) 硬件平台设计( p l a t f o r m ) 硬件平台设计是一个用于应用领域的计算平台。它在可扩展的网络中定义域、资源节 点和系统控制。由于该系统不是一个完全专用的系统，所以在设计时要考虑具体任务的映 射过程，通过某些工具的仿真验证最终得出资源的选择以及资源在网络中具体的相对位 置。 ( 3 ) 系统设计( s y s t e m ) 系统设计过程也就是把具体的应用映射到n o c 资源的过程。n o c 的设计方法支持任务 的动态和静态映射，但是都将面临资源的分配、优化以及系统性能的验证与纠正等问题。 系统设计过程和分布式并行系统的设计很相似。 南京邮电人学硕l j 研究生学位论文第二章片上网络相关概念 2 3 2n o c 设计流程 n o c 的设计思想：在n o c 之外，增加一个处理单元作为通讯中枢，主要执行处理单 元映射( 包括了静态通讯分配) 和动态通讯的即时处理等功能。根据不同的系统约束条件， 该处理单元既能以软件形式实现，也能以硬件形式实现，或者是软硬件协同实现【1 9 1 。 根据应用来设计一个n o c 需要执行下面的步骤。如图2 5 所示： 图2 - 5 基于通讯的n o c 设计流程 1 ) 将应用说明转换为通讯任务图，通讯任务图是用任务与任务之间的关系表示应用的一 种拓扑图，顶点是计算任务，各项点间的有向弧表示任务之间的数据通信； 2 ) 根据现有的i p 库和任务的属性，进行任务分配和调度，将通讯任务图中的每个任务分 配到相应的处理单元，得到应用特征图； 3 ) 根据应用特征图中各任务的执行次序和它们之间的通讯任务的约束要求和执行次序， 将处理单元分配到不同的可利用的资源节点，得到n o c 体系结构说明；同时确定了应 用特征图中所有静态通讯的路径，得到网络通讯服务表( 包含了执行整个应用特征图 南京邮电大学硕l j 研究生学位论义第二章片一卜列络相关概念 期间的静态通讯路由信息) ，并将所有数据和路由信息传送给通讯中枢。通常的可行的 方法就是先执行步骤2 ，根据要求得到一个最优解，然后执行步骤3 ，得到最终的设计。 当然，这种方法存在着一定的问题：两个局部最优解并不能保证得到全局最优解。但 是如果想同时执行步骤2 和3 得到一个全局最优解的话，将对映射算法提出了更高的 要求，尤其是映射算法的执行时间： 4 ) 根据n o c 体系结构说明设计n o c 。 2 3 3 实现n o c 的关键技术 n o c 设计方法的目的是为了使得n o c 工作得更加有序，减少网络通信的拥堵现象， 保证网络的畅通，从根本上提高n o c 执行任务的效率，同时也满足n o c 在功耗、效率等 方面的要求，而且在保证任务执行的高效率的同时降低n o c 的功耗。如何设计出高效的 n o c ，有如下几方面的关键技术【2 0 】： ( 1 ) 通信协议与拓扑结构 n o c 通信协议的抽象层次划分和n o c 通信协议栈模型是开展n o c 通信研究的起点。其 中的关键技术包括n o c 通信协议的物理层同步技术、网络层路由技术以及网络接口协议等； 结合集成电路设计的特点，研究计算机网络中现有拓扑结构向n o c 移植的可行性，开发新 的拓扑结构，以及同构结构、异构结构的特性模型，都是十分关键的技术。 ( 2 ) n o c 系统集成与验证技术 在n o c 系统集成与验证中主要包括系统级软硬件划分技术、应用特征提取及应用特征 图映射、重用技术、以及n o c 性能评估技术。系统级软硬件划分是在n o c 软件、通信基础 架构的基础上，研究n o c 软硬件协同设计与验证方法，建寺_ n o c 系统级软硬件模型；n o c 重用技术主要指系统级重用，且p s o c 的重用；性能评估研究设计、验证的效率与性能在设 计流程各个层次的评估方法。 ( 3 ) n o c 基础元件库设计技术 n o c 基础元件库相当于s o c 时代的i p 库，库元件既包括s o c 、i p 等传统元件，也包括链 接通道( 1 i n k ) 、接口、路由器、电开关等n o c 时代的特有元件。为了使n o c 的任一组合特性 和线性工作量特性接近理想状态，从而提高设计效率，n o c 基础元件库设计技术是另一个 关键部位之所在。例如，遵循“积木化”原则的内在规律，将积木单元拓展n s o c 平台时， n o c 基础元件库的设计技术、资源节点与片上互连结构接e l i p 技术( r e s o u r c en e t w o r k i n t e r f a c e ，r n i ) ，以及片上互连结构中的基本通讯i p 设计技术等，都是必须受到高度关注 南京邮l u 人学硕i j ”究生学位论义第二章”1 ：刚络相关概念 的核心部位。 ( 4 ) 操作系统关键技术 计算机网络的主流结构是一台服务器管理着若干台p c 机。如果把这种结构移植到芯片 上，n o c 中的s o c 节点将分为主控节点和从属节点，每个节点都有本地操作系统。主控o s 和从属o s 需要执行不同层次的调度、同步、分配、互锁等任务。网络操作系统将成为n o c 关键技术之一。典型的操作系统问题有h a l ( h a r dw a r ea b s t r a c t i o nl e v e l ) 中的数据类型、 引导代码、环境变量及环境变量切换函数库、处理器模式切换以及底层驱动程序及应用接 口等。 2 3 4n o c 设计考虑因素 在片上网络的设计过程中，虽然已经有了系统的设计过程与步骤，但是真正实际的设 计过程中，仍然需要考虑很多相关因素，这些因素主要包括以下几种： 1 ) 功耗：片上网络中大部分能量被内部互连网络消耗。在片上网络系统的设计过程 中，功耗的大小需要被作为主要考虑因素。 2 ) 面积：如果超出芯片容量的大小承受范围，即使再优秀的片上网络的设计方案也 是无法物理实现没有使用价值的。面积是芯片设计的重要考虑因素之一。集成电路设计面 积的大小和多方面的因素是相关的，如i p 功能块的面积，预计片上系统设计规模以及布线 的实施等。 3 ) 定制：面向不同功能和用途的需求，对片上网络系统的设计和要求也是不同的。 根据具体应用来定制也是片上网络的特点之一。而且片上网络技术中被定制的层次可以分 为系统结构、协议、服务质量以及硬件软件流等【2 1 1 。 4 ) 耐故障：处理单元和通信链路容易发生故障。理想的片上网络设计可以为存在节 点或者链接故障的系统提供可靠的保护。 2 4n o c 通信协议 通信协议是信息从源节点传输到目的节点遵循的一定规则或者是方法，通常分为多个 层次。在计算机网络中，使用7 层o s i 协议模型作为开发不同应用领域通信协议栈时的参 考。由于n o c 应用对资源开销和系统功耗都有严格的要求，同时要充分考虑到通信协议与 资源节点的接口，所以片上网络的通信协议，需要根据通信需求对o s i 七层参考模型进行 裁减与优化，以降低协议处理带来的额外开销【2 2 1 。片上网络的协议模型将协议栈划分为三 1 4 南京邮一乜人学硕一i 研究生学位论文第二章片上网络相关概念 个层次f 2 3j ：软件层、体系结构控制层以及物理层。软件层包括系统及应用等软件，体系结 构控制层包括传输层、网络层和数据链路层等协议，而最底层则是与物理连线等相关的协 议。每层的协议功能如图2 - 6 所示。 软件层应用层 系统层 体系结构控制层 传输层 网络层 数据链路层 物理层 物理连线 图2 - 6n o c 通讯协议栈示意图 应用层：片上互连网络的应用层用于处理应用程序的通信、数据传输、消息传输和同 步机制。应用层与外界资源节点的接口包括软件线程、任务、数据传输协议和同步策略， 主要研究有关应用程序的并行表达映射，通信建模。应用层的设计要考虑网络应用需求， 针对不同应用进行设计。 链路网络层：该层对数据包进一步划分为多个流控单元，便于实现链路上的流量控制。 链路网络层用于处理与应用程序无关的消息封装传输，它包括通信数据包和微片控制协 议、网络拓扑结构、路由算法、交换策略、流量控制、聚合通信协议等。链路网络层与外 界的接口主要是网络通信控制协议。本层要通过模拟、仿真进行互连网络拓扑结构、网络 层通信协议、流控方式的性能评价，使其满足系统设计目标。 物理层：片上互连网络的物理层完成底层微片的传输。片上互连网络通常使用全局异 步局部同步传输方式，物理层要处理多时钟域问题。多时钟域包括资源节点时钟、存储单 元时钟等。物理层与外界的接口为数据传输的时钟、控制、数据信号等。物理层各部件与 工艺相关，当工艺改变时需要修改或重新设计各个功能部件。 片上网络通信协议规范资源节点在网络上的数据传输，确保数据能正确、有序地从源 节点传输到目的节点。通信协议需要考虑的问题主要包括【2 4 j ： 1 ) 交换方式，它包括电路交换、包交换、虚跨步交换、虫洞交换等； 2 ) 路由算法，它包括固定路由算法和自适应路由算法； 3 ) 控制策略，它包括集中控制策略和分布式控制策略； 4 ) 链路连接特性，它可以是基于连接的或是无连接的： 南京邮电人学硕i ： i j f 究生学位论文 第二章片上网络相关概念 5 ) 延时处理策略，它可以是使用不丢包的策略或是使用可丢包的策略。这些内容将 在第四章中将详细描述。 2 5 本章小结 本章首先介绍 n o c 的节点结构，其中介绍了资源节点和交换节点以及两者之间的网 络接口，说明了每个节点的构成及其作用；然后简单的介绍了n o c 拓扑结构；阐述t n o c 的设计流程、设计方法、实现n o c 的关键技术及设计过程中需要考虑的因素：最后说明了 n o c 的通信协议，借鉴了计算机网络的协议栈模型讲述t n o c 协议栈。 1 6 南京邮电人学硕上研究生学位论义第三章片l 网络拓扑结构 第三章片上网络拓扑结构 在片上网络中，拓扑结构、路由算法和交换策略是影响互连网络性能的重要因素，这 三方面的因素是紧密联系的。其中拓扑结构是各处理单元间的通信的物理制约，它决定了 交换节点和交换节点，以及交换节点和存储器或者外设之间的数据通路，主要体现片上互 连网络中的交换节点是如何分布和连接的，节点与链路的布局和互连方式，它制约着整个