（计算机软件与理论专业论文）noc映射方法和路径分配研究.pdfVIP

上海大学硕士学位论文 摘要 片上系统s o c ( s y s t e mo nc h i p ) 的出现使得整个系统在一个芯片上实现成为 可能。总线由于可以提供高性能的互连而被广泛运用在s o c 中。但是随着半导 体技术的持续发展，出现了一些与总线相关的问题，如吞吐量受限，全局时钟 难以同步，系统扩展性受限等。为了克服总线结构的不足，一些研究组织提出 将片上互连网络结构应用于s o c 设计，借鉴并行计算机互连网络的思想来实现 大量核的互连，称为n o c ( n e t w o r ko i lc h i p ) 。 对于n o c 设计而言，映射和路径分配是至关重要的两个环节，映射决定每 个处理单元在n o c 的位置；路径分配则确定两个资源节点间的通讯路径。映射 方法和路径分配的实现对节省n o c 系统功耗和通讯延时有着非常重要的意义。 n o c 映射是一个n p 问题，在规模较大的n o c 中几乎不可能求得其最优解， 主要的解决办法是通过启发式算法求得较优解，本文基于2 d m e s h 拓扑结构的 n o c 平台，建立了以通讯功耗优先的映射目标函数，并且采用粒子群优化算法 ( p s o ) 来解决n o c 映射问题，同时通过精英重组算子来克服p s o 算法早熟的 缺点。实验结果表明，粒子群优化算法( p s o ) 很好的完成了n o c 映射任务， 相比于随机映射，在通讯功耗上节省了1 0 - - 6 5 ，并且在n o c 规模越大的情 况下，功耗节省的越显著。 本文提出了一种改进的a 木路径搜索算法来完成n o c 路径分配任务。本算 法是根据2 dm e s h 拓扑结构的特点设计估价函数，使得在路径搜索过程中得到 有用的启发信息，以提高路径搜索效率。又采用多次搜索法对算法进行改进， 能够保证搜索到最优路径。模拟实验表明，本算法很好地实现了n o c 路由的路 径分配，同时，算法实现的效率要明显优于d i j k s t r a 最短路径算法。 关键词：片上网络，映射，路径分配，粒子群，启发式，功耗 v a b s t r a c t i tb e c o m e st r u et ob u i l daw h o l es y s t e mo nac h i pw i t ht h ee m e r g e n c eo fs o c c a i l e ds y s t e mo nc h i p t h eb u sa r c h i t e c t u r eh a sb e e nw i d e l yu s e db e c a u s ei t c a n p r o v i d eh i g h p e r f o r m a n c ei n t e r c o n n e c t h o w e v e r , w i t ht h ec o n t i n u e dd e v e l o p m e n t o fs e m i c o n d u c t o rt e c h n o l o g y , t h e r ec o m es o m ep r o b l e m sa b o u tb u s 。r e l a t e d t h e p r o b l e m si n c l u d el i m i t e dt h r o u g h p u t ，s y n c h r o n i z a t i o n a n ds y s t e ms c a l a b i l i t y i n o r d e rt os o l v et h e s ep r o b l e m s ，s e v e r a lr e s e a r c hg r o u p sp r o p o s ean e wa r c h i t e c t u r e c a l l e do n c h i pi n t e r c o n n e c t i o nn e t w o r k s ( o c l n ) ，w h i c hi sa l s oc a l l e dn e t w o r ko n c h i p ( n o c ) m a p p i n ga n dp a t hr o u t i n ga r et w o c r i t i c a la s p e c t sf o rt h en o cd e s i g n m a p p i n g c o n f i r m st h el o c a t i o no fe a c hp r o c e s s i n gu n i t ，a n dp a t hr o u t i n gd e t e r m i n e s t h e c o m m u n i c a t i o np a t hb e t w e e nt w on o d e s w h i c ha r ei m p o r t a n tt os a v et h en o c s y s t e mp o w e r a n dt h ec o m m u n i c a t i o nd e l a y t h en o c m a p p i n gp r o b l e mi sa n pp r o b l e m ，a n dw h e nt h es i z eo fn o ci sl a r g e ， i ti si m p o s s i b l et og e tt h eo p t i m a ls o l u t i o n u s u a l l y , w eu s et h eh e u r i s t i ca l g o r i t h mt o g e tt h ea p p r o x i m a t eo p t i m a ls o l u t i o n b a s e do n2 d m e s ht o p o l o g yo f n o c p l a t f o r m ， ap o w e rp r i o r i t ym a p p i n go b j e c tf u n c t i o ni ss e tu pa n dt h ep s o ( p a r t i c l es w a r m o p t i m i z a t i o n ) a l g o r i t h mi sp r o p o s e di nt h i sd i s s e r t a t i o n i n o r d e rt oi n c r e a s et h e d i v e r s i t yo fp a r t i c l e sa n dr e s o l v et h ep r e c o c i o u sp r o b l e m t h em e t h o do fr e c o m b i n i n g t h ee l i t ep a r t i c l e si sa d o p t e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h ep s oa l g o r i t h m c o m p l e t e st h et a s ko fn o cm a p p i n gv e r yw e l l ，c o m p a r e d t or a n d o mm a p p i n g ，s a v i n g p o w e rc o n s u m p t i o nb y1 0 6 5 w h i l et h ep s oa l g o r i t h mi s m o r es u i t a b l ef o r n o cw i t hl a r g es i z e t h i sp a p e rs u g g e s t sa ni m p r o v e da 木p a t hs e a r c h i n ga l g o r i t h mt oc o m p l e t et h e t a s ko fp a t hd i s t r i b u t i o no fn o cr o u t i n g a c c o r d i n gt o t h e2 d m e s ht o p o l o g y c h a r a c t e r i s t i c s ，t h i sa l g o r i t h md e s i g n st h ev a l u a t i o nf u n c t i o n t o g e tt h eu s e f u l h e u r i s t i ci n f o r m a t i o na n di m p r o v et h ee f f i c i e n c yo fp a t hs e a r c h i n g , a n df i n dt h e o p t i m a lp a t ht h r o u g ht h em u l t i p l es e a r c h i n g t h ee x p e r i m e n t a lr e s u l t ss h o w t h a t , t h e v i 上海大学硕士学位论文 e f f i c i e n c yo fs e a r c h i n gp a t hh a sb e e nn o t i c e a b l yi m p r o v e dr e l a t e dt ot h ec l a s s i c s h o r t e s tp a t ha l g o r i t h md i j k s t r a k e y w o r d s ：n o c ，m a p p i n g ，p a t hr o u t i n g ，p s o ，h e u r i s t i c ，p o w e rc o n s u m p t i o n v i i 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发 表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即： 学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学 校可以公布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：堡巡导师签名：姐日期：乏蛆 上海大学硕士学位论文 第一章前言 随着半导体技术的不断发展，微处理器性能不断得到提升，未来的片上系 统( s o c ) 能在单个芯片上集成数十个，甚至数百个处理单元( p r o c e s s i n gu n i t ) 、存 储单元( s t o r a g eu n i o 。为了满足现今电子产品越来越复杂的功能需求，多核s o c 的出现就成为必然。多核s o c ( m p s o c ) 设计的一个非常核心问题就是片上组件 间的通信，片上通信设计地是否优良直接关系到芯片内各处理核性能的发挥。 传统s o c 一般采用时分多路总线作为核间的通信方式，如：i b m 公司的 c o r e c o r m e c t 【l 】，a r m 公司的a m b a ( a d v a n c e d m i c r o c o n t r o u e rb u s a r c h i t e c t u r e ) 2 】和s i l i c o r ec o r p 公司的w i s h b o n e 3 1 。然而随着工艺技术的持续发 展，片上总线所带来的问题暴露了出来，主要表现为以下两方面：一、可扩展 性比较差，当片上处理核增多时，总线上的通信就会出现拥塞；二、单一时钟 的同步问题，由单一系统时钟同步全芯片的工作将极其困难。在这背景下，提 出了新一代的互连结构- n o c 。n o c 是借鉴计算机网络的设计思想 4 】，即将 每个口模块看作微型网络的一个组件，设计一种微型网络层次结构来实现各个 p 模块间的互连。 1 1 课题研究的背景 1 1 1 国外研究现状 国外的研究机构从系统结构、通信路由策略、物理布线的时钟策略、可测 试性分析等多方面对n o c 进行了系统研究，并取得了一定成果。其中影响较大 的有瑞典皇家理工学院( k t h ) 和l i n k u p i n g s 大学、以及美国的麻省理工学院和 斯坦福大学等。 瑞典皇家理工学院( k t h ) 研发的n o s t r u m 网络结构使用了主干链路的概念， 它主要研究从物理层到应用层的通信问题，n o s t r u m 是通过将每个路由节点连 接到另外四个路由节点而形成一个规则的2 d m e s h 拓扑结构，一个口核连接 到一个路由节点。交换网络采用了同频不同相的伪同步时钟，每个p 核使用不 上海大学硕士学位论文 同甚至仕葸阴町钾买士见。n o s t n t m 网殆采用了自适应反射路由策略和很小的缓 冲避免了拥塞并具有自适应容错能力，采用保留通信资源来提供保证延迟的流 量并提供尽最大努力流量。该研究组正在研究n o c 的协议、映射技术、时钟策 略。他们研究网络处理器和多媒体应用的n o c 平台。用n o s t r u m 仿真环境n n s e 来配置n o s t r u m 网络的节点数量、拓扑结构、路由策略、流量模式等进行仿真， 仿真结果可以采用不同的图形方式显示【6 。丌。 瑞典l i n k 6 p i n g s 大学研发的s o c b u s 是一个用于硬实时系统的片内通信网 络。典型的应用是无线通信的基带处理和通信基础设施。s o c b u s 采用包连接 的电路( p a c k e tc o n n e c t e dc i r c u i t ) 交换方式。实际上就是利用包交换的方式，让 一个数据包寻找路由，如果成功，则保持所走过的路径，作为电路交换的路径设 置。如果不成功，则可以重发。这个交换方式的优点是没有死锁、不要缓冲器， 缺点是数据包的重发会导致延迟和不确定性。s o c b u s 采用2 d m e s h 拓扑结构， 可以根据应用来增加或删除路由器和链路来优化网络拓扑结构。用c + + 实现了 一个基于事件的高速n o c 模拟器。模拟器的输入是用x m l 表示的流量和网络 模型。他们正在研究用f p g a 实现s o c b u s 引。 意大利b o l o g n a 大学和美国s t a n f o r d 大学联合研发的x p i p e s 是一个可综合 的、高性能的n o c ，通过对路由节点、通信链路和网络接口的配置可以得到任 意的拓扑结构，采用了蠕动交换技术和确定性源路由的静态路由算法。网络接 口采用o c p 2 o ( o p e nc o r ep r o t o c o l2 o ) 协议，支持网络和口核不同的时钟。链 路可以分级产生流水线。s u n m a p 工具是根据应用需求自动选择最佳拓扑结 构，并根据约束条件和口核之间的流量模型映射核到选定的拓扑结构并选 路由策略，进行配置x p i p e s c o m p i l e r 工具。x p i p e s c o m p i l e r 工具自动根据元件 库中的元件和输入的拓扑结构、路由策略等实现一个定制的n o c ，输出一个 s y s t e m c 的n o c 设计。他们对m e s h 结构的m p e g 4 解码器和定制结构的m p e g 4 解码器面积和功耗进行了分析比较【9 】。麻省理工学院的r a w 处理器，属于一种 基本的n o c 。r a w 用全双工的连接实现可编程路由器和计算资源之间的通信。 r a w 的主要应用是作为一个超级计算机进行多媒体处理【5 1 。 下表列举了在国际上有影响力的几个n o c 实例。 2 上海大学硕士学位论文 表1 - 1国外n o c 实例介绍 c e l l 1 0 - 1 1 1r a w i t 2 】s p i n e l 3 】 研发机构m m美国麻省理工大学巴黎第六大学 网络规模一个p p e ，8 个s p e s 1 63 2 拓扑结构双向环状网络e m 4 x 4 m e s h 4 列胖树 制作工艺( u m ) 0 0 90 1 50 1 3 工作频率( m n z ) 1 6 0 02 2 52 0 0 网络带宽( b i t s ) 3 0 2 7 2 3 5 1 2 5 面积( m m 2 ) 1 4 83 3 1 2 44 6 表中各种n o c 都有各自的拓扑结构、路由方式、网络规模、物理设计等， 适用于不同的系统，现今的研究成果【悼1 q 对n o c 的进步发展起到了很好的推动 作用。 1 1 2 国内研究现状 国内对n o c 的研究相对来说起步较晚，主要侧重于理论研究，并没有实际 的产品，与国外相比存在较大的差距。当前国内对n o c 所做的研究主要有如下 几个方面： 首先，合肥工业大学所做的研究 1 7 - 1 9 1 解决了长期困扰总线结构的难题：全 局时钟问题。时钟延迟越来越影响着全局同步的准确性，并且时钟树大量消耗 面积资源和功率资源，i t r s 数据表明，5 0 r i m 节点的时钟树将消耗三分之一的 功率。因此解决好了全局时钟问题，将在很大程度上节省节点上的功耗。 其次，哈尔滨工业大学【2 0 s o c 研究中心对n o c 低功耗自适应数据保护机制 做了深入的研究，根据不同n o c 通信链路错误数目自适应选择，达到系统芯片 功耗最优化。该机制的流程是数据从源节点到目标节点的传输过程中，采用端 到端数据保护机制，同时检测通信链路上发生的错误当超过给定的范围时，就 对该点进行纠错，否则不用纠错。 还有西北工业大学有关n o c 模块化测试的研究，提出了基于n o c 的模块 化测试方法【2 1 1 。结合可扩展的片上互联网络和同事多线程结构，提出网络互连 3 上海大学硕士学位论文 多线程处理器。而在并行d s p 处理器方面，利用n o c 功耗模型和时延模型分 析了二维和多维的m e s h 网络结构中功耗时延的差别。 近年来，我国越来越重视n o c 的研究，投入了大量的资金在各大院校和 研究机构开展研究，并且取得了一定的成果。从国内发表的论文来看，2 0 0 6 年 前有关n o c 的论文是2 4 篇，而到了2 0 0 8 年猛增至1 4 2 篇，可见近两年来，针 对n o c 的研究已经成为片上系统的一大热点。 从以上国内外研究现状可知，当前国内研究机构基本上是对n o c 功耗、 设计方法【2 2 2 钔、全局时钟、通信可靠性、路由算法c 2 5 】、通信算法和协议【冽以及 模块化测试方法等方面做了深入的研究。而国外研究机构主要侧重于系统结构、 通信路由策略、物理布线的时钟策略、可测试性分析等多方面的研究。由上概 括可知，当前国内外各研究机构对n o c 体系结构的设计流程尚未做深入研究， 而n o c 的实现离不开其设计流程，本文主要针对n o c 的映射( m a p p i n g ) 和路径 分配( r o u t i n gp a t ha l l o c a t i o n ) 这两个n o c 设计流程中必不可少的环节进行研究。 1 2 本文研究的意义 随着制作工艺的进步和s o c 技术不断完善，现今的s o c 可以集成一个或 多个处理器、存储器、以及片上可编程逻辑等知识产权核6 pc o r e ，i n t e l l e c t u a l p r o p e r t yc o r e ) 。但是，随着s o c 集成度越来越高的情况下，传统的以总线结构 为通信基础的s o c 技术面临着在性能、功耗、延时和可靠性等诸多方面的难题。 主要问题如下： ( 1 ) 带宽限制。总线是一种共享介质的互连结构，某一时刻只允许一个设备 使用总线，仲裁逻辑允许高优先级的设备获得总线的使用权。在总线被占用期 间，其他所有请求被阻塞，直到总线空闲。当很多部件争用一条总线时，会造 成严重阻塞，并会降低总线频率等。 ( 2 ) 信号集成度。更低的电源电压及更小的特征线宽使得整个s o c 系统对 电流中的噪声更加敏感，而共享介质上的功能部件则进一步加重了噪声。 ( 3 ) 信号延迟。随着集成特征尺寸的下降，连线延迟成为影响信号延迟的主 要因素。总线结构是全局控制的，在1 0 亿晶体管时代，全局连线延迟大于时钟 4 上海大学硕士学位论文 周期，因此，总线结构的全局连线使得时钟的偏移很难管理。 ( 4 ) 全局同步。全局连线上的信号延迟决定了系统的时钟周期，为了保持甚 至提高系统时钟频率，只能对全局连线进行分布式流水线模式，或采用全局异 步局部同步( g a l s ) 的时钟模式。 n o c 作为s o c 发展的趋势，能很好解决基于总线所面临的难题。n o c 以 其支持同时访问、可靠性高、可重用性高等特点成为更理想的大规模片上多核 系统互连技术。n o c 克服了总线结构可扩展性差的缺点，为1 0 亿晶体管时代 提供了一种可行的片上系统通信机制。它除了可以连接更多的口组件，与总线 结构相比，还有高可重用性等特点。对于n o c 设计而言，除了任务分配和任务 调度之外，还需要增加两个步骤：映射和路径分配。映射决定每个处理单元在 n o c 的位置；路径分配则确定两个资源节点间的通讯路径。映射方法和路径分 配的实现对节省n o c 系统功耗和通讯延时有着非常重要的意义。 1 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 映射。 第四章设计和实现了n o c 路径分配。分析了n o c 路径分配问题的原型， 对通讯模型进行了深入的探讨。提出了改进的a 宰路径搜索算法很好的完成了 n o c 路径分配任务。 第五章测试和实验结果分析。 第六章总结与展望。 上海大学硕士学位论文 第二章n o c 系统综述 2 1n o c 基础知识 2 1 1n o c 通讯方式和体系结构 ( 1 ) n o c 通讯方式 在n o c 系统中，数据包( p a c k e t ) 是处理节点问相互通信的基本单位f 2 7 1 ，其 大小根据需求来设置，可以设为几个字节，也可设定为一块内存区域所包含的 信息。n o c 通信时，一个时钟周期内所交换的信息单元称为数据分片( f l i t ) ，由 于其操作的原子性，就定义了网络中两个处理节点之间的最大带宽。通常，一 个数据包由多个数据分片组成，当进行一个完整的信息交换时，从处理器层来 看，是简单的传送接受一个数据包，从原子操作角度看，网络节点间进行了多 次的数据分片交换。 n o c 是由许多组件构成，除了处理节点和存储节点，还有转发器( s w i t c h ) ， 其主要目的是对交换的数据分片进行处理，包括了缓存区、控制逻辑以及路由 器( r o u t e r ) ，路由器连接到转发器的入口和出口，对从源节点传来的数据进行路 由选择，通过合适的转发器发送到目的节点。衡量一个n o c 系统的性能，通常 有两个标准，数据分片处理时延( f l i tl a t e n c y ) 和数据包处理时延( p a c k e tl a t e n c y ) 。 数据分片处理时延是一个数据分片从源节点到目的节点所花费的时间，可以通 过计算跳数( 从一个s w i t c h 转发到另一个s w i t c h 称为一跳) 和所用的时钟周期数 进行衡量；数据包处理时延是目的节点接收一个完整的数据包所花费的时间， 即从开始接收第一个数据分片到接收完最后一个数据分片所用的时钟周期数。 ( 2 ) n o c 体系结构 n o c 系统主要是由两个部分组成：处理单元( p r o c e s s i n ge l e m e n t ) 和负责 p e 之间信息交换的通讯节点 2 s - 3 0 】，如图2 1 所示。一般处理单元可以是处理器、 可复用器件、存储器、i o 设备等。通讯节点负责资源节点之间的信息交换，如 路由器。图2 2 中给出了一个单个路由的基本结构【3 l 】。 6 上海大学硕士学位论文 图2 1p e 与路由布局图图2 2 路由结构图 通讯节点是互连网络中的主要部分，其核心就是交换开关。如网络中的路 由器，其主要作用是寻找出信息从起点到终点的最短最有效的路径。在数据传 输中，有两种路由方式可供设计者选择：确定性路由( d e t e r m i n i s t i cr o u t i n g ) 和 自适应路由( a d a p t i v er o u t i n g ) 。但是对于n o c 设计，自适应路由规则并不适合。 这并不是考虑自适应路由中路由表的存在，而是由在计算升级和维持信息的复 杂度决定的。在n o c 中，路由器是其核心部件。因为减少了网络缓存数量，数 据包的延时与源和目的端之间的距离无关，虫洞路f l j ( w o r m h o l er o u t i n g ) 广泛用 于n o c 通信。数据包被分解成流量控制单位( f l i t ) ，然后，流量控制以一个一个 的f l i t 为单位运行。 n o c 中允许存在任意类型的资源节点，典型的资源节点可以是带缓存的嵌 入式微处理器和d s p 核、专用硬件资源、可重构硬件资源，或者是上述各种硬 件的组合。计算类的资源节点以微处理器核、d s p 核等形式存在，而存储类的 资源节点则要求尽可能的分散，以避免访问数据时要跨越整个芯片。各种尺寸 的s r a m s 、d r a m s 、f l a s h 满足了不同的需求。 2 1 2n o c 拓扑结构和路由方式 ( 1 ) n o c 拓扑结构 n o c 的拓扑结构很大程度上是借鉴了并行计算机互联网络的结构【3 2 1 ，主要 分为规则拓扑和非规则拓扑两大类。 规则的拓扑具有规则的网络参数，具有可复用性，降低了设计时间和成本， 7 上海大学硕士学位论文 适用于通用的对称、同构系统。常见的规则拓扑结构有二维网格( 2 d m e s h ) 拓扑结构和二维环绕( 2 d t o r u s ) 拓扑结构【3 3 】。二维网格拓扑结构是当前研究 中最常用的拓扑结构( 如图2 3 所示) ：每一个资源节点与一个通讯节点相连， 而一个通讯节点与四个相邻的通讯节点和一个资源节点相连；通讯节点实现路 由的功能，并作为每个相邻的资源节点的网络接口，具有结构简单、可扩展性 好、便于实现和分析等优点。与二维网格相比，二维环绕拓扑结构( 如图2 4 所示) 将处于边界的通讯节点也连接起来，使所有的通讯节点成为一个环路， 从而增加了片上连线。但是环路与环路之间有交叉的地方，在物理实现时不可 避免地需要更多的布线资源。 图2 - 32 d m e s h 拓扑结构图2 _ 42 d t o m s 拓扑结构 而非规则拓扑可以面向不同的领域，根据特定的应用需求定制，不具有广 泛的应用性3 4 。6 1 。主要分为以下几类： 1 ) 专用网络。是指网络的拓扑从零开始设计，完全根据具体的应用需求生 成，没有遵循一定的规律。 2 ) 基于规则拓扑。这类网络，指在规则网络拓扑的基础上做一些改变，如在 规则拓扑的局部增加或删除一些节点或链路，从而使定制后的网络失去了规则 性。 3 ) 分层网络。在分层网络中，网络的拓扑呈现为两层或多层的层次化结构， 一般包括全局网和局部网两个层次，分别可以根据需要选用规则拓扑或非规则拓 8 上海大学硕士学位论文 扑。 4 1 网络总线混合拓扑。其实也是一种层次化结构的n o c 拓扑，全局网采用 规则或非规则的网络拓扑，而在局部网中采用总线。 ( 2 ) n o c 路由方式 n o c 路由算法基本上可分为2 种：确定性路由算法( 静态路由算法) 和自 适应路由算法( 动态路由算法) 3 7 - 4 1 】。 在确定性路由算法中，数据包的传输路径完全由包的源地址和目的地址决 定，其实现较为简单，当网络未发生拥塞时，数据包的传输时延最小，但不能 对未来的拥塞做动态调整【2 5 】。因此，当网络比较繁忙时，由于不能动态的对传 输路径进行调整，路由器易发生堵塞。 自适应路由算法即所谓动态的路由算法，为了避免网络发生拥塞，每个数 据包在传输时根据实时的网络状况动态地对路径做出调整【4 2 1 。它的实现逻辑比确 定性路由算法复杂，而且当网络只有轻度拥塞时，数据包传输的时延比较大。 2 2n o c 设计 2 2 1n o c 结构设计 n o c 是针对复杂结构系统应用的解决方案【4 3 1 。使用片上系统的环境一般具 有大量的计算子系统和存储子系统，这样大量的子系统集成在单芯片上。而对 于芯片规模不是很大的系统，采用片上系统的解决方案不具有实用价值。怎样 整合针对不同功能进行设计的子系统，优化不同子系统之间的交互协议，是片 上网络设计中需要重视的问题。片上网络因为需要进行大量的数据运算和通信， 因此需要解决对多处理器的支持、r i s c 处理器与d s p 处理器之间的协同工作 问题，因此片上网络的设计与多核设计有相似处。 按照工艺目前的发展速度推测，当进入6 5 r i m 工艺阶段，每块芯片上的传 输门数量可以达到2 4 亿，目前的a s i c 和系统设计的方法已经不能满足如此规 模和复杂程度的设计，同时s o c 设计方法也不能满足系统可扩展性的需求。从 物理实现角度分析，对于如此复杂的系统，需要划分为多个时钟域，因此需要 9 上海大学硕士学位论文 进行“全局异步一本地同步”设计( 2 9 】；从体系结构角度分析，片上网络是一个高 计算量的系统，串行计算的处理器不能满足这样的要求，指令级并行( i l p ) 可以 实现并行运算，但其复杂的控制逻辑以及从大规模的应用中进行指令划分实现 i l p 的难度成为i l p 实现并行系统的瓶颈。线程并行能够实现更为细粒度的并 行性，但是与单个处理器相比，实现相同功能需要更多额外线程，例如进行两 个计算子系统之间的通信线程。应用程序的并行性将各个嵌入式系统映射到具 体计算子系统中，实现分布式处理系统。 为了利用口复用的优势，在更为复杂的片上网络应用中，需要复用更为复 杂的系统，除了m 复用外，还需要对计算子系统处理器结构、网络互连结构、 软件平台、已有的设计芯片甚至设计方法进行复用。这就需要设计者严格定义 连接网络的接口和协议，将不同平台下的系统集成到网络中。 从设计复杂性角度来看，在设计初期，从设计设想到最后硬件实现会有很 多实现的选择，随着设计步骤的一步步实现，设计者可以选择的空间变得越来 越小。因此对于片上网络这样的复杂系统来说，需要在设计过程中做特别仔细 的考虑，对于片上网络相对s o c 更长的迭代周期( i t e r a t i o n ) 来说，应当避免这 样的冗余迭代周期。n o c 设计的指导思想包括：首先，应将系统划分到不同的子 系统中；其次，确定将系统抽象到各个抽象级别的模型中，并确定各个级别的 抽象模型的性能评估准则；第三，需要确定不同子系统结构间的交互问题，并 优化整个系统性能；第四，对各个抽象级别模型通仿真进行性能评估和相应的 调整；最后根据各个子系统相应的结构，通过相应的开发工具实现整个系统。 2 2 2n o c 通讯设计 当前，n o c 设计都是采用任务和功能分离的策略，就是资源节点只负责计 算任务，数据传输、通信等任务则交给通讯节点负责。但是现今通讯节点的功 能有限，而且研究也都局限于几个紧密相连的节点间的关系，只能实现局部的 最优化，局部的最优极有可能导致全局更差，甚至可能造成整个过程难以收敛。 s o c 中的口模块在集成到n o c 时，需针对不同的总线标准设计相应的接 口逻辑。当s o c 存在多种总线时需要进行总线接口的转换。基于标准的总线设 1 0 上海大学硕士学位论文 计方法使不同的口模块供应商能够遵守一致总线标准提供口，为系统集成节约 了设计时间。 针对以上所述，为了实现n o c 中处理器子系统以及通信系统的设计可重 用性目标，需要定义出清晰的片n o c 各层次模型、抽象级别以及整体的设计流 程 铒】。片上网络通信采用了通信协议堆栈的形式，其设计流程如图2 5 所示。 具体设计流程如下： ( 1 ) 在初始阶段，n o c 通讯设计是从系统的抽象虚拟模型出发的，通过消 息传输的机制进行数据传输仿真，该阶段没有具体的传输路径，通过全局变量 在各子系统之间进行数据通讯。 ( 2 ) 在网络层设计阶段，对各个m 模块之间的数据通讯采用点对点的数据 传输模式。网络层设计的目的是得到精确的系统链接模型，该模型中各p 模块 间通过直接链接的互连通信部件进行数据通讯，通过简单的互连模型确定各p 模块间的相互联系。 ( 3 ) 在通信链路设计阶段，相邻资源节点间的数据传输按照实际数据通讯 的媒介来实现。通信链路设计生成了系统互连的物理模型，在该模型中，各个 节点间的互连通过具体的引脚和连线实现，n o c 各协议层的传输行为在这里得 到实现，整个系统按照网络协议进行基于时钟的网络通信仿真。具体的互连可 以是寄存级描述，也可以是t l m 模型描述。根据实现参数的不同，t l m 模型 可以在数据传输质量、模型复杂程度引起的仿真速度之间进行平衡【4 5 】。图2 5 中的网络协议( n e t w o r kp r o t o c o l s ) 与媒体协议( m e d i ap r o t o c o l s ) 分别代表了网络 层上的通信协议以及具体实现通信的物理互连上的协议 4 6 1 。 上海大学硕士学位论文 图2 5n o c 通讯设计流程 该设计方法与s o c 的设计方法类似，遵循从高层到底层的实现原则。从系 统的实现方法来看，由上而下的设计方法能够从高层确定问题的方向，并对问 题进行分割，缩小问题的范围，再在底层解决问题。 2 3 本章小结 本章主要是对n o c 系统进行综述，首先介绍了本文研究所需要的一些基础 知识，分别从通讯方式和体系结构以及拓扑机构和路由方式这几个方面对n o c 系统进行了阐述。第二部分内容主要分析当前n o c 的设计方法，从结构设计和 通讯设计两个角度来分析n o c 的设计流程。 1 2 上海大学硕士学位论文 第三章n o c 映射方法研究与实现 n o c 映射是n o c 设计中必不可少的一环。针对该问题，本章在基于2 d m e s h 拓扑结构的n o c 平台上，建立了以通讯功耗优先的映射目标函数，并且提出了 带重组粒子算子的粒子群优化算法( r p o p s o ) 来实现面向功耗优先的n o c 映 射。 3 1 面向功耗优先的n o c 映射问题描述 n o c 映射的过程是将各个p 核分配至n o c 拓扑结构的过程 4 , i s 】，如图3 1 所示，将应用特征图中的口核通过映射函数映射至n o c 特征图上，有向边的 权值表示一个p 核到另一个疋核的通讯量，映射结果的好坏直接影响到n o c 系统的通讯功耗。作为片上系统，功耗肯定是极为关键的参数，因此本节先从 分析n o c 功耗模型开始展开对n o c 映射方法的研究。 3 1 1n o c 功耗模型 图3 1n o c 映射过程 网络通讯功耗是指任意资源节点间的数据通讯所产生的功耗。本文采用了 w a n ghs 等人【4 7 1 建立的体系结构级的通讯功耗模型，传输一个数据包( p a c k e t ) 的功耗用铀表示。 点j 切= 五k + 层0 + e 南+ 五毛+ 玩七 ( 3 1 ) e p a c k t = e b 盯+ e 砷+ e 曲+ e t 咄 ( 3 - 2 ) 上海大学硕士学位论文 表示将一个数据包写入输入缓冲器的功耗；砌表示从输入将缓冲中读 出一个数据包时的功耗；跏= + 鼬表示缓冲器的功耗；e r b 表示仲裁的功耗； 如表示交叉开关( c r o s s b a r ) 的功耗；e 1 j i 表示通道( 1 i n k ) 的功耗。令 如= 岛矿臣r 6 + 如表示路由节点的功耗。日表示数据包经过的通道数。数据包 ( p a c k e t ) 从路由节点n 传输到路由节点r j 的功耗： 岛= 门针矽五厶+ 日e 1 k( 3 3 ) 日个通道必定连接着册1 个路由节点，因此在公式2 3 中，路由节点上所花费 功耗的系数比互连线上的系数多一。由上式可知，n o c 的功耗主要在两个部分： 互连线功耗和资源节点功耗。 1 ) 互连线功耗 在互连线上，功耗主要有三部分组成 4 8 4 9 ，即开关功耗只w i 砌，短路电流功 耗p , h d 一。i r c u f f ，漏电功耗凡妇，表达式如下： p 纽c o l2p s w i 浊七p s h | 奠嘲t + p k h g e 0 一 互连线上总功耗公式的各个部分表达式分别如下为： p 哪i 钯h = a v 2 d d f ( c p + c o ) s + c dq 一5 、) p 渤嚏，诤蕊t i 可砌di s h 帆j t 哦硅w srl n 3q = 3 v d d 锄s 2( 3 7 ) 这里的为电源电压；厂为系统的时钟频率。厶 州。i 枷“为每单元宽度上的短路 电流；锄为每单元晶体管宽度上的泄漏电流； 根据以上各部分的功耗表达式，就可以得到每单位长度互连线上的功耗值， 为如加，z 于是对于任意两个距离为三的资源，假设互连线的数目为，则其互 连线路上的总功耗为： p = p t a t o l l n z ( 3 8 ) 2 ) 路由节点功耗 典型的路由节点包括如下一些部分：输入输出虚通道b u f f e r ，在路由阻塞 时，用于存储数据包；头部解码器，根据一定的路由算法对数据包的头部进行 解码，确定目的地址，一边数据交换；仲裁器，为输入请求窜则分配输出虚通 道；c r o s s b a r ，交换单元，将数据包路由到相应的输出虚通道：链路控制器，响 1 4 上海大学硕士学位论文 应输入链路的请求，对相应输入链路请求金像应答。 针对一个f l i t 建立其从输入端口进入路由节点，然后按照虫洞路由和维序 x y 路由算法通过路由节点，发送到输出端口的能量消耗模型。消耗能量的表 达式为： g r o u t e r = 2 e f i f o + 五珏+ 丘哪b a r ( 3 - 9 ) e f i f o 对应虚通道的能量，由于输入和输出端口均采用了虚通道队列，所以要乘 上2 倍的因子。虚通道能量的近视值如下是所示： e f i f o = 万xd e p t h a lxk l ( 3 1 0 ) 其中，n 为虚通道的数目，d e p t h 为f i f o 的深度，a ，为f i f o 中数据的活动因 子，k ，是与工艺相关的参数。是路由节点中的主要能量消耗单元。 局啦为头部解码器、仲裁器、链路控制器等逻辑控制单元的能量消耗。其 能量的近似表达式为： = c l a l + c 2 a l + k( 3 - 1 1 ) 其中，c 卜c 2 是与逻辑门有关的一些电容及电阻值，由实现工艺来决定；a ，为 开关因子；k 对应泄漏能量消耗。 易嬲姗为c r o s s b a r 交换开关中的能量消耗。其能量模型与上面的控制逻辑 部分的能量模型的建立方法类似，近似的计算公式为： e c 吣s s b a r = e l + a c + k 3 0 - 1 2 ) 其中，c j 为与电路的电容及电阻值相关的参数，a c 为c r o s s b a r 的开关因子，与 数据的活动性有关；岛与实现工艺有关的一个参数。 3 1 2n o c 映射目标函数的建立 n o c 映射就是将各i p 核按照一定的优化规则分配到n o c 平台上，实现其 应用，并且使目标成本最小化。为了便于公式描述，给出以下定义和约束条件： 定义3 1给定应用特征图a c g ( e , e ) 为有向图，图中顶点职e v , 表示一个执 行若干任务的i p 核；有向弧e ，e 表示与v j 2 _ n 的通信任务，其权重w f f 表示 与v j 之间的通信量：以数据包( p a c k e t ) 为单位计数通信量。 定义3 - 2 给定n o c 结构特征图n c g ( r , a ) 为有向图。图中顶点r i 鼎，表示 1 5 上海大学硕士学位论文 n o c 中的一个资源节点；有向弧a i j 副表示从n 到r j 的路由路径，其权重p 勺表示 资源节点n 发送一个数据包( p a c k c t ) 至j 吩的功耗。 约束条件：每个p 核只能被分配到一个资源节点上；同样每个资源节点只 能拥有一个口核。 根据以上的定义和约束条件，功耗优先的n o c 映射目标函数描述如下： 记a c g ( k , e ) 和n c g ( r , 矽的映射函数为：妒似；映射的最小通信功耗如公式 3 1 3 所示： m i n ( p e ) = w i j x p e ( 颅巧：) ； v 眯y ( 3 1 3 ) 3 2 进化计算算法分析 n o c 映射问题实际上是受约束的二次分配问题( q a p ) ，当前对于二次分配 的问题有了深入的研究，由于它是一个n p 问题，当问题的规模较大时，几乎 不可能求得最优解，目前基本上都是采用启发式方法获得近似的最优解，比如： 遗传算法，蚁群算法，以及快速蚁群算法和粒子群优化算法等，都被应用来解 决二次分配问题。 ( 1 )