（通信与信息系统专业论文）片上网络映射模型研究及工具设计.pdf

摘要 摘要 在摩尔定律的引导下，伴随着半导体产业和工艺的不断发展，集成电路上晶 体管数目不断增多的趋势给整个与集成电路相关的研究领域带来了极大的挑战和 前所未有的影响。为了在单一芯片上集成大规模晶体管，以实现复杂的电子系统， 片上系统设计技术最初于2 0 世纪9 0 年代中期被提出，逐渐成为集成电路设 计领域的一个重要的分支。同时，随着s o c 集成度的不断增加，系统越来越 复杂，深亚微米工艺带来的设计困难越加明显，一种全新的能适应片上多处 理系统并行运算能力和复杂内部连接的片上技术便慢慢成为s o c 技术的一个主 线，这就是片上网络技术。 本文从片上网络的发展、特点即其关键技术说起，然后以片上网络技术关键 问题之一的映射问题为核心展开讨论。文章首先给出片上网络的一般设计流程及 其特点，然后结合对传统n o c 映射模型和映射算法的简单介绍，提出一种简单有 效的基于实时数字信号处理系统的n o c 映射模型和相关的改进映射算法，并为该 映射优化问题建立相应的目标函数模型和约束条件模型。 在完成有关n o c 映射问题的基础理论研究之余，笔者设计了一款面向n o c 映 射问题的e d a 工具g a g u il o ，本文对该工具的优势、软件层次、简单设计方法 及其主要特性都做了详细的说明。 最后，本文使用一种常见的无线传输系统接收器作为应用系统，结合g a g u i1 0 工具，通过图表和数据的方式向读者展现了这种新的n o c 映射模型的主要优点。 同时，本文的实验部分证明了改进算法在处理复杂映射优化问题时所体现出来的 简单、高效、目标优化效果显著等诸多优点。 文中提出的新的映射模型、映射算法和映射工具，都有具体的数学模型 并被组合在一起，形成了一套通用性和可操作性极强、可配置内容丰富的研 究工具。因此，本文对n o c 映射问题的未来研究具有一定的实践性参考价值。 关键字：片上网络映射，m m m a p ，目标优化，遗传算法，映射工具 a b s t r a c t a b s t r a c t w i t ht h ea d v a n c eo fs e m i c o n d u c t o rt e c h n o l o g y , i ta l l o w si n t e g r a t e d c i r c u i t ( i c ) d e s i g n e r st oi n t e g r a t eah u g en u m b e ro ft r a n s i s t o r so n as i n g l ec h i p ，w h i c hp r o v i d e st h e a d v a n t a g e sa n dc h a l l e n g e sf o ri ci n d u s t r yi t s e l f s y s t e m o n c h i p ( s o c ) t e c h n o l o g yw a s p r o p o s e di nt h en i n e t i e so ft h e2 0 t hc e n t u r yt op r o v i d ea ne f f i c i e n tw a yt oi m p l e m e n tt h e c o m p l e x e l e c t r o n i c s y s t e m s s i n c et h ei n t e r n a lc o n n e c t i o n s a m o n go n c h i p m u l t i p r o c e s s o r sb e c a m em o r ea n dm o r ec o m p l i c a t e d ，a ne f f e c t i v em e t h o dc a l l e d n e t w o r k o n c h i pf n o c ) w a sp r e s e n t e dt os o l v et h e s ec o m p l e xo n c h i pc o m m u n i c a t i o n i s s u e s t h i st h e s i sf o c u s e so nt h em a p p i n gp r o b l e mo fn o c ，w h i c hi so n eo ft h e k e yi s s u e s f o rn o c t e c h n o l o g y a tf i r s t ，t h ed e s i g nf l o wo fn o cb a s e ds o ci si n t r o d u c e d t h e n ， b a s e do nt h et y p i c a lm a p p i n gm o d e l sa n dm a p p i n ga l g o r i t h m s ，an e ws i m p l ea n d e f f e c t i v en o c m a p p i n gm e t h o di sp r o p o s e di nt h i st h e s i s f i n a l l y , m a t h e m a t i c a lm o d e l s o fo b j e c t i v ef u n c t i o n sa n dc o n s t r a i n sa r ed e r i v e df o rt h i sm a p p i n gs c h e m e a c c o r d i n gt ot h ep r o p o s e dm a p p i n gs c h e m e ，a ne d at o o l ，c a l l e dg a g u i ，u s e df o r n o c m a p p i n gi s s u e si sa l s od e s i g n e d 。t h ea d v a n t a g e s ，f u n c t i o n a ll e v e l s ，d e s i g nf l o w a n dc h a r a c t e r is t i e sa r ei n t r o d u c e di nt h i st h e s i s i nt h ec a s es t u d y , w et a k e sam i m o o f d mr e c e i v e ro fw i r e l e s st r a n s m i s s i o n s y s t e m sa sa l le x a m p l et oe x p l a i nh o wt ou s et h ep r o p o s e ds c h e m ea n de d at o o la n d d e m o n s t r a t et h ea d v a n t a g e so ft h em a p p i n gs c h e m ea n dt h ee f f i c i e n c yo ft h et 0 0 1 t h em e t h o di n t r o d u c e di nt h i st h e s i s ，w h i c hi sc o n s i s to fam a p p i n gm o d e l ，m a p p i n g a l g o r i t h m sa n dm a p p i n gt o o l ，c o u l db eu s e df o rt h ep r a c t i c a ls y s t e md e s i g na n dn o c r e s e a r c h e s k e y w o r d s ：n o cm a p p i n g ，m m - m a p ，o b j e c t i v e o p t i m i z a t i o n ，g e n e t i ca l g o r i t h m ， m a p p i n gt 0 0 1 i i 图目录 图目录 图1 1s o c 设计流程图2 图1 2n o c 设计流程图一5 图1 3 通讯任务图与应用特征图6 图2 1n o c 设计平台11 图2 2n o c 典型映射问题示意图1 2 图2 3 片上网络网格结构1 3 图2 _ 4n o c 拓扑结构分类图1 4 图2 5 三种常用的n o c 拓扑结构1 5 图2 - 6n o c 同构处理单元平台1 6 图2 7 二维4 4m e s hn o c 结构1 7 图2 8n o c 路由节点内部结构。1 7 图2 - 9d f g 到2 x2n o c 的映射m d f g 1 9 图2 1 0 映射模型2 ) 2 0 图2 11 映射模型1 ) 和映射模型3 ) 2 1 图3 1 一个简单的映射实例2 9 图4 1 染色体编码与映射结果。3 7 图4 2 遗传算法一般流程3 9 图4 3 染色体映射实例4 0 图4 4 单点交叉实例4 2 图4 5 基因位变异实例4 3 图4 6 随机映射算法伪代码5 4 图5 1 软件层次结构图5 9 图5 - 2n o c 映射工具界面6 0 图5 3d f g 信息输入界面6 1 图5 _ 4n o c 拓扑结构选择界面6 2 图5 5 映射算法选择界面，6 2 图5 - 6 仿真结束导出结果6 3 图6 1i m t 高级无线传输系统接收端等效d f g 6 4 图6 2m m m a p 遗传映射在不同拓扑下得到的最优延时值6 8 图6 3m m m a p 遗传映射在不同拓扑下的运行时间6 9 图6 42 d m e s h 下( 网络大小6 4 ) 遗传迭代收敛过程7 0 图6 5m m - m a p 遗传映射在不同拓扑下得到的最优功耗值7 l 图6 6m m m a p 遗传映射在不同拓扑下的运行时间7 1 图6 72 d d b 下( 网络大小3 2 ) 遗传迭代收敛过程7 2 图6 8 第组实验( 多目标映射) 的二维收敛图7 4 v 图目录 图6 - 9 延时单目标映射对比( 2 0 次遗传映射和1 0 0 0 次随机映射) 7 7 图6 - 1 0 功耗单目标映射对比( 2 0 次遗传映射和1 0 0 0 次随机映射) 7 8 图6 - 1 1 多目标映射对比( 2 0 次遗传映射和1 0 0 0 次随机映射) 7 8 v l 表目录 表目录 表6 1 数据节点权值一览表6 6 表6 2d f g 直连边权值一览表6 7 表6 3 四组实验结果对比一览表7 3 表6 4 单目标多目标5 次遗传映射对比一览表7 5 表6 5 不同迭代次数和种群大小的单目标遗传映射对比一览表7 6 表6 - 6n o c 映射求解时遗传算法和随机算法的特性区别7 9 v i l 缩略词表 缩略词表 英文缩写英文全称中文含义 a c g a p p l i c a t i o nc h a r a c t e r i z a t i o ng r a p h 应用特征图 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 dc i r c u i t 专用集成电路 c g tc o m m u n i c a t i o nt a s kg r a p h通信任务图 c nc o m m u n i c a t i o nn o d e 通信节点 d f gd a t af l o wg r a p h数据流图 e d ae l e c t r o n i cd e s i g na u t o m a t i o n电子设计自动化 g ag e n e t i ca l g o r i t h m遗传算法 g a l s 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 u i g r a p h i c a l - u s e r - i n t e r f a c e 图形用户界面 i c i n t e g r a t e dc i r c u i t 集成电路 i pi n t e l l e c t u a lp r o p e r t y 知识产权 i s i n t e g r a t e ds y s t e m 集成系统 m i m o m u l t i p l ei n p u tm u l t i p l eo u t p u t 多输入多输出 m m m a p m u l t i t o m u l t im a p p i n g多到多映射 m p s o c m u l t i p r o c e s s o rs y s t e mo nc h i p 片上多处理器系统 n o cn e 时o r ko nc h i p 片上网络 n pn o n - d e t e r m i n i s t i cp o l y n o m i a l非确定性多项式 q o sq u a l i t yo fs e r v i c e 服务质量 r ar a n d o ma l g o r i t h m随机算法 r nr e s o u r c en o d e 资源节点 r n i r e s o u r c en e t w o r ki n t e r f a c e资源网络接口 s i s 0 s i n g l ei n p u ts i n g l eo u t p u t 单输入单输出 s o c s y s t e mo nc h i p 片上系统 t gt a s kg r a p h 任务图 v i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名： 日期：纠汐年矿月咖 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 导师签名：当么衅一 日期：加( p 年眇月万日 第一章绪论 1 1 研究背景 第一章绪论弟一早 三百。1 ：匕 遵照摩尔定律的规律发展，集成电路( i c ，i n t e g r a t e dc i r c u i t ) 已有几十 年的历史。基于信息市场的需求，随着微电子自身的发展，以微细加工( 集 成电路特征尺寸不断缩小) 为主要特征的多种工艺集成技术和面向应用的系 统级芯片的发展迅速。当半导体产业进入超深亚微米乃至纳米加工时代，在 单一集成电路芯片上将可以实现一个复杂的电子系统，如手机芯片、数字电 视芯片、d v d 芯片，等等。集成电路设计者能够将越来越复杂的功能集成 到单硅片上，片上系统( s o c ，s y s t e mo nc h i p ) 正是在集成电路向集成系统 ( i s ，i n t e g r a t e ds y s t e m ) 转变的大方向下产生的。1 9 9 4 年m o t o r o l a 发布的 f l e x c o r e 系统和1 9 9 5 年l s i l o g i c 公司为s o n y 公司设计的s o c ，可能是基 于知识产权核( i pc o r e ，i n t e l l e c t u a lp r o p e r t yc o r e ) 完成的最早s o c 系统。 由于s o c 可以通过充分利用已有的设计积累，显著地提高了a s i c ( a p p l i c a t i o n s p e c i f i ci n t e g r a t e dc i r c u i t ，专用集成电路) 的设计能力，因此发展非常迅速，引 起了工业界和学术界的广泛关注。 1 1 1 片上系统 s o c 技术，是一种高度集成化、固件化的系统集成技术。使用s o c 技术 设计系统的核心思想，就是要把整个应用电子系统全部集成在一个芯片中。 在使用s o c 技术设计应用系统，除了那些无法集成的外部电路或机械部分以 外，其他所有的系统电路全部集成在一起。 用s o c 技术设计应用电子系统的几个阶段如图1 1 所示。 s o c 以其耗电量低、系统体积小、系统功能集成化、高速、低成本等诸 多优点及基于知识产权核设计理念的特性，在一段时间内成为i c 设计业界 的焦点。但s o c 性能越来越强，规模越来越大，同时由于深亚微米工艺带来 的设计困难等，使得s o c 设计的复杂度大大提高。在s o c 设计中，仿真与验 电子科技大学硕士学位论文 证是s o c 设计流程中最复杂、最耗时的环节，约占整个芯片开发周期的 5 0 - 8 0 ，采用先进的设计与仿真验证方法成为s o c 设计成功的关键。随 着半导体技术的发展，片上器件集成度的进一步提高，出现了片上多处理器系统 ( m p s o c m u l t i p r o c e s s o rs y s t e r a so nc h i p ) 。由于单芯片上集成的处理器、硬件核 心、存储器等器件的数目不断增加，因此需要一种高扩展性的通信架构来实现片 上器件之间的信息交互。 写硬件设计说明书 开发硬件行为级模型 可重用i p 核划分 s o c 集成及验证 1 1 2 片上网络 系统功能分析 写设计说明书 开发系统数学模型 验证和修改算法 软、硬件功能划分 软、硬件接口定义 软、硬件协同仿真 写软件设计说明书 软件开发 硬件电路与应用软件卜叫产品发布 图1 1s o c 设计流程图 今天，商用片上多处理器系统可以集成几十个核在一个片子上，那么将来， 集成成百上千个核在一个片子上以支持更大计算能力的多处理器系统必将出现。 为了解决当前及未来片上多处理器系统的内部复杂连接问题，以网络通讯概念为 核心的一种数据传递与交换技术，片上网络( n o c ，n e t w o r ko nc h i p ) 便应运而生， 并且得到日益广泛的关注和重视【1 】。片上网络作为一种以通讯为核心的片上系统 交换技术，可以很好地适应片上多核的复杂连接问题，因此，它成为片上多处理 2 第一章绪论 器系统内部可伸缩性微型网络的一种很好的选择。 1 片上网络的优势 相比传统总线结构，在片上多处理器系统中使用片上网络结构的主要优势可 以归纳如下： 在物理结构上具有更好的可扩展性和可伸缩性。片上网络可以根据需要， 通过结构的更改，从而改变最大带宽和所需内部连线。 在高负载情况下具有更好的性能。片上网络能实现较高的处理频率，应付 大带宽需求和并行流量的应用系统。 更容易实现模块化。由于片上网络的结构设计一般比较规则，可以从应用 中的计算结构方便地转化为通信结构，因此有利于降低结构设计的工作量。 具有更高的能耗利用率。对于相同的负载情况，相对于传统总线结构而言， 片上网络结构可以运行在较低的频率下，更快地完成数据传输，因此可以减少系 统的能耗，提高能耗利用率。 总体而言，片上网络通过并发和非阻塞交换获得更高的带宽，通过分组交 换获得更高的链路利用率，通过分层协议获得可靠的传输，通过点对点传输 获得低功耗是一种全局异步或准同步的、模块化、可升级的结构。 2 片上网络关键技术问题【2 ，3 】 网络拓扑结构选择 选择合适的n o c 拓扑结构是片上网络设计中非常关键的问题之一。n o c 网 络传输信息的能力主要依靠拓扑结构，不同的拓扑结构对网络的延迟、吞吐量、 面积、功耗、容错性能等有着重要的影响。在已有的研究当中，应用较为广泛的 n o c 拓扑结构主要包括二维m e s h 结构，二维环绕m e s h 结构，胖树结构，星型 结构，二维d b 结构，三维m e s h 结构，三维环绕m e s h 结构等等。 路由算法选择 路由算法的选择可以确定一个信息如何从源节点到达目的节点。与传统总线 结构不同，n o c 采用包交换的路由机制。对于大多数应用的n o c 设计来说，确 定性路由算法使用较为广泛，它更好地适应了n o c 的资源限制和严格的延迟需 求，具有可预测的服务质量，并且实现片上系统的低功耗设计。 交换技术选择 交换技术是在n o c 交换层中实现的技术，它决定交换节点什么时间以什么方 式连接其输入输出端口。现有n o c 交换技术比较常见的包括存储转发、虫孔交换、 虚跨步交换，均为包交换技术，即在发送数据前不需要建立链路，包通过最优路 3 电子科技大学硕士学位论文 由算法原则从而选择其最优路径到达目的地。 服务质量 服务质量( q o s ，q u a l i t yo f s e r v i c e ) 被定义为网络提供给i p 核的服务数量， 它包含服务和服务协商两方面内容。服务应该具有高吞吐量、低延时、低功耗等 特点，而协商完成的是在p 核需求的服务与网络提供的现有服务之间实现平衡。 服务质量包括尽最大努力服务和保证服务两种基本类型。他们提供不同层次的许 诺服务，并且对通信行为有潜在的影响。 流量控制 在n o c 中，流量控制的对象是交换节点之间和端到端之间的传输协议的业务 量。通过避免缓冲区溢出及丢包，这些协议提供了平衡通讯量的策略。现在多数 n o c 采用的流量控制方式主要包括虚通道方式和限制数据包注入网络速度的方 式。相对比而言，虚通道流量控制增加了硬件开销，而通过限制注入网络包的方 式可以达到限制网络中同时传输包数量的目的。 资源网络接口设计 资源网络接口( r n i ，r e s o u r c en e t w o r ki n t e r f a c e ) 是i p 核与网络间的接口， 即资源节点( r n ，r e s o u r c en o d e ) 与通讯节点( c n ，c o m m u n i c a t i o nn o d e ) 之间 的接口。由r n i 的名称不难发现，r n i 包括连接资源的部分和连接网络的部分。 通过r n i 接口，i p 核以一定的代价使用网络，同时口核与网络资源都可以得到 重用。 定时同步 在一个片上网络上，包含了多个口模块，每个p 都工作在自己的定时同步 信息下。因此如何解决n o c 的全局定时问题是n o c 在物理设计层面的一个关键 问题。目前普遍采用的解决方法是全局异步一局部同步( g a l s 。g l o b a l l y a s y n c h r o n o u sl o c m l ys y n c h r o n o u s ) 法，即每个资源节点都工作在自己的本地时 钟域，而不同的资源节点之间则通过通讯节点进行异步通讯。对于不同的n o c 设 计而言，会有不同的定时同步方法，暂时没有一个统一的标准。 映射 一般意义上的n o c 映射是在给定任务图( t qt a s kg r a p h ) 、设计约束和p 库的基础上，将每个任务分配到合适的口核上，同时安排好每个i p 核上任务的 执行顺序，然后将每个口核分配到n o c 拓扑结构中的合适位置。由上述提出的 映射中，一般来说搜索空间都随网络尺寸的增长而呈阶乘递增，因此，普通的n o c 映射问题均为n p 问题。目前，n o c 映射可以采用启发式算法求解，采用不同的 4 第一章绪论 映射算法将影响映射结果和映射过程的执行速度等。 性能评估 毫无疑问，性能评估在任何一个系统设计中都是最重要的技术问题之一。对 于n o c 来说，不同结构的n o c 将拥有不同的性能，因此为了比较不同结构的n o c ， 则需要使用标准的性能评价方法，如对能反应n o c 性能的关键要素进行分析，常 用的包括吞吐率、延迟、面积和功耗。 3 片上网络设计流程 如图1 2 ，可以将n o c 设计流程分成两类【4 1 ，称( i ) 流程为基于i p 库的设计 流程，而( i i ) 流程为基于平台的设计流程。本文所采用的n o c 映射方法是基于 平台的设计流程的。 应用描述 土 通讯任务图 1 映射、调度 1 l n o c 实现 ( i ) 基于i p 库的设计流程 ( 1 i ) 基于平台的设计流程 图1 - 2n o c 设计流程图 基于p 库的设计流程主要包括三个步骤：1 ) 将应用说明转化成为一个通讯 任务图( c o m m u n i c a t i o nt a s kg r a p h ) ；2 ) 从已有p 库中选择合适的处理单元， 然后将通讯任务图的任务分配到各个处理单元上并确定各处理单元上任务的执行 顺序，得到应用特征图( a p p l i c a t i o nc h a r a c t e r i z a t i o ng r a p h ) ；3 ) 在满足一定性能 指标和约束条件的前提下，将每个被选中的处理单元映射到n o c 的资源节点上。 与基于p 库的设计流程相比较，基于平台的设计流程相对则要简单得多，主要包 括2 个步骤：1 ) 将应用说明转化成为通讯任务图；2 ) 在满足一定性能指标和约 束条件的前提下，把通讯任务图的每个任务分配到相应资源节点上。 图1 3 给出了通讯任务图与应用特征图的转换关系：假设通讯任务图中包含 5 电子科技大学硕士学位论文 6 个任务气岛，从i p 库中选出4 个处理单元鹧，经过分配和调度之后， p e o 执行任务气、小毛，码执行任务乞，码执行任务f 4 ，鹧执行任务岛。 岛，f l ，毛 f 4 ( i ) 通讯任务图( i d 应用特征图 图1 - 3 通讯任务图与应用特征图 4 片上网络设计过程中遇到的挑战和不足 基于某个应用，设计一种满足特定约束条件且具有良好性能的高效片上网络 结构是一个很复杂的过程。总体而言，采用n o c 代替原有片上系统设计方法也带 来了一些不足，包括：由于交换电路和接口的存在增加了电路面积；数据打包、 缓冲、同步和接口增加了延迟；缓冲和增加的逻辑造成了功耗增加；与原有 i p 核接口和协议的兼容问题等。 1 。1 。3 片上网络映射问题 如前一节所述，片上网络的映射问题是片上网络设计中的一个关键技术问题 之一。根据n o c 设计流程的两种常见类型，即基于口库的设计流程和基于平台 的设计流程，那么我们也可以将映射问题简单地分为两个类型，即核映射( c o r e m a p p i n g ) 和任务映射( t a s km a p p i n g ) 【5 】。核映射即一般意义上的映射，是在给 定任务图、设计约束和口库的基础上，将每个任务分配到合适的口核上，同时 安排好每个口核的任务执行顺序，然后在分配好每个口核在n o c 拓扑结构中的 位置，如图1 3 ，完成了从任务通讯图到应用特征图的转换。而任务映射指的是 在分配任务时，根据任务之间通信量或实时性要求，把任务映射到可用n o c 资源 上。本文提到的n o c 映射是建立在任务映射上的一种更简单的映射方法。 对于基于平台设计的片上网络映射问题主要涉及以下方面内容： 6 第一章绪论 1 应用系统的图形化抽象 这是在映射过程开始之前需要进行的第一个步骤，一般而言就是根据实际的 应用说明得到需要的系统电路，然后将电路的各个要素抽象成由点、线、箭头、 权值等元素构成的赋权有向图，即前述所称的任务图( 本文采用“数据流图”代 替传统任务图的称谓) 。该赋权有向图唯一地标识一个实际的应用系统。 2 n o c 网络拓扑结构的图形化抽象 由于是基于平台的设计模式，那么在映射开始之前就需要先选定所需要的网 络拓扑结构，然后同样将网络结构的各个要素抽象成赋权图。网络拓扑对应的赋 权图的点代表一个网络节点，赋权图的边代表双向的网络通道，这是与前述任务 图的区别之处。该赋权图唯一地标识一个固定的n o c 网络拓扑结构。 3 建立数学模型 所有问题的解决最后都需要转化成为数学模型的求解。关于映射问题通常涉 及到的需要建立的数学模型包括：任务图的数学描述，网络拓扑图的数学描述， 映射算法的数学描述，映射过程需要满足的约束条件的数学描述，衡量映射结果 好坏的目标函数的数学描述。 4 映射结果的验证与分析 得到映射模型的数学表达之后，便可以通过一些实际的系统，对其数学模型 进行软件仿真和硬件仿真，从而可以得出该映射方法的优劣性。为了全面比较各 种映射方法的优劣，有时候需要通过特定的工具或者研究人员自己开发的工具来 进行判断。因此映射结果验证工具的开发也是片上网络映射问题一个重要的方面。 本文在后续章节将具体介绍笔者自己开发的n o c 映射相关e d a ( e l e c t r o n i c d e s i g na u t o m a t i o n ，电子设计自动化) 工具。 1 2国内外研究现状 n o c 是一仑崭新的话题，在国际上也只是刚刚起步不久。随着技术的不断发 展，越来越多的研究机构意识到n o c 的潜力，纷纷投入到其中并推动着它的发展， 使得n o c 成为一个十分活跃的学术前沿领域。从2 0 0 1 年开始至今，世界上有超 过9 0 家研究机构对n o c 各个层次进行了研究【6 】。国外比较著名的有k t h ，b o l o g n a 大学，s t a n f o r d 大学，p h i l i p s 公司，s tm i c r o e l e c t r o n i c s 公司，a r t e r i s 公司等。短 短不到十年内，在与n o c 设计相关的性能优化工具和e d a 工具方面已经取得的 7 电子科技大学硕士学位论文 成果包括：瑞典k t h 研发的n o c 架构n o s t r u m ，研究从物理层到应用层的通信 问题；意大利b o l o g n a 大学和美国s t a n f o r d 大学联合研发的一个可综合、高性能 的n o c ，x p i p e s 工程；荷兰p h i l i p s 公司研发的具有保证服务并提供尽最大努力 服务的n o c ，a s et h e r e r a l 工程；英国m a n c h e s t e r 大学研发的使用握手信号进行 数据交换的自定时n o c ，c h a i n 工程；由法国p i e r r ee tm a r i ec u r i e 大学研发的 通用可扩展s o c 互连网络，s p i n 工程等等。 n o c 作为一种新的通信结构，在工业界的研究也逐渐开展起来。尽管在实际 商业化芯片中，n o c 类型的通信结构还比较少见，但不少大企业大公司开始了 n o c 的相关研究，商用研究成果主要包括【3 】：s o n y 公司的p s 3 ，p h i l i p s 公司的 a e 也e r e a ln o c ，s o n i c s 公司的s m a r ti n t e r c o n n e c t ，s t 公司的s t n o c ，i n t e l 公司的p o l a r i s8 0 核处理器等等。 相对于国外的n o c 研究，国内的研究稍微滞后。近几年来国内研究n o c 的 几家主要高等学府包括合肥工业大学，清华大学，电子科技大学，西安电子科技 大学，西北工业大学等，研究成果主要局限于理论研究，如合肥工业大学的周干 民等开展的关于n o c 基础理论( 4 】的研究，清华大学的徐宁仪等提出的基于簇的层 次化片上网络c h n o c 7 】，电子科技大学的李忠琦等开展的面向软件无线电的片上 网络基础研究和m s n s 仿真器【8 】的自主研发等等。可见，国内相比于国外在n o c 方面的研究，还有很大的差距，但整体而言，由于n o c 的设计研究仍处于初始阶 段，这将为国内s o c 解决方案的研究提供了一次很好的机会。 1 3本文课题背景及主要研究工作 本文课题来源于国家8 6 3 计划项目“具有开放式无线架构的多处理器阵列软 件无线电技术”( 2 0 0 7 a a 0 1 2 2 9 1 ) 。该项目拟采用片上系统和片上网络的前沿技 术，结合软件无线电技术，用于开放式无线架构的多处理器阵列设计，用于解决 目前多处理器阵列带来的成本高、并行度低、面积增大等问题。 本论文在该项目的支持下，展开的主要研究工作和创新点如下： 在通讯任务图的基础概念上使用自主定义的数据流图代表实时的数字信号 处理系统，利用数据流图的权值和连接关系得出完整的链路信息，客观地反 映映射前数字信号系统延时、功耗等性能参数； 基于传统的n o c 设计方法和映射平台，提出了一种新的从数据流图到n o c 第一章绪论 网络拓扑的映射方法m m m a p ，实现不同规模的多点到多点的映射，原理简 单、步骤更少、具有较好的应用价值；m m m a p 选用基本遗传算法作为映射 算法的原型，通过一些改进使算法能够适应n o c 映射问题，以获得较好的算 法收敛特性；同时针对映射目标建立功耗模型、延时模型和多目标模型，相 比传统功耗和延时的数学模型，能更准确地表示映射前后系统的性能变化。 为了方便研究人员更快更全面地分析不同应用系统在不同条件下的映射结 果，笔者使用m a t l a b 的g u i 工具自主开发了一款可重配置性高、可扩展性高 的n o c 映射工具g a g u i ，同时采用该工具，结合不同的应用实例，获得了本 文中列出的所有映射数据和映射图，验证了本文提出的映射方法的优越性和 实用性。 1 4本文结构安排 本文各章结构及主要内容安排如下： 第一章：介绍本文研究背景，分析片上网络相关领域在国内外的研究现状， 简述本文课题背景及主要研究工作。 第二章：描述经典n o c 映射模型，并由此提出笔者的映射模型，重点给出数 据流图、网格型片上网络和m m m a p 映射方法的严格定义。 第三章：结合经典延时和功耗模型，提出在n o c 映射问题的数学模型，包括 映射目标函数的数学模型和约束条件的数学模型。 第四章：详细介绍在解决n o c 映射问题中采用的常用算法，着重给出随机算 法和遗传算法的算法流程。 第五章：介绍笔者设计的用于n o c 映射的e d a 工具的软件层次、设计方法 和主要特性，并附上详细的操作流程。 第六章：以i m t 高级无线传输系统接收器为应用实例，运用本文提到的映射 方法，借助笔者设计的映射工具，完成所有参数设置，得到丰富的映射结果，并 对结果进行分析验证。 第七章：总结全文和展望。 9 电子科技大学硕士学位论文 第二章m m m a p 映射模型 片上网络的核心思想就是将计算机网络技术移植到芯片设计中来，从而实现 片上多处理系统的高效并行运算。由此产生n o c 设计的两大核心内容：n o c 平 台架构研究和基于n o c 平台的映射方法研究。关于n o c 平台的架构描述由文献 f 1 0 给出，分为三种：h a r d 平台，f i r m 平台和s o f t 平台。而基于n o c 平台的映 射过程一般要经历从任务图到i p 核的调度和从i p 核到n o c 结构的映射两个步骤 【9 】。过去的大部分研究【9 】【1 1 , 1 2 】采用了f i r m 平台，文献1 1 0 1 和 1 1 1 完成了从i p 核到 n o c 结构的映射过程，而文献 1 2 完成了任务图到i p 核和i p 核到n o c 结构的两 步映射。映射的优化目标通常是最小化通信成本【1 3 】或者功耗【1 4 , 1 5 l ；不同的映射结 果，对于系统的执行时间、通信时延、通信能耗等性能有着重要的影响。 接下来，本章首先给出典型映射模型的描述，然后对笔者提出的m m m a p 映射模型给出严格定义，并将该模型与典型映射模型进行对比。 2 1 典型的映射模型 相比于传统的计算机群大型网络，片上网络具有一些不同的特性： 与典型的大型网络相比，在片上网络上能使用的资源是非常不足和有限的。 因此，片上网络首先要减少面积的代价，从而实现整体系统代价的减少。 大部分大型网络的设计目标只有一个，那就是不顾一切地去获得最高的网 络性能( 如吞吐量，平均包延迟等) ，而大部分n o c 的设计都会有一定功耗的约 束。随着移动设备产品市场的不断拓展以及芯片价格地持续下降，低功耗设计的 概念变得越来越重要。事实上，对于很多种类的产品来讲( 如便携式多媒体设备， 手机等) ，功耗已经成为产品设计的主要优化目标，而性能只是作为其中的一个典 型的设计指标。 大型网络设计完成后一般能够提供适用于各种应用的通用平台，而大部分 的片上网络开发之后只能适用于特定的应用或者用于- - j , 类应用。 基于以上几点区别，显然不能将现有的大型网络设计技术直接搬到n o c 的设 计领域中来。那么，就需要有一种面向n o c 的专用设计方法，这种方法能够很好 1 0 第二章m m m 姐殃射模型 地在完成n o c 设计的过程中同时最大化n o c 的优势。因此，关于n o c 的研究就 此开展开来。不失一般性，这里可以将n o c 平台粗略分成三类【9 】：硬( h a r d ) 平 台、固( f i r m ) 平台和软( s o r ) 平台。如图2 - i 所示。 n o c 硬平台指的是具有完全确定的架构的n o c 设计平台。对于硬平台来说， 网络上所有的计算单元、通信单元和通信结构都被预先设计好。因此该平台不具 备结构可定制的灵活性，而面向该平台的设计任务只剩下通信和任务的调度问题。 园园叵 日日匣 困回回 圈困曰 圆圆囤 固回囤彗垂隧 删谲二隧蒌| 囊| 鬓| ； ：辫搿。掣 圈2 一in o c 设计平台 n o c 固平台比硬平台稍微灵活一点，网络上的通信结构是预先设定好的，而 不同的网络结构中的基本通信单元上嵌入哪些口核则是可选的。设计者需要像填 充空位一样将各个口核一个个地填入相应的通信单元上。固平台的设计问题主要 就是口映射和路由路径分配的问题，即一方面要考虑如何将不同i p 核映射到不 同的n o c 通信单元上，另一方面考虑映射完后通信单元之间如何作好路径规划， 以保证最小化设计代价( 如功耗) 。 而n o c 软平台作为三种类型中灵活性最高的设计平台在使用该平台设计时， 设计者可以选用不同的网络通信单元( 即采用不同的网络连接方式) ，在完成p 核到通信单元的映射之后构建完整的新的片上网络。设计者可以根据具体应用的 特性来灵活地选择n o c 的连接结构。而这种不周于硬平台或者固平台的灵活性也 导致了一些问题，那就是一些设计特性( 如平面布置圈、线宽等) 无法预先确定 圈。口 电于科技大学硕士学位论文 一蒋一 一萼稀：簿爹萝 口墨日口、”一生囝f 昏裂， 第二章m m - m a p 映射模型 于n o c 路由自身面临的约束和资源问题与广域网不同，因此，n o c 路由策略具 有实现算法简单，节约资源的特点。n o c 路由一般采用以虫洞路由 ( w o m t h o l e t b a s e dr o u t i n g ) 等确定性路由为代表的路由策略。 最简单且研究最为成熟的n o c 网络结构当属2 d - m e s h t ”啊络结构。假设由 个网格组成的2 d m e s h 网络，它的网格结构如图2 - 3 所示。每一个网格都由 一个处理器核和一个路由器组成。每个路由器都与相邻的四个网格以及这些网格 上的处理器单元相连通每一条这样的通道都由两条单向的点到点链路组成。由 于资源有限，缓冲器( b u f f e r s ) 用寄存器实现，且宽度较小。路由嚣的核心是一 个5x5 交叉开关( c r o s s b a rs w