（计算机软件与理论专业论文）片上网络路由算法和映射算法研究.pdf

摘要 摘要 片上网络（noc）已经成为微电子和通讯方面的热点研究，它的主要思想是 将互联网络上的技术引入到片上网络中来。随着片上系统（system on chip,soc） 集成度的逐步提高，传统的总线结构的弊端逐渐暴露出来，比如总线带宽、全局 同步等，而片上网络可以有效的解决这些问题。 在片上网络研究的关键技术中，路由算法决定了分组发送的选择路径，对网 络的吞吐、时延、服务质量等将产生很大的影响。映射算法决定每个处理单元在 noc 的位置，根据其优化的目的不同，它将对 noc 系统的功耗、时延、面积、 负载均衡等产生重大的影响。 本文主要针对片上网络的路由算法和映射算法两方面进行了研究，主要的工 作包括如下两个方面： 1. 在研究现有互联网络和片上网络确定性和适应性路由的基础上， 提出了一种确 定性和适应性相结合的路由算法 drm。该算法主要用于解决不规则 2dmesh拓 扑结构中面向规则的拓扑的路由算法无法保证连通性， 而现有算法为了保证连 通性而使用了较多的虚信道的问题。仿真结果表明，drm 路由算法相比 boppana 算法和 virtualnetwork 算法，具有一定的性能优势。 2. 在研究现有片上网络映射算法、 全局优化算法的基础上， 设计了一种结合了任 务分配与任务调度的面向低能耗的多步映射算法。 与传统的映射算法相比， 该 算法将片上网络设计中的任务调度与分配的因素结合到片上网络的映射算法 中来，该映射算法分为三个阶段分别是：任务调度、ip 核映射、数据模块映 射。仿真结果表明，该映射方法可使 noc 系统的功耗得到有效的减少。 关键词：片上网络 路由算法 映射算法 蚁群算法 abstract abstract recently, the technology called network-on-chip(noc) has aroused wide public concern. the reason for noc has been designed is that with the steady growth of integration of system-on-chip(soc), the shortcomings of the traditional bus architecture have been exposed gradually. such as bus bandwidth, global synchronization and so on. so noc has been designed to solve the problem which is caused by development of soc. routing algorithm determines the path by which the packets are sent. the choice of the path will produce a significant impact on network throughput, delay, quality of service and so on. mapping algorithm was decided that each processing unit in the noc position, according to the different purpose of optimizing, it will have a significant impact on noc systems power consumption, delay, area, load balancing, etc. in this paper, routing algorithm and mapping algorithm have been mainly studied. the main work and contribution have been generalized as follows: 1.through the research of internet and nocs deterministic and adaptive routing, drm algorithm which is combined deterministic and adaptive routing algorithm has been designed,which not only ensures connectivity of any couple of communication nodes but also just requires only two virtual channels.furthermore, in the drm routing algorithm, the method have been designed which is used for the choice of path.simulation results show that, drm routing algorithm compares with boppana and virtualnetwork algorithm has certain performance advantages. 2.through the research of existing on-chip network mapping algorithm and global optimization algorithm, a multi-step mapping algorithm for low-power consumption have been designed which is combined with task allocation and task scheduling. compared with the traditional mapping algorithm, the algorithm in this paper takes the factors of task scheduling and allocation into account, mapping algorithm is three steps: task scheduling, ip core mapping, data block mapping.the simulation results show that the mapping method in this paper can effectively reduce noc power consumption . keywords: network-on-chip(noc) routing algorithms mapping algorithms ant colony algorithm 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。 （保密的论文 在解密后遵守此规定） 本学位论文属于保密，在 年解密后适用本授权书 本人签名： 日期 导师签名： 日期 第一章 绪论 1 第一章第一章 绪论绪论 1.1 片上网络的产生背景及原因 1.1.1 片上网络产生的背景 noc1-5片上网络已经成为微电子和通讯行业的热点研究之一，作为未来soc 的实用开发平台，它的产生是soc不断发展的结果，片上系统soc(system on chip) 是20世纪90年代出现的概念。它将计算资源,即多个处理核和可重用的组件集成到 一个芯片上, 它的连接方式采用了总线连接。该连接方式降低了设计的难度,减少 了芯片的面积成本,有利于计算资源的标准化。 随着半导体工艺的不断发展和soc 技术的不断完善,现在的soc 中可包含一 个或多个处理器、存储器、模拟电路、数模混合电路以及片上可编程逻辑等ip核。 根据国际半导体技术路线图预测, 到2010年单个芯片上的晶体管数目将达到22亿 个。如何有效地利用数目众多的晶体管是芯片体系结构必须回答的新问题。倘若 因循单核的发展思路, 芯片设计将面临互连延迟、存储带宽、功耗极限等性能提升 的瓶颈问题。因此, 业内普遍认识到, 有必要研究新型的芯片体系架构以同时适应 性能增长和功耗下降这种看似矛盾的需求，多核技术被看做是一条可行之路。多 核能够用多个低频率核单元产生超过高频率单核的处理效能, 获得较佳的性价比。 围绕着多核的一系列技术问题业已成为近期芯片业研究的重点和未来的主要发展 方向。 图 1.1 noc 网络结构图 按照不同的片上互连方式, 多核可分为两大类： 传统的基于总线的互连和基于 网络的互连。 前者是现有的扩展, 通过多总线及层次化总线等技术使得片上集成更 多的处理器核, 从而实现高复杂度和高性能, 而后者是近些年提出的崭新的概念, 即多处理器核之间采用分组路由的方式进行片内通信, 从而克服了由总线互连所 带来的各种瓶颈问题, 这种片内通信方式称为片上网络。 片上网络路由算法和映射算法研究 2 1.1.2 片上网络产生的原因 noc 是指在单芯片上集成大量的计算机资源以及连接这些资源的片上通信网 络，如图 1.1 所示。 noc 由负责计算的 ip 单元和负责通讯的路由器单元组成， ip 既可以是现有意 义上的 cpu、soc，也可以是各种专用功能的 ip 核或存储器阵列、可重构硬件等； 路由器单元负责连接 ip 单元，实现计算资源之间的高速通信。通信节点及其间的 互连线所构成的网络被称为片上通信网络 （on-chip network, noc） ,它借鉴了分布 式计算系统的通信方式，用路由和分组交换技术替代传统的片上总线来完成通信 任务。noc 的核心思想是将计算机网络技术移植到芯片设计中来。noc 产生的动 因即为其与 soc 相比所具备的优势 7，这些优势大致可概括为如下几个方面： 1)有效缩短设计“剪刀差” 。 集成电路设计效率的增长率总是滞后于芯片集成度的增长率，造成了芯片集 成度和设计效率之间著名的“剪刀差 6”，并且他们之间的差距还在继续增大，如 图1.2所示。重用设计方法学是缩短“剪刀差”的有效途径，各个层次的电路功能 模块的重用有效地弥补了设计效率的差距。但是随着电路规模成指数增长，现有 重用单元的电路规模依然不够大，缩短“剪刀差”仍然是个问题。集成电路设计 方法学的发展史，就是一个不断扩大重用单元规模的过程，前一个阶段的“产品” 将成为下一个阶段的重用单元（晶体管 - 门级电路 - ip 模块 - soc 平台）。 noc 提供了支持高效率可重用设计方法学的体系结构：现有规模的soc 完全可以 作为noc 的资源节点参与重用设计， 其重用效率无疑将大大提高。 不仅如此， noc 通过通讯节点连接资源节点，每个资源节点只要符合片上通讯协议即可，就像因 特网对pc 本身的要求十分宽松一样。在集成多个处理器单元时，以通讯协议为核 心的noc 设计方法所特有的高设计效率将发挥巨大的优势，为缩短剪刀差提供了 一个解决方案。 图 1.2 集成电路设计和芯片集成度的剪刀差 2)有利于提高总线带宽 总线结构是现有芯片架构的通信脉络，随着电路规模的扩大，总线结构将成 第一章 绪论 3 为芯片设计的瓶颈：虽然总线可以有效地连接多个通信方, 但总线地址资源并不 能随着计算单元的增加而无限扩展虽然总线可由多用户共享, 但一条总线无法支 持一对以上的用户同时通信, 即串行访问机制导致了通信的瓶颈。对于当前的内 嵌处理器的发展水平，单个芯片可以很容易的内嵌数百个或数千个处理器。但是 实际中，实现复杂的socs技术远远落后于扩大单硅片容量的技术。图1.3中，红线 表示对于一个给定的硅片技术，每个片可用的门的数量，而蓝线表示对于一个给 定的硅片技术，每个片实际上利用的门的数量。由图1.3可以形象的说明目前的急 需一种新的电子系统级的设计方法使得两个技术的发展可以同步化。 图1.3 芯片复杂性和设计复杂性趋势图 此外, 片上通信是功耗的主要来源, 庞大的时钟网络与总线的功耗将占据芯 片总功耗的绝大部分。noc的网络拓扑结构提供了良好的可扩展性,noc连线网络 提供了良好的并行通信能力, 从而使得通信带宽增加几个数量级。此外,noc将长 的互连线变成交换开关之间互相连接的短连线, 这对功耗控制变得极为有利, 另 一方面：noc借鉴了通信协议中的分层思想, 这就为从物理级到应用级的全面功耗 控制提供了可能。 3)有利于解决全局同步的难题 纳米工艺的飞速发展将使得全局同步问题越来越突出，当使用50nm工艺，时 钟频率为10ghz时，全局线延迟将达6-10个时钟周期，时钟偏斜很难控制，而时钟 树又是影响芯片功耗和成本的一个主要因素。随着时钟频率的逐步提高，这些问 题将变得越来越突出。 而noc的片内网络通信方式， 资源之间的短线互联和天然的 全局异步局部同步（gals）时钟策略是解决这些问题有效途径。 1.2 片上网络系统设计 1.2.1 片上网络的结构特点 片上网络将计算和通信两个行为进行了分离，计算资源由ip核和本地内存组 成，对应应用层上的一个独立的应用，ip核是一个可以重构的硬件单元。计算单 片上网络路由算法和映射算法研究 4 元只受芯片面积和接口条件的限制。资源网络主要包含路由器、信道和资源网络 接口。资源网络接口将资源和网络连接，使资源相对网络透明，实现了异构计算 资源间的方便、灵活的通信。noc结构是一种片上通信基础结构，涉及osi的物理、 数据链路和网络层。资源网络接口的设计，解放了计算资源在通讯服务任务上的 负担；分离了计算资源与网络通讯，使计算资源相对网络透明，从而实现异构资 源间的互联，提高了设计的重用性。资源网络接口易于使用分层的方法实现系统。 在分离高层,易于计算资源的重用;在分离的低层使得网络资源的重用得到优化, 提高了实际设计效率。 1.2.2 片上网络设计流程 noc系统设计 8分为计算资源结构设计和noc结构的设计。 计算资源结构设计描 述了应用系统的行为，系统的功能是由计算资源单元来实现的。noc结构的设计流 程简述如下: 1) 通信的模型化和分析。 分析所有计算资源之间数据信息传输的特点,抽取传 输信息的数量,信息单元的尺寸,通信的类型和速率。结合实际应用的领域量化和 抽象化通讯模型。 2）拓扑结构与协议设计。在建立的通信模型基础上设计拓扑结构和协议, 目 标是保证网络的健壮性和扩展性，与此同时尽量降低网路的复杂度等，这一步是 noc 设计核心。 3)版图规划评估。在noc中不是逻辑电路,而是互连结构主要影响着系统的功 耗和面积。芯片的版图规划的评估是通过评估时钟周期上每个互连的延迟以及分 析功耗、面积,为互连获得设计要求。 4)系统性能分析。在仿真平台上(例如opnet),通过对计算资源结构的通信跟 踪,仿真noc结构。仿真结果可用于对不同设计的选择和完善系统的设计。如果设 计不能满足性能要求或仅有太小的性能改善,必须返回前2步重新进行设计。 5)noc逻辑与电路设计。逻辑电路的行为由拓扑和协议的设计定义,通过硬件 语言描述,并且综合。 6)功耗、面积分析。累加每一个活动的功耗,可计算出noc的最大功耗;累加每 一个设计部分,得到总的硅和金属使用的面积。如果功耗和面积不能满足要求,必 须返回选择不同的电路设计或重新进行版图规划, 最坏情况下需重新进行拓扑结 构和协议的设计。 第一章 绪论 5 1.3 片上网络研究的发展现状及趋势 1.3.1 片上网络的发展现状 noc 的目前的主要研究方向为：1）基于 noc 通信单元中的路由器结构的研 究，该方面研究主要是通过对路由器中的缓存和开关结构等具体技术细节进行讨 论，已保证 noc 的具体需要，比如功耗、面积等；2）基于 noc 的拓扑结构的研 究，比如 2dmesh、spin、2d torus、folded torus 等；3）基于 noc 的映射算法的 研究，映射算法是一种决定实际 ip 核在给定拓扑中位置的映射方案的算法；4）基 于 noc 的交换机制的研究；5）基于 noc 的路由算法研究，路由算法根据其性能 所体现的侧重的不同又分为，面向服务质量 qos 的路由算法，面向容错的路由算 法等等。 1.3.2 片上网络的发展趋势 1）层次化多核发展方向 微软公司2007年月在美国西雅图召开了第一个以众核为主题的研讨会, 标志 着众核设计已经成为技术发展的趋势和学术研究的热点。集成电路设计总是想方 设法把现有的各种电子电路乃至计算系统集成到单一芯片上, 因此计算机体系结 构历来是集成电路片上系统架构的参考体系。超级计算机是最强大的计算机, 充 分参考超级计算机的体系结构是设计多核处理器的基本思路。超级计算机体系架 构的基本特征就是小核大阵列和层处理器。超级计算机告诉我们, 小核大阵列和 层次化管理必将成为众核处理器的主流技术发展方向。 2）noc 拓扑结构三维化 rtrs2007年版阐述了moremoore（延伸摩尔定律）和more than moore(超越摩 尔定律)两个概念，其中延伸摩尔定律是按照等比例缩小继续走微细化的道路, 而 超越摩尔定律追求的是功能多样化, 并指出下一代soc(noc)与sip技术融合的发 展趋势。正如itrs 预测，在工艺技术发展和设计技术需求的双重驱动下, 三维集 成又称为系统级封装, sip技术愈来愈受到学术界和工业界的关注和重视，noc虽 然克服了全局延迟过长带来的信号完整性及全局同步等一系列问题, 但并没有在 根本上解决缩短物理连线, 减小信号时延的问题。由于二维noc布局条件的限制, 难以保证关键部件相邻以缩短关键路径长度, 而三维集成技术可以把不同的器件 层堆叠起来, 不仅在真正意义上缩短了连线的长度, 并克服这种布局的限制。因 此把noc和三维集成这两种设计技术融合起来的三维noc自然受到很大的关注。目 前从事该领域研究的学术机构包括美国斯坦福大学、加州理工大学、宾州州立大 学、华盛顿州立大学, 瑞典皇家工学院、日本keiouniversity，加拿大的不列颠 片上网络路由算法和映射算法研究 6 哥伦比亚大学，以及intel、toshiba等大公司的研究中心。可见，三维noc已经引 起了国际上学术界和产业界的关注，很可能在未来几年内发展成为一个重要的研 究领域，并得到广泛的关注。 1.3.3 片上网络的研究价值 自 2000 年起，很多研究机构提出了各种各样的创新的片上网络架构，这些研 究机构包括 bologna、kaist、kth、lip-6、mit、ucsd、manchester、stanford、 tampere、technion、飞利浦研究实验室、意法半导体和 vtt 技术研究中心等。一 些芯片厂商（intel, amd, ibm 等）也都致力于这方面的研究，英特尔公司的研究 人员已经采用片上网络架构研究出世界上首个具有与超级计算机性能相似的可编 程处理器，每个芯片内含 80 个内核， 1 亿个晶体管，散发 98 瓦的热量。其尺寸 相当于一个指甲盖大小，耗电量低于当前绝大多数的家用电器。这是英特尔公司 创新性的“万亿级计算”研究项目的成果，该研究项目旨在为未来的个人电脑和 服务器提供万亿级浮点运算性能， 即每秒运算一万亿次。 同时， ibm power4、 power5 就是典型的采用开关网络进行片上通信的片上网络芯片。而最新的 ibm cell 处理 器同样也采用了一种新型的环形网络。因此片上网络是芯片产业发展的趋势，这 类芯片将在今后可以接入互联网的计算机中起到关键性的作用，为教育和协同工 作创造新的应用，推动基于个人电脑、服务器和掌上设备的高分辨率娱乐内容的 创新。坚持开发拥有自主产权的片上网络技术，将使我国在该领域具有强大的竞 争力,从而带动国内 ic 产业往深度,广度方向发展. 因此，加快片上网络技术的研 究将对我国芯片产业的发展起到巨大的推动作用。 1.4 论文内容及结构 本文在绪论说明了 noc 的产生背景、总体设计流程、现阶段研究成果以及未 来的发展方向，接下来的内容安排如下： 第二章为片上网络关键技术研究：从片上网络的拓扑结构、交换机制、映射 算法、路由算法四个关键技术进行了分析，并阐述了现阶段研究所提出的经典的 理论，并分析其优缺点。 第三章针对 noc 中的实际情况，提出了不规则的 2dmesh 的路由算法，并进行 了仿真对比。 第四章针对 noc 中的实际情况，提出了一种面向低功耗的 noc 映射方法，该 方法通过三个阶段进行映射，与其他方法相比，此映射方法结合了任务调度和任 务分配，考虑的因素更加全面化，并进行了仿真。 第五章对全文工作进行总结，并提出了展望。 第二章 片上网络关键技术 7 第二章 片上网络关键技术 2.1 片上网络的拓扑结构 noc的拓扑结构定义了网络内节点与链路的布局和互连方式,拓扑结构的衡量 标准通常是以理论上影响路由成本和性能为基础的, 除了要考虑普通网络中所关 心的节点数量、边的数量、网络维度、网络直径、平均距离、对分宽度之外, 还 要考虑通信模式的嵌入属性,对于网络的时延、吞吐率、面积、容错、功耗等性能 它也有着至关重要的影响,进一步还影响了网络中的路由策略、映射算法等,研究 noc拓扑结构具有重要的意义。 片上网络拓扑结构很大程度上借鉴的计算机互联网的网络结构，noc拓扑包括 规则拓扑与不规则（定制拓扑）两大类，如表格2.1与2.2所示。 表2.1 noc规则拓扑分类 规则拓扑 直接网络 网格 多维环绕 超立方 其他拓扑：线性阵列等 间接网络 树 碟网 其他拓扑 表2.2 noc非规则拓扑分类 非规则（定制） 拓扑 专用网格 基于规则拓扑 分层网络 网络总线混合拓扑 在介绍具体的拓扑结构之前,首先要了解片上网络拓扑结构的主要性能指标 9-10。 2.1.1 拓扑结构主要性能指标 距离和直径：在网络中，任意两结点间沿最短路径通信所经过的边的数目称 为这两个结点间的距离，整个网络距离的平均值为平均距离，记为 d。任意两结点 间距离的最大值称为该网络的直径，记为 d。 度：结点度指与结点相连节的边数（链路或者通道数） ，表示结点所需的 i/o 8 片上网络路由算法和映射算法研究 端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一 步表示为：结点度=入度+出度。其中入度表示进入结点的通道数，出度表示从结 点出来的通道数。网络中个结点度的最大值为网络的度。 网络规模：在直接互连网络中，网络的总结点数和总边数称为网络的规模， 它反映了网络的大小及实现成本，也反映了该网络所能连接的部件的多少。 对分宽度和对分带宽：当网络被切成相等的子网络时，所要移除的最小边数 称为网络的对分宽度（设为b表示） 。令每一信道的带宽都为w，则对分带宽为 wbb 。对分带宽是衡量一个网络吞吐量的一个重要参数。 规则性与对称性：规则性是指网络结点连接所遵循确定的规则。在一个规则 网络中，各结点连接的相邻结点数是相等的。任意两个结点间的通信的路径算法 比较规则和简单。规则性还可以用对称性来描述。在全对称性网络中，每个结点 在途中的地位是等同的；局部对称性网络中只有部分结点在集合位置上和其余部 分结点对称。 路径多样性：是指网络中任意两点之间都具有多条等价的不相交的路径，一 个具有路径多样性的网络可以提供容错能力和负载均衡能力 连通性：它指的是当网络被分为两个不连通的网络时，所需去除的最小的边 的数量。该参数用来衡量网络发生故障时网络的抗毁性（resilience） 。 成本：一般由边的数量决定。 可扩展性及平面性：可扩展性是指网络拓扑性能保持不变的情况下，扩充结 点的能力；平面性是指网络拓扑在平面上能否实现。这两个参数直接关系到直接 互连网络实现的经济性和适应性，是设计时必须要考虑的问题。 2.1.2 片上网络的拓扑结构 1）规则拓扑 规则拓扑主要来自于并行计算机互连网络,可分为两大类:直接网络,网络内 任一交换节点,都与ip核直接相连。间接网络,网络内一部分交换节点只与其他交 换节点相连。 流行的直接网络包括有二维网格 11(2dmesh) ,二维环绕12(2dtorus)和超立方, 而k元n立方体则是这三种网络的通用形式。其他的直接网络还包括一维线性阵列、 环网、全连接、星形网等。 a)二维网格 在一个n*n的二维网格中，除边界外，每个节点与其上、下、左、右的近邻相 连。因此节点度为4，网络直径为2*（n-1）。二维网格由于其结构简单、可扩展 性好、便于实现和分析等优点，在noc领域得到了广泛的应用。例如nostum, 第二章 片上网络关键技术 9 aethereal,socn,socbus,hemes等。如图2.1所示。 图2.1二维网格的拓扑结构 图2.2二维环绕的拓扑结构 b)二维环绕 二维环绕也称 2dtorus，w.j.dally 和 b.towles 提出了 2dtorus 结构，这种结 构是基于直连网络中的 torus 结构提出的，该节点与其水平和垂直方向的对称节点 连接，形成了一个二维环绕，该结构的节点度仍然为 4，直径为 n/2(取整)。相比 二维网格直径有所减小，但是种过长的环形信道可能会产生额外的延迟。该结构 如图 2.2 所示。folded torus 13结构弥补了这一缺陷，如图 2.4 所示。该结构通 过改变交换结点地连接方式,如图 2.3 所示，从而解决了由于过长的环形信道产生 额外的延迟，提高了系统的整体性能。 0321 0321 图 2.3 不同连接方式比较 图 2.4folded torus 拓扑结构 c）超立方 超立方（hypercube）原本是几何学中的概念，并不是专为片上网络而提出的 新型拓扑结构。它可以是任意n维的（n是非负整数），并且有2n个顶点，一个顶 点连接n条边，所有的边在顶点处都以直角互相连接。 在silicon graphics公司商用的ccnuma (cache coherent non-uniform memory access)技术 20中运用了超立方拓扑结构，和簇结构相似，其中一个路由器连接4 个cpu。 图 2.5 展示了超立方 18从 0 维到 4 维的结构，当然，超立方结构还可以扩展到 更高维。虽然我们不能用 3 维的视角很好的理解具有 4 维或更高维空间的拓扑结 构，但掌握了它们的连接规则以后，我们可以构建一个系统来实现与之相同的端 到端连接关系。 10 片上网络路由算法和映射算法研究 （a）0 维 （b）1 维 （c）2 维 （d）3 维 （e）4 维 图 2.5 各维超立方网络拓扑结构 表 2.3 对上图中 04 维超立方结构的个别属性进行了简单的总结： 表2.3 超立方的部分性质 空间维数 顶点数 （路由器数目） cpu数 边数 0维 1 4 0 1维 2 8 1 2维 4 16 4 3维 8 32 12 4维 16 64 32 间接网络主要包括树、簇的拓扑结构、benes网、clos网等,其中比较常见的 是树、碟网和簇的拓扑结构。 d）树和蝶网 树中的内节点是交换机，叶子是ip核。除了根节点，每个内节点只与其父节 点和若干个子节点相连。对于包含n=2 n个叶子的二叉树，其节点度数为3，网络直 径是2n-2,网络的延迟取决于树的深度，即节点数的对数。 传统 k 叉树的主要问题是单个父节点尤其是根节点，容易成为通信瓶颈。 gft 11-16是对所有 fat-tree 结构的一种总结和归纳。资源被放置在叶子节点处，其 余非叶子节点均为交换节点。gft 的数学表述为( ,)gft h m w，具有 h m个资源， 其中 h 与层数相关，实际的树有 h+1 层；m 表示每个非叶子节点的孩子节点个数； w 代表每个非根节点的父节点个数。图 2.6 示意了(2,2,3)gft。 和树一样，碟网也是一种对树型的网络。对给定的2*2交叉开关，线对中各引 出一根线简单的交叉就获得了蝶网的基本构造块。n维的蝶网包括n=2 n个ip核和 n*2 n-1个度数为2的交换机节点，交换机组织成n层，每层有n/2个交换机。 e）簇型拓扑结构 第二章 片上网络关键技术 11 saneei 等人提出了基于簇的拓扑结构 17cluster mesh，如图 2.7 所示。该结 构中一个交换结点连接 4 个 ip 核改变了传统结构一个交换结点连接一个 ip 核的 方式，进一步减少 ip 核之间的通信距离，有利于本地业务，降低路由查找的时间 和复杂度。基于此思想，有一批相似的拓扑结构涌现出来，如图 2.9 中的 cluster octagon 19， 图 2.8 中的 cluster torus 等。 这类拓扑结构增强了系统的本地特性， 提高了系统的性能。 (2,0) (0,0) (1,0) (2,8) (1,5) (0,3) 图 2.6 (2,2,3)gft的拓扑结构 图 2.7 基于簇的拓扑结构 sss s sss ss s s s s s s s s 图 2.8 cluster torus 拓扑结构 图 2.9 cluster octagon 拓扑结构 2）非规则拓扑 规则拓扑具有规则的网络参数,具有可复用性,降低了设计时间和成本,适用 于通用的对称、同构系统。与规则拓扑不同,非规则拓扑可以面向不同的领域，根 据特定的应用需求定制。根据定制方式的不同,非规则拓扑主要分为以下四类: a)专用网络 专用网络是指网络的拓扑从零开始设计,完全根据具体的应用需求生成,没有 遵循一定的规律。指出在相同的性能指标下,专用网络减少了交换机的使用数目, 在功耗和面积上更有优势。 b)基于规则拓扑 这类网络,指在规则网络拓扑的基础上做一些改变,如在规则拓扑的局部增加 或删除一些节点或链路,从而使定制后的网络失去了规则性。对现实生活中大量网 络的研究表明,许多网络拓扑既不是完全规则的,也不是完全随机的。这些网络介 于两者之间,被称为“小世界”网络。规则拓扑如二维网格具有较大的网络直径, 12 片上网络路由算法和映射算法研究 同时缺乏对簇的有效支持。另一方面,完全定制的专用网络,结构一般比较复杂,没 有规律可言。比如通过在二维网格中插入一些连接远距离节点的链路,使noc的静 态属性(网络直径)和动态属性(链路利用率等)都得到了显著改善。 3)分层网络 在分层网络中,网络的拓扑呈现为两层或多层的层次化结构,一般包括全局网 和局部网两个层次,分别可以根据需要选用规则拓扑或非规则拓扑。比如全局网采 用二维网格,局部互连采用二叉树。 4)网络- 总线混合拓扑 该拓扑结构其实也是一种层次化结构的noc拓扑,全局网采用规则或非规则的 网络拓扑,而在局部网中采用总线。混合拓扑综合了共享介质总线和互连网络的机 制,与总线相比增加了带宽,与规则或非规则网络相比又降低了节点间距离。 2.2 常见交换机制 交换机制 21 定义了数据在片上网络路由器中传递的方式，并规定了沿输出端 口将数据发送出去的时机，其中也包含了所传输数据的形式。目前片上网络中常 见的交换机制基本是借鉴因特网及并行计算机互连网络中的现有技术，主要包括 电路交换、分组交换、切通交换、改进虫孔交换等。还有一些人提出了比较有特 点的交换方式，如管道式电路交换，以及将虫孔交换与虚切通交换相结合的交换 方式 34等各种交换方式。 2.2.1 电路交换 电路交换是早期采用的一种交换方式。最早产生于公共交换电话网( pstn) , 是一种面向连接的交换机制。电路交换建立连接的过程如下： 1）通过一个信息头按照一定的路由规则选取连通路径。 2）建立连接，与此同时预定所经过路径的信道资源。 3）收端在成功收到这个信息头后沿确定路径返回应答。 4）发送端接到这个应答后传送数据开始。 电路交换中，每次传输数据前都要在源结点与目的结点之间建立一条专用的 通信线路。一旦进入数据传输阶段，消息就不会阻塞。通讯结束后，发端向收端 发出终止通信的要求，并沿路拆链，释放对各段链路的使用权。 采用面向连接的方式可以保证片上网络一些特定业务的服务质量。在多媒体 业务中, 消息一般数量较少, 但消息较长, 所以采用电路交换方式较有优势。因 为当消息较长时, 数据部分的传输时间远大于路径建立的时间, 并且由于独占整 个物理带宽, 因此可以保证高吞吐和低时延。与此同时，其可靠性高，几乎没有 第二章 片上网络关键技术 13 抖动，能够很好的保证服务质量（quality of service） 。目前已经提出的片上网络模 型, 如aethereal, nostrum和mango等都用到了这种面向连接的思想来提供有 保障的服务。采用电路交换的另一个好处是不需要在路由节点中添加缓存资源, 这可以在很大程度上减小面积。目前的soc有大量的配线（wiring）资源，可以提 供满足不同带宽的数据流；而且电路交换中可以做到数据信息和控制信息分离， 从而使异步通信技术易于实现；除此以外，数据包中的控制信息较少，因此可以 节省能耗，增大吞吐。由于数据流在物理信道是单独分开的，所以在交叉开关 （crossbar）中不会产生冲突，结点交换结构（switch architecture）的复杂度低。传 统电路交换的一个缺点是一条链路只能被一个预留通道的应用所使用, 而采用时 分复用的虚电路方式可以很好的解决这个问题。这种面向连接的交换机制采用异 步通信, 很好的解决了片上同步问题。然而对于尽力而为的业务而言, 这种面向 连接的电路交换并不适用, 因为尽力业务中的消息较短, 且通信较频繁, 建立路 径的时间开销将不可容忍, 同时也会消耗过多的能量。 2.2.2 分组交换 分组交换是片上网络中最早使用的一种交换机制，第一步，先将消息分成若 干个固定长度的数据段，再在每个数据段前面加上几个字节的消息头，就构成了 一个分组，消息头中通常包含源节点地址、目的节点地址等路由信息和其它的相 关控制信息。分组交换中，消息以分组为单位在网络中传输，每个分组可以完成 从源结点到目的结点独立路由，绕开各种故障或者拥塞区域等。中间结点在接受 到分组后，分组在向下一个特节点转发之前完全缓冲在每个中间节点中。如果当 前结点不是该分组的目的结点，则按照所查的路由表将分组转发出去，否则分组 被提交到网络的高层处理，完成存储与转发的整个过程。 在消息较短且发送频繁的情况下，分组交换较有优势，这正好符合了片上网 络通信业务的特点。但是，将分组完全存储在中间节点需要在路由器的结构中设 置至少一个分组大小的缓冲器来存放整个分组，而这将增大路由器的面积，文献 中指出缓冲器在片上网络路由器中占的面积最大，所以分组交换的这个特点对于 片上网络来说将是致命的缺陷。在有些具体应用中，也有某些结构将需要转发的 一个或多个分组存储在本地存储器中，再通过一个专用的消息协处理器来处理消 息，即负责计算输出通道的地址和转发消息等，将这种沿用局域网和广域网的实 现方法运用到片上网络当中时，路由器与存储设备之间的链路必然会成为整个系 统的瓶颈。同时，有人提出在路由器中设置为所有输入通道所共享的中央队列来 减少对缓冲设备容量的要求，但这种方法使得中央队列的管理与资源的分配变得 相当复杂，会增大路由器内部的延时。 14 片上网络路由算法和映射算法研究 2.2.4 切通交换 切通交换是分组交换机制的一种改进。切通交换又分为虚切通（virtual cut-through, vct）交换 22和虫孔交换(wormhole switching)23-24。 在虚切通交换中，分组交换中的头微片在到达中间节点后就可以立刻进行路 由无需等到整个分组全部被中间节点接收。如果所选择的输出路径是空闲的，就 开始传输分组头后的数据部分。事实上，在当前路由器接收完整个分组之前，消 息甚至不需要进行缓冲，可以直接跨接到下一个路由器的输入上，它的消息流控 单位是分组。一旦当头片受阻时，整个分组将保存在该节点中，也就是说路由器 中必须提供数量至少为一个分组大小的缓冲器，即利用虚切通技术的路由器中的 缓冲器资源数量应该与应用分组交换技术的路由器中的缓冲器数量相等。因此在 网络负荷很重，分组被阻塞的现象频繁发生时，虚切通交换就和分组交换一样了。 在受阻后，虚切通交换允许后续数据片继续前进到头片受阻的结点，并释放它们 所占的资源，减少了进一步阻塞的可能。文献 23仿真了虚切通交换机制和虫孔交 换机制在各种条件下的性能。结果表明，两者的能耗相近，但是虚切通取得了较 好的时延性能。而虚切通要求的缓存较大，会增加芯片的面积。 为了克服缓冲器过大，造成芯片面积过大的缺点，虫孔交换机制被提出了。 该交换机制是受虫子，蚯蚓等蠕形动物的前行过程启发而设计的一种相对智能型 的交换机制。蚯蚓等动物的身体分为很多结状部分，在前行过程中，头部首先向 前探路，而身体的其它结状部分随着身体的前行，慢慢前行，直至到达目的地。 在虫孔交换机制的设计时，设计了很小的缓冲器，它首先将整个分组分割为更小 的片（flit） 。这些片可分为头片(head flit)与数据片(data flit)。头片含有路由信息， 可进行路径的选择，数据片不具有选路功能。整个分组的路由是由头片带路，数 据片紧跟头片向目的结点移动来实现的。而该交换机制特别设计时强调每个信道 只有一个片大小的缓存。该交换机制下的传输时延可粗略计算为：/ wr tdl w, 其中d为源目的结点间的跳数，l为消息长度，w为信道带宽。 由上式可以看出，当/l w远大于d时，时延对距离不敏感，因此适合于大规 模网络结构的应用。正是由于这个优点，虫孔交换机制被广泛应用于当前的商用 并行计算机，太比特路由器等中。这种交换机制需要的缓存资源少，每个结点的 缓存只有一个片的大小，有利于缩小芯片面积。虫孔交换时延对跳数不敏感，当 网路规模增大时，时延增加不明显。因此虫孔交换成为当前片上网络中使用最广 泛的交换机制，但是它也存在自身的一些缺陷。由于每一个缓存大小为 1 个片， 当输出信道繁忙而导致头片受阻，后面数据片也无法路由，容易造成死锁和网络 拥塞； 文献 24提出一种改进的虫孔交换来提高网络的吞吐量，通过在头片和数据 片设置不同的时钟，使数据片到达任何一个结点后不需要查找端口，因此可以减 第二章 片上网络关键技术 15 少数据片在结点的等待时间，从而减少死锁发生的可能性或者降低拥塞程度，而 保持头片的路由决策时间不变。但是，它也存在自身克服的缺点，当头微片在中 间结点受阻时，其后续的数据微片由于没有足够的缓冲器空间则只能滞留而不能 向前。并且由于分组可能包含很多微片，因此很容易发生一个分组同时跨接多个 路由器的情况，使得多个中间路由器的资源被占用而得不到释放，缓冲器间的相 关性扩展到了多个路由器，很可能造成网络的拥塞甚至死锁。 2.2.5 改进的虫孔 为了弥补传统的虫孔交换由于路由决策时间过长而导致的性能下降，产生了 改进虫孔 25交换方式。传统的虫孔交换在传输头微片和数据微片时使用相同的时 钟周期，但在改进型的虫孔交换中，在传输数据期间将使用更短的时钟周期，以 提高时延性能。 在改进的虫孔交换中，数据微片不需要计算路由信息而只是跟随前面的微片 向前转发，即在路由器结构中数据微片通过输入缓冲器后直接连接到输出缓冲器， 而不需要中间的路由决策单元进行判决，又因为在自适应路由器中缓冲器的存取 速度通常比路由决策单元的处理速度快很多，所以在头微片和数据微片的传输期 间使用不同的时钟的方法有利于进一步提高时延性能，并且压缩数据微片在时域 上的有效长度，从而缓解了竞争。 2.2.6 管道式电路交换 管道式电路交换综合了电路交换与虫孔交换的特点。它将分组进行分割成片， 并像虫孔交换一样，用头片来探测路径。头片在探测路径以及受阻释放路径的过 程，是运用电路交换机制的方法进行的。比较特殊的是，管道式电路交换机制下， 在头片到达目的地发挥反馈之前，源结点中的数据片和尾片都不得发送。这样相 当于为每个分组建立了端到端连接，从而确保时延上界，而且在头片探路过程中， 绕开了故障区域，后续分组可以在存在故障区域的情况下到达目的地。因而该交 换机制具有一定的容错性。同时也保证了数据的可靠传输，比较适用于传输质量 要求高的业务。当然，该交换机制也具有一定的缺陷性，如建立连接开销过大， 很容易造成网络饱和，吞吐能力差等。 2.2.6 各种机制对比分析 电路交换先由路由头建立链路，成功后，消息将沿着该链路传输。电路交换 的数据传输速度快，可靠性高，能够很好的保证服务质量。但是从建链开始到拆 链结束的过程中都要占用物理信道，不适合在通信业务频繁且数据量不大的片上 16 片上网络路由算法和映射算法研究 网络中使用，链路利用率较低。分组交换的转发方式是先将分组完全缓冲在每个 中间节点中，然后再向下一节点转发。此种方法在消息较短且发送频繁的情况下 较有优势，链路利用率比电路交换高，能够在一定程度上缓解阻塞。它最大的缺 点是需要在每个路由器中设置较大容量的缓冲器，导致芯片面积过大，因此不适 合在片上网络中使用。同时分组时延与距离成正比，不能适应网络规模扩大的发 展趋势。虚切通，接收完头微片并且路由信息决定的输出链路空闲时，不等整个 分组接收完就将消息跨接到下一节