（计算机科学与技术专业论文）基于gsa算法的noc映射研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得武汉理工大学或其他教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 签名：雠日期：也! ! ：! 乡 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签 导师( 签名) 喀詈世厂日期弘1 1 f 哆 憎j 寸 7 摘要 近些年来，由于基于总线结构的片上系统所带来一些问题，借鉴计算机网络 的思想，研究者们将网络设计技术应用到芯片设计中，提出了片上网络，以解决 总线结构所不能解决的问题，从而达到提高模块的可重用性，以及增强系统的可 扩展性和灵活性。在单芯片上集成更大规模的电路是n o c 设计的最终目标，功耗、 速度和面积是n o c 设计的重要因素，随着纳米级工艺技术的发展，功耗已是n o n 设计的重要约束，特别是便携式手持设备，如p d a 、手机等产品，功耗已经成为 该类产品设计的瓶颈。如何降低片上网络的通讯功耗，已成为n o c 设计者们关心 的问题。 n o n 映射：是指在给定网络拓扑结构、应用的任务图描述、m 核库以及设计 约束( 功耗、延迟和面积等) 的基础上，为每个任务选择合适的p 核，并且根据任 务图来确定口核上任务的执行顺序，然后再决定已被选择的口核之间的互连关 系，即他们在n o n 网络拓扑结构中的位置关系。 针对片上网络设计中的低功耗映射问题，本文在研究分析了低功耗模型的基 础上，提出了一种新的降低功耗的的优化方法一基于遗传模拟退火的组合优化算 法，它将模拟退火嵌入到遗传算法中，采用模拟退火对个体寻优，然后通过遗传 算法，对群体寻优。此算法在满足通讯延迟的情况下，能很好的降低系统的通讯 功耗，同时能加快算法的收敛速度。 关键词：片上系统，片上网络，遗传模拟退火算法，低功耗映射。 a b s t r a c t i nr e c e n ty e a r s , d u et ot h ec h i pb a s e d0 1 1b u ss t r u c t u r et h a tb r i n g s 舳ep r o b l e m s r e s e a r c h e r sa p p l yn e t w o r kd e s i g nt e c h n o l o g yt o c h i pd e s i g np r o c e s s ，a n dp r e s e n t sa p i e c e i no r d e rt os o l v et h en e t w o r kt h a tc a n n o tb es o l v e db yb u ss t r u c t u r e , s o 嬲t o i m p r o v et h em o d u l er e u s a b i l i t y , e n h a n c et h es y s t e ms c a l a b i l i t ya n df l e x i b i l i t y , i d e a s w h i c hr e f e r e n e df r o ms y s t e mo fc o m p u t e rn e t w o r k i n t e g r a t i n gm o r el a r g e s c a l ec i r c u i t i na s i n g l ec h i pi st h eu l t i m a t eg o a lf o rd e s i g n i n gn o cd e s c r i p t i o n p o w e r , s p e e da n d a r e ai st h ei m p o r t a n tf a c t o r so fd e s i g n i n gn o c d e s c r i p t i o n w i t ht h ed e v e l o p m e n to f n a n o s c a l et e c h n o l o g y , p o w e rc o n s u m p t i o ni sa l r e a d ya l li m p o r t a n tc o n s t r a i n t n o c d e s c r i p t i o nd e s i g np o r t a b l eh a n d h e l dd e v i c e s , e s p e c i a l l yp r o d u c t ss u c ha sm o b i l e p h o n e , p d 八p o w e rc o n s u m p t i o n , h a sb d ? , o m et h e b o t t l e n e c ko fs u c hp r o d u c t d e s i g n h o wt or e d u c et h ep o w e ro f c o m m u n i c a t i o nn e t w o r kc h i ph a sb e c o m ea c o n c 锄f o rd e s i g n e r so fn o cd e s c r i p t i o n n o cd e s c r i p t i o n m a p p i n gi st op o i mt ot h er e l a t i o n s h i po fp o s i t i o nb e t w e e n i n t e r c o n n e c t e di nt h e i rn o c d e s c r i p t i o nn e t w o r kt o p o l o g ys t r u c t u r ei nag i v e nn e t w o r k t o p o l o g ys t r u c t u r e , a p p l i c a t i o nt a s kg r a p hd e s c r i p t i o n , i pc o r el i b r a r ya n dd e s i g n c o n s t r a i n t s ( p o w e rc o n s u m p t i o n , d e l a ya n da r e a , e t c ) ，o nt h eb a s i so fa p p r o p r i a t ef o r e a c ht a s la n da c c o r d i n gt ot h ei p 他t a s kg r a p ht od e t e r m i n et h ee x e c u t i o no ft h ei p c o r et a s ka n dt h d e c i d e dt oo r d e rh a sb e e nc h o s e ni pn u c l e a r a c c o r d i n gt oc h i pn e t w o r kd e s i g no ft h el o wp o w e rc o n s u m p t i o nm a p p i n g p r o b l e m s , t h ep a p e rp r o p o s e san o wm e t h o df o rt h eo p t i m i z a t i o no fl o w e rp o w e r c o n s u m p t i o na f t e rr e s e a r c h i n ga n da n a l y s i n gl o wp o w e rc o n s u m p t i o nm o d e l r b a s e d o ng e n e t i cs i m u l a t e da n n e a l i n ga l g o r i t h mo fo p t i m i z i n g , i te m b e d e ss i m u l a t e d a n n e a l i n g i n t o g e n e t i ca l g o r i t h m ，w h i c h 嘲s i m u l a t e da n n e a l i n gt oo p t i m i z e i n d i v i d u a l ，a n dt h e no p t i m i z eg r o u p sb yt h eg e n e t i ca l g o f i t h r a n l i sa l g o r i t h mi sg o o da t r e d u c i n gp o w e ro fc o m m u n i c a t i o nc o n s u m p t i o no ft h es y s t e ma n dc a na c c e l e r a t e c o n v e r g e n c es p e e di nm e e t i n gc o m m u n i c a t i o nd e l a y s k e yw o r d s ：s y s t e m - o n - c h i p ； n e t w o r k - o n - c h i p ； g e n e t i cs i m u l a t e da n n e a l i n g a l g o t i r t h m s ：l o wp o w e rc o m u m p u t i o nm a p p i n g 目录 摘要i a b s t r a c t i i 第l 章绪论。l 1 1 研究背景1 1 2n o c 的研究动态。3 1 2 1n o c 国际研究动态3 1 2 2n o c 国内研究动态4 1 3 本文的主要研究内容5 1 4 本文的组织结构：6 第2 章n o ( 2 关键技术研究7 2 1n o c 概述。7 2 1 1 n o c 概念7 2 1 2n o c 技术优势分析。8 2 1 3n o c 的性能评估8 2 2n d c 互连结构9 2 2 1n o c 拓扑结构9 2 2 2n o c 资源节点1 3 2 2 3n o c 通讯节点1 3 2 3n o c 通信协议l5 2 3 1 物理层16 2 3 2 数据链路层1 7 2 3 3 网络层1 8 2 3 4 传输层18 2 3 5 系统与应用层1 9 2 4n o c 设计流程19 第3 章n o c 路由策略2 l 3 1n o c 包交换技术：2 l 3 1 1 电路交换技术 3 1 2 存储转发交换技术2 2 3 1 3 虚拟直通交换技术2 3 3 1 4 虫孔交换技术2 4 3 2n o c 路由算法2 5 3 2 1 确定性路由2 6 3 2 2 自适矗立路由。2 7 3 3 本章小结3 l 第4 章基于g s a 优化算法的n o c 映射研究3 2 4 1g s a 算法概述3 2 4 1 1 遗传算法3 2 4 1 2 模拟退火算法4 0 4 1 3 遗传模拟退火算法4 2 4 2n o c 映射问题4 3 4 3n o c 映射数学模型4 4 4 3 1 功耗模型4 5 4 3 2 问题形式化描述。4 6 4 4 基于g s a 优化算法的n o c 映射的实现4 7 4 5 本章小结5 0 第5 章总结与展望。5 l 5 1 总结5 l 5 2 展望5l 参考文献5 2 致谢! 洱 附录：攻读硕士学位期间公开发表的论文5 5 武汉理工大学硕士学位论文 第1 章绪论 伴随着半导体工艺技术的快速发展，将大规模晶体管集成到单一芯片上的梦 想成为了现实，已经能够将大量的口模块( 包括d s p 、视频音频流处理器、高带 宽i o 模块等) 和嵌入式的存储单元集成到一起。但是多种运算模块的协同工作 需要更多的通信资源。以往以总线结构互联的芯片设计模式以不能满足这一需求， 片上网络以通信网络为中心的芯片设计模式必然取代片上总线模式。 1 1 研究背景 随着半导体技术的快速发展，越来越复杂并且多元化的功能正逐渐的被集成 到单一芯片上，i c 设计慢慢的开始向集成系统转变，在这个转变的过程中，出现 了s o t 2 。s o c 把数字和模拟混合电路集成在单s i 芯片上，该数字和模拟混合电 路包括存储器( s d r a m 、s r a m 、f l a s hr o m ) 、嵌入式核( m c u 、d s p 或m p u ) 、 以及一些专门使用在某一领域的功能模块，比如p l l 、d a c 、2 d 3 d 图形运算单 元等等。s o c 设计采用口核复用技术，即选择你需要的m 核，口核的互连成为 总线结构的关键，s o c 采用总线结构来实现各坤核之间的通讯。然而随着半导 体技术的发展和芯片集成度的增加，以总线互连的结构必然导致一些问题的出现， 以下列出s o c 几个主要的问题： a ) 可扩展性差。在做需求分析的时候，s o c 中的各功能模块根据特定的应 用已经确定下来，固定好各物理模块位置，使得位置不轻易改变，使得系统运行 更加稳定。为使得在深亚微米效应下s o ( 2 能够正确工作，针对这一具体需求，对 总线、时钟网络和其他全局信号走线都进行了专家设计。一旦s o ( 2 物理设计完毕 后，如果出现不合理设计或者个别错误，这将是非常严重的问题，因为各模块已 经固定下来，而纠正这种不合理设计或者个别错误，需要考虑全局各模块，这样 好比重新对s o c 进行了设计。 b ) 平均通信效率低。总线结构是s o c 关键所在，s o c 中各功能模块是采用总 线互连的，如同1 1 所示，在某个时间段内，只能有一个功能模块独占总线，如 m p u 和动态存储器通讯时，其他模块不能使用总线进行通讯，只有当m p u 和动 态存储器通讯结束，交出总线控制权，其他功能模块才能获得总线控制权，和别 的模块进行通讯。从通讯的局部来看，因为某一时段内，只有一个功能模块独占 总线，一旦某个功能占有总线时，它的通讯速度非常快，效率也是非常高的。这 只是对某个占有了总线的模块而言，对于那些没有占有总线的模块来说，它们要 等 效 的 几 构 问 单 源 武汉理工大学硕士学位论文 n o c 体系结构有效地解决了因总线结构而引起的一系列问题：1 ) 可扩展性 差的问题，因为s o c 的地址空间是有限的，必然限制了系统的扩展；2 ) 平均通信 效率低的问题；3 ) 功耗和面积大的问题。 随着片上网络上集成的口核数目越来越多，p 核之间的通讯功耗成为n o c 设计的重要问题，如何提出一种n o n 映射优化算法，降低m 核之间的通讯功耗， 成为n o c 研究的热点。 1 2n o c 的研究动态 1 2 1n 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 的关键问题上，包括通讯延 时、通讯功耗、网络拓扑结构、路由算法以及系统性能等方面，就不同研究点提 出相应的解决方案。比如在研究网络拓扑结构设计方面，研究者们提出了诸多解 决方案，比如c l i c h e ( c h i p - l e v e l i n t e g r a t i o no fc o m m u n i c a t i n gh e t e r o g e n e o u s e l e m e n t s ) 【1 1 、2 dt o r o u s 2 1 、o c t a g o n l 3 和b u t t e r f l yf a t - t r e e ( b f t ) 【4 】等架构。 在路由算法方面，研究者们提出了基于确定性路由策略的d o r ( d i m e n s i o n - o r d e r e d m u t i n g ) 【5 】和r o m m 6 1 等算法，还有研究人员提出了自适应路由算法。在功耗方 面，j i n g c a oh u 、r m a r c u l 懿c u 研究团队 7 - 9 1 提出了大量的重要的结论。与此同时， 各研究团队通过自己的理论基础开发出了用于测试的n o c 原型系统【l 们。以下以表 格的形式列出在n o c 研究方面取得重要成果的研究机构或大学以及他们的研究的 项目，如表1 1 1 所示。 除了表中所列举的之外，还有许多国家也参与了n o c 方面的研究工作，比如 希腊、芬兰、意大利、法国、印度等。 3 武汉理工大学硕士学位论文 表1 1 1 在n o c 方面研究取得成果的机构或大学 n o c 研究机构研究的工程项目项目概述 p i e r r ee tm a r i es p 玳s p i n 是可编程、可升级的集成网络，它 c u r i e 大学将并行计算中的分组交换技术引入系 统芯片，从而实现数据通讯 瑞典皇家技术学院 n e t w o r k - o n - c h i p瑞典皇家技术学院第一次提出n o c 概 和芬兰盯大学 a r c h i t e c t u r e念，其定义为在单一芯片上实现的，由 n o c a r c交换开关互连的存储资源、计算机资源 和i o 资源，并同v 1 1 大学联合启动 n o c a r c 计划，开始研究n o c 基础架 构 m a n c h e s t e r 大学 c h a i nc h a i n 是通过一个握手信号实现数据 交换的n o c ，它采用细粒度流水线的链 路互连。c h a i n 网络的数据交换采用存 储转发的包交换技术，路由策略采用分 布式路由。 美国麻省理工学院r a wr a w 使用的架构是简单的和高度并行 的v l s i 架构，指令集是可扩展的和可 配置的。r a w 结构中资源的分配、调 度、通信、计算和模块间的同步都是由 编译器决定的，由于r a w 的细粒度通 信采用的是本地存储器来实现的，因此 它能够挖掘出一磐应用的并行性。 i n t e l t e r a f l o p n o c t e r a f l o p n o c 是一个多核系统，它具 有8 0 个处理器，基于1 0 x 8m e s h 二维 网络。每个核由本地指令、双浮点处理 单元以及数据存储器组成。处理器核与 消息传递的5 端口的路由器互连。该芯 片可应用于多媒体数据挖掘、实时视频 通信以及手持实时语音识别等方面。 1 2 2n o c 国内研究动态 随着片上网络的快速发展，国内一些高校和研究机构也纷纷投入到n o c 研究 领域中来，并取得可喜的科研成果。但是，相比国际而言，国内在这一领域的研 究起步还是比较晚的，国内从事n o c 研究的机构和成果主要包括： ( 1 ) 以樊晓娅、荆元利等人为代表的西北工业大学的研究团酣n l ，通过对n o c 体系结构的深入研究，在片上网络o s i 参考模型中引入模块化的测试方法，从而 提出基于n o c 的模块化测试方法。 ( 2 ) 合肥工业大学的教授周干民和高明伦等人【1 2 】对n o c 的理论基础进行了深 4 武汉理工大学硕士学位论文 入研究，得出重要的理论结果：n o c 在解决多核系统体系结构相关问题方面具有 很好的优势，并且解决了总线结构中的全局时钟问题。他们在理论研究的同时， 对n o c 芯片设计也有所研究，并设计了8 核的n o c 芯片模型。 ( 3 ) 以马立伟、孙义和等人为代表的清华大学研究团队【1 3 1 ，定义了片上系统 的对象消息级原型，将面向对象的方法引入到系统建模中，分两步实现：1 ) 根据 特定的规则把对象映射为硬件模块：2 ) 将对象间的函数调用映射为n o c 上的消息 传递，通过两部映射完成系统划分和通信特征提取。然后将片上系统的通信特征 进行提取，从而构造n o c 拓扑结构，并自动生成网络结构的源代码，对面向应用 的n o c 设计提出了一般方法。 ( 4 ) 以张岩、周文彪等人为代表的哈尔滨工业大学的n o c 研究团队1 1 4 j ，深入 研究了n o c 的功耗问题，提出了n o c 低功耗、自适应数据的保护机制，在各路由 节点之间对数据进行保护，确保系统芯片通讯功耗最小。 1 3 本文的主要研究内容 功耗是n o c 映射的重点问题，很多研究人员采用各种有效的启发式方法，在 满足一定约束条件下，把优化n o c 映射作为重要目标。n o c 映射是指在给定网络 拓扑结构、应用的任务图描述、m 核库以及设计约束( 功耗、延迟和面积等) 的 基础上，为每个任务选择合适的口核，并且根据任务图来确定口核上任务的执 行顺序，然后再决定已被选择的口核之间的互连关系，即他们在n o c 网络拓扑 结构中的位置关系【1 5 l 。在n o c 映射时，随着n o c 拓扑结构的网络尺寸的增长， 映射搜索的空间呈阶乘增长，比如对一个含有1 2 个m 核的n o c ，将有1 21 种映 射结果，可见映射问题是一个n p 难问翘1 6 1 。n o c 映射是n o c 设计的最后一个阶 段，映射的好坏直接影响着系统的通讯功耗和通讯时延，如何提出一个高效的映 射算法是研究者一直关注的问题。本文研究的主要内容就是寻找一种优化算法， 使得n o c 映射更快，并且n o c 闻通讯功耗更小，为此，本文提出了遗传模拟退 火( g e n e t i cs i m u l a t e da n n e a l i n g ，g s a ) 组合优化算法，并研究分析了n o c 路由 策略和路由算法。 武汉理工大学硕士学位论文 1 4 本文的组织结构 本文总共分为五章，各章安排如下： 第l 章为绪论部分，主要讨论了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 各层的通讯协议。 第3 章主要介绍了n o c 的路由策略和路由算法，n o c 间的路由技术的好坏， 直接关系到网络拥塞和死锁问题。 第4 章本文的核心部分，研究基于g s a 优化算法的n o c 映射，首先简单概 述了下遗传算法和模拟退火算法，接着研究了g s a 优化算法在n o c 映射中的应 用以及算法的实现，详细介绍了算法实现的每一步骤。 第5 章总结和展望，对全文进行了总结，并提出了以后的研究工作。 6 武汉理工大学硕士学位论文 2 1n o c 概述 第2 章n o c 关键技术研究 2 1 1n o c 概念 片上网络n e t w o r k - o n - c h i p ( n o c ) 是指在单芯片上，由大量集成的各种资源 所互连形成的通讯网络。如图2 1 所示。n o c 是片上系统( s y s t e m - o n - c h i p s o c ) 的一种新的设计方法，由于s o c 设计中面临全局同步的问题，基于片上网络的体 系结构系统能够很好的解决全局异步局部同步的时钟机制，现在复杂的芯片设计 中能够发挥很好的作用，解决总线结构所不能解决的一些问题。基于n o c 的体系 结构是一种全新的片上通信方法，由于n o c 的提出，使得基于传统总线结构的系 统性能得到很大的改善。基于n o c 的体系结构由两部分组成：1 ) 计算子系统，2 ) 通信子系统。其中计算子系统是指由p e ( p r o c e s s i n ge l e m e n t ) 构成的子系统，它 的任务是完成广义的“计算一，此处p e 只是个代词，它既可以是现有意义上的 s o c 、处理器、存储器，也可以是某个专用功能的i p ( i n t e l e t u a lp r o c e s s ) 核、可 重构硬件，甚至可以是m e m s 器件等；而通信子系统是指由s w i t c h 组成的子系统， 它主要作用是连接p e ，实现各功能模块之间的通信，如图2 1 所示。 圈鼬畅囤髓置黻圜冀一与_ 雌口囤张鞔 囵一存 圆一元回噼h 元 图2 - i 片上网络结构图 7 武汉理工大学硕士学位论文 2 1 2n o c 技术优势分析 n o c 采用基于分组存储路由方式进行片上通信，使得基于n o c 体系结构的芯 片在通信功耗、口核重用、通信方式等方面都有着很好的实用性。n o c 所体现出 来的技术优势主要有以下几方面： ( 1 ) n o c 体系结构有利于提高通讯带宽 总线结构是指所有的功能模块共用一条总线进行通信，在模块比较少的情况 下，总线结构能够很好的发挥作用，但是随着系统的功能越来越强，芯片上所集 成的模块越来越多，大量的模块共用总线通信，导致系统的通信效率很低。虽然 总线结构可以有效地连接多个口核，但是随着计算单元不断增加，总线结构的地 址资源并不能无限扩展；虽然多个通信方可共享总线，但是某一时段，只能有一 对通信方获有总线控制权，这一串行访问机制必然导致通信的瓶颈。 n o c 网络拓扑结构采用计算机网络的思想，它有着如下的优点：1 ) 具有良好 的可扩展性；2 ) 具有良好的并行通信能力，从而使得通信带宽大大增加；3 ) 具 有更低的通讯功耗，由于n o c 采用交换开关互连口核，使得m 之间的连线大大 缩短，这有利于通信功耗的控制；4 ) n o c 借鉴网络中通讯协议的分层思想，这有 利于从物理层到应用层之间的各层来控制功耗。 ( 2 ) n o c 体系结构有利于提升i p 核重用设计 由于总线架构的可扩展性和可重用性很差，为此在芯片处理能力的发展过程 中，随着芯片处理能力的需求不断变化而不断的改变芯片设计，任何一代芯片的 功能都不可能完全没变化，它都有一定程度的变更，随着需求不一定，这种变更 也是不定的，对于开发人员来说，根据不定的变更而不断的改写程序，这是很头 疼的过程。为缩短芯片设计周期和减少开发成本，将通信架构独立设计，并运用 更加弹性的技术。 由于通信协议层在n o c 中本身属于独立的资源，因此n o c 是一种高效率、m 可重用设计方法学的体系结构。现有的s o c 整体可以作为计算节点“即插即用“于 n o c 的网络节点，当作n o c 的一个网络节点来用；n o c 采用网络拓扑结构互连， 使得通信和计算完全分离，通信和计算是两个独立的步骤。由于计算和通信的分 离，如今重用不单单是计算单元可重用，而是计算和通信单元皆可重用，从而大 大提升了重用设计的水平。 2 1 3n o c 的性能评估 任何一套方案或者架构的优劣，都需要标准的评估体系，来帮助研究者选择 8 武汉理工大学硕士学位论文 更优的架构或者方案，n o c 体系结构的性能评估体系包括如下几个方面： ( 1 ) 吞吐率 吞吐率是关于计算机系统或者数据通信系统的数据传输率的测速，这些系统 包括路由器、网桥、网关等等。吞吐率是一个重要的衡量指标，它反映了一个系 统以及该系统的部件在处理数据请求的能力。简而言之，吞吐率就是指在给定的 时间内，从一个节点传输到另一个节点的数据量。在n o c 体系结构中，吞吐率是 指单位时间内，数据包通过网络的数量。 ( 2 ) 延时 延时是指数据从源节点传输到目的节点所花费的时间总和，数据传输过程中 的路径常常包括：适配单元、路由节点和连线，所以传输延时由三部分组成：数 据在源节点的发送延时、网络传输的延时以及数据在目的节点上的接收延时。源 节点与目的节点的距离和采用的路由算法是决定延时的关键因素。 ( 3 ) 面积 由于n o c 是在单芯片上设计，所以面积也是n o c 设计的重要因素，n o c 体 系结构芯片的面积主要有三个部分：c a ) 路由节点的交换部件所消耗的面积；( b ) 芯片上的布线所消耗的面积；( c ) i p 核与网络的接口适配单元和输入输出适配单 元的面积。 ( 4 ) 功耗 功耗是指数据在网络传输上所消耗的能量，n o c 体系结构上的功耗主要分为： 交换开关上的功耗和链路上的功耗。功耗也是n o c 研究中的重点问题。 2 2n o c 互连结构 2 2 1n o c 拓扑结构 片上通讯方式由点对点连接方式演变到基于总线的互连，到最后的基于分组 交换网络的互连。点对点的连接方式如图2 2 ( a ) 所示，点对点连接方式的缺点 主要表现如下：( 1 ) 每个核将产生大量的连线管脚，( 2 ) 芯片面积一定程度的增 大，( 3 ) 无法预测的信号延迟以及信号质量问题，( 4 ) 系统可升级性很差，大量 连线资源因不可重用而浪费。但是基于点对点连接方式的s o c 通讯性能将是最优 的。目前s o c 设计中通常使用的是基于总线互连，如图2 2 ( b ) 所示，各个口 核通过总线互连，从而减少各个p 核的管脚，达到简化连线的作用。基于总线结 构互连的s o c 基本解决了由点对点连接所带来的一些列问题。但是各m 核共享总 线上有限的带宽，所以总线结构互连方式满足不了大型系统的性能要求。基于分 组交换和存储转发的n o c 解决了点对点、基于总线结构所不能解决的问题，可以 9 武汉理工大学硕士学位论文 预料，基于n o c 的芯片将是下一代的主流产品，如图2 2 ( c ) 所示。 基于总线的互连 ( c ) 基于分组交换同络的互连 图2 - 2 片上通讯方式的连线演变图 拓扑结构是指通讯节点在芯片上分布和连接的方式。良好的拓扑结构对芯片 的性能起着至关重要的作用，拓扑结构的选取需根据节点模块的尺寸、系统需求 和节点间的位置来选取。以下因素是判定拓扑结构良好的标准：1 ) 通讯节点之间、 通讯节点与资源节点之间的通讯要尽可能的相邻，这样通讯功耗相对会很低。2 ) n o c 的通信信道是由物理连线组成的，所以节点之间要具有可扩展性，且节点间 的连接不能太复杂。 通过查找研究当前的一些文献，作者总结出几种拓扑结构类型，介绍如下： ( 1 ) 2 维网状网络结构( 2 - dm e s h ) ，它是n o c 拓扑结构中使用最多的一种结 构，它可具体细分为规则的( r e g u l a r ) 、不规则的( i r r e g u l a r ) 以及稀疏的( s p a r s e ) 目前研究中使用最多的拓扑结构就是规则的2 dm e s h 结构，如图2 - 3 ( a ) 所示， 节点s 代表通讯节点，节点r 代表资源节点，一个s 连着一个r ，除边界节点外， 每个s 同时连着四个s 。通讯节点对资源节点的数据进行存储转发。eb o l o t i n 等 人在研究面向服务质量( q o s ) 的n o c 时提出了不规则的2 dm e s h 拓扑结构，如 图2 3 ( b ) 所示，图2 - 3 ( c ) 表示的是稀疏的2 维网状网络拓扑结构。 芹i 阿到斟刨 ( a ) r e g u l a r2 - 1 ) m e s h ( b ) l r r e g u l a r2 dm e s h ( c ) s p a r s e 2 - 1 ) m e s h 图2 - 32 - d 网状网络拓扑结构图 ( 2 ) 蜂窝结构( h o n e y c o m b ) ，相比其他结构而言，蜂窝结构的连线比较 l o 武汉理工大学硕士学位论文 多，连线资源相对比较紧张。如图2 _ 4 所示，黑色的框代表通讯节点，白色 的框代表资源节点，一个资源节点连着三个资源节点，同时又与三个通讯节 点相连；而一个通讯节点用于数据的存储转发，所连接的节点数目更多，它 与六个资源节点和六个通讯节点相连。 图2 4 蜂窝拓扑结构图 ( 3 ) 2 维折叠环结构( 2 df o l d e dt o r u s ) 在2 维网状网络结构的基础上，w j d a l l y 提出一种新的构想：采用数据包通 讯方式的互联网络代替以前的连线结构。基于这样的构想，w j d a l l y 提出了2 维 折叠环的拓扑结构。它将处于拓扑结构边界的通讯节点彼此连接起来，使得边界 节点之间的通讯更快，整体形成一个环路，但是也带来了一些不好的地方，首先 增加了节点之间的连线，其次如图2 5 所示，环路之间存在交叉，这就使得在具 体布线时，需要更多的布线空间 图2 - 52 维折叠环结构图 ( 4 ) 八角形网络结构( o c t a g o nn e t w o r k ) 八角网络结构是e k a f i m 在研究网络处理器时所提出的一种新的拓扑结构， 武汉理工大学硕士学位论文 如图2 - 6 所示。在单个八角形子网络中，任意两个资源节点之间只需要通过两个 内部的连线就可以进行通讯。 图2 - 6 八角形网络结构 ( 5 ) 胖树网络结构( f a t - t r e e n e t w o r k ) 胖树网络结构是由g u e r d e r 等研究者在设计可编程( p r o g r a m m a b l e ) 、可升级 ( s c a l a b l e ) 的集成网络( i n t e g r a t e dn e t w o l k ) 时提出来的一种拓扑结构。如图2 7 所示，树的深度越大，则节点间通讯时间越长，对于深度为三的胖树结构来说， 任意两个资源节点之间通讯最多只需要经过三个通讯节点 q 嘲t 晡椭 m 啊蛐一l 霉k 蛸o f 缸翻露 图2 7 胖树网络结构图 影响一个拓扑结构的性能的参数有以下几个方面：( 1 ) 距离，指两个节点之 间的节点数；( 2 ) 带宽，指网络中所能传输的最大流量；( 3 ) 连接度，指与节 点直接毗邻的节点数；( 4 ) 通讯延时，信息从源节点传输到目的节点所花费的时 间总和。单从这些参数来看，规则的2 dm e s h 结构并不是最好的，但是由于规则 的2 dm e s h 的结构简单、易扩展性、良好的重用性和易于实现等优点，很受研究 者们的欢迎，大多数研究者都选择规则的2 dm e s h 结构。 1 2 武汉理工大学硕士学位论文 2 2 2n o c 资源节点 资源节点就是口核，实现某些功能的模块，一个应用程序，根据功能划分成 不同的模块，每一个模块对应一个资源节点。n o c 对资源节点的类型并不限制， 可以是任意类型的节点，比较典型的资源节点有：d s p 核、专用的硬件资源、带 缓存的嵌入式微处理器、可重构的硬件资源，或者是各种资源的组合。图2 8 显 示了n o c 中可能包含的一些资源。微处理器核、d s p 核代表的是计算类的资源节， 为了防止访问数据时更快，对于存储类资源节点就要尽可能的分散。对于不同尺 寸的f l a s h 、d r a m s 、s r a m s 资源节点可以满足不同的需求。 曰嚼一圈i l m a - ea t 越困 图岫囤m w 硼团h h 嘲i n t , _ - f a e * 图2 - 8 资源节点中包含各种类型的硬件资源图 2 2 3n o c 通讯节点 n o c 是由多个通讯节点互连起来的网络，所以通讯节点是片上网络的主要元 素，而交换开关又是通讯节点的核心。通讯节点是用来存储转发资源节点之际的 信息的，存储转发的功能是由交换开关来实现的，它将从某个输入端口传来的信 息，按着选择机制从一个或多个输出端口分发出去。通讯节点之所以能进行存储 转发，是因为它带有缓冲器，通过缓冲器将传进来的信息先缓存，但是缓冲器需 要占用很多空间，增加芯片的面积，所以如何减小缓冲器的空间是通讯节点设计 的一个难点。如图2 9 ( a ) 所示，这是一种带有输入和输出缓冲器的交换开关。如图 2 - 9 ( b ) 所示，和图2 1 0 ( a ) 不同的是，这个交换开关不带有缓冲器，所以它的结构 相对来说简单，并且节省空间。由于没有缓冲器，它传递的数据包都是自带寻址 信息，并且独立地从源节点传输到目的节点【m 1 3 武汉理工大学硕士学位论文 图2 - 9 交换开关结构示意图 通讯节点r o u t e r 的结构主要有几个部分组成：输入通道、输出通道、交换开 关。 输入通道具体又分为如下几个功能模块： ( 1 ) 输入流控制模块：路由器之间或者路由器和口核之间的通讯是根据两种 信号来实现的：输入请求信号i n p u tr e q 和输入接受信号i n p u ta c k 。输入流控制模 块的功能就是提供这种通讯握手信号。当i n p u tr e q 信号为有效时，说明上一级路 由器想要和自己通讯，输入流控制模块首先判断i n p u ta c k 信号的状态， 当 i n p u ta e k 为有信号时，表明缓冲器还未满，可以接受数据，然后和上一级路由器 的某一个输出端口建立通道，进行数据的传输。当i n p u ta c k 为无信号状态时，表 明缓冲器已满，通道无法建立，不能进行数据的传输。 ( 2 ) 输入缓冲区模块：对于传统的计算机网络中的路由器来说，最重要的是 缓冲区的大小，而对路由器的功耗和面积考虑不多，所以往往采用d r a m 和s r a m 这样的大缓存来实现。片上网络是在单芯片上实现的，功耗和面积都是片上芯片 设计的重点，对于面积消耗很大的s r a m 和功耗很大的d r a m ，并不适合片上网 络。n o c 中路由器的数据交换技术采用的是冲孔路由技术，缓冲器采用寄存器来 实现， ( 3 ) 头部解析单元模块：通过分析头部解析单元的信息，对数据片进行解析 以及路由选择，而路由的选择一般采用确定性维序x y 路由算法。路由的过程是 这样的：首先分析数据片的类型，如果该数据片是片头，片头中保存了数据传输 的源地址和目的地址，根据源地址和目的地址选择一条合适的数据传输通道，如 果此时有别的数据包在使用该输出通道，则片头进入到节点缓冲区中的等待队列， 后续的数据暂时不要读出，直到该输出通道可用；如果可用，则建立通路，进行 1 4 武汉理工大学硕士学位论文 后续的数据传输，在这个过程中，该数据包始终占有该通道，别的数据包无法使 用该通道，直