三维片上网络功耗评估及映射算法.pdf

代号代号 分 类 号分 类 号 学号学号 密级密级 1070110701 TN4TN4 公开公开 1017121017122 2003003 题题（中、英文）（中、英文）目目 三维片上网络功耗评估及映射算法三维片上网络功耗评估及映射算法 Power evaluation of 3D NoCPower evaluation of 3D NoC and mappingand mapping algorithmalgorithm 作 者 姓 名作 者 姓 名 魏洁魏洁 蔡觉平蔡觉平 教授教授 工学工学 提交论文日期提交论文日期 二一三二一三年一月年一月 微电子学与固体电子学微电子学与固体电子学 指导教师姓名指导教师姓名、职称职称 学 科 门 类学 科 门 类 学科、专业学科、专业 西安电子科技大学 独创性(或创新性)声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。申请学位论文与资料若有不实之处，本人承担一切相关责任。本人签名：日期 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。(保密的论文在解密后遵守此规定)本学位论文属于保密在 年解密后适用本授权书。本人签名：日期 导师签名：日期 摘要 摘要 采用 TSV 作为垂直互联的三维片上网络结构结合了三维电路和片上网络两者的优势，能获得更高的带宽、更低的延时和更高的吞吐量。但三维片上网络的高集成度也给芯片温度管理问题提出了更高的要求，而该问题的基础是低功耗问题的研究。所以本文以片上网络的互联功耗为研究对象。本文首先建立了三维片上网络的互联功耗模型。互联包括路由和链路两部分，而链路又分为水平链路和垂直链路 TSV 两类。每一部分的功耗都分为动态功耗和静态功耗两部分，分别进行讨论。接着，本文阐述了片上网络的映射问题，并介绍了三种映射优化算法。文章最后评估了二维片上网络结构、一层 Cache 和两层Cache 的三维片上网络结构在不同注入率下的互联功耗，讨论了不同端口的路由和针对不同包格式的片上网络结构在功耗方面的优劣，并比较了遗传算法、分支界限算法和模拟退火算法三种映射算法的优化结果。仿真结果明确了三维片上网络结构相较于二维结构在功耗方面的优势，在包格式为 16bits*16flits 的情况下，一层 Cache 和两层 Cache 的三维结构与二维结构相比，功耗分别降低了 12%和 22%。采用包交换策略时，包格式和路由结构的选择都会对片上网络的功耗有显著影响。映射算法的仿真结果表明，不同的映射算法对功耗有不同程度的优化。模拟退火算法与遗传算法和分支界限算法相比，优化效果更明显，功耗降低的比例高 12%。关键词：三维片上网络 TSV 功耗建模 映射算法 三维片上网络功耗评估及映射算法 Abstract Abstract 3D NoCs can achieve high bandwidth,low latency and large throughput，which combine the benefit of through silicon vias and 3D ICs.Due to high packaging density of 3D NoCs,temperature management becomes a crucial problem,therefore,the research objects of this paper are interconnect power and cache power.This thesis focuses on establishing detailed power consumption models of interconnection and cache in 3D NoCs.The interconnected components include router and links which can further be separated into horizontal links and vertical links.The power of each component is divided into dynamic power and static power.Then,Genetic Algorithm,Branch-bounds Algorithm and Simulated-annealing Algorithm are introduced to solve mapping problem of NoCs.Finally,the energy performances of 2D NoC,3D NoC with one cache layer and two cache layers under different injections are compared.Additionally,the energy performance of 3D NoC structures with different kinds of routers and different packet formats are explored.And the results of three optimization algorithms are also analyzed.The simulation results indicate that 12%and 22%power consumption can be respectively reduced by adopting two kinds of 3D Mesh NoC,and other factors,such as router parameters and packet formats,have a great effect on power consumption.The simulation also indicates that SA algorithm can achieve better power performance compared to GA algorithm and Branch-bounds algorithm,the ratio of which is 12%higher.Keywords:3D NoC TSV Power model Mapping algorithm 三维片上网络功耗评估及映射算法 目录 目录 第一章 绪论.1 1.1 研究背景.1 1.1.1 三维片上网络的兴起.1 1.1.2 NoC 功耗研究.1 1.2 国内外研究现状.2 1.3 研究目标及成果.4 1.4 本文的结构安排.4 第二章 3D NoC 基本概念及仿真平台介绍.7 2.1 3D NoC 相关概念.7 2.1.1 拓扑结构.7 2.1.2 路由算法.8 2.1.3 交换机制.9 2.1.4 TSV 结构及工艺.10 2.1.5 Cache 的基本概念.11 2.1.6 功耗的基本知识.13 2.2 仿真平台.14 2.2.1 片上网络互联仿真器 ORION2.0.15 2.2.2 Cache 仿真器 CACTI5.3.16 2.2.3 多内核互联仿真平台 OPNEC-SIM.16 第三章 3D NoC 功耗建模.19 3.1 路由模块的功耗建模.19 3.1.1 缓存模块的功耗.19 3.1.2 仲裁器的功耗.21 3.1.3 Crossbar 的功耗.22 3.2 链路的功耗.24 3.2.1 水平链路的功耗.24 3.2.2 垂直链路(TSV)的功耗.26 3.3 Cache 的功耗.28 第四章 片上网络的映射算法.31 4.1 NoC 映射问题的描述.31 4.2 任务图的表示.33 4.3 映射算法介绍.34 2 三维片上网络功耗评估及映射算法 4.3.1 遗传算法.34 4.3.2 分支限界算法.35 4.3.3 模拟退火算法.36 第五章 仿真介绍与结果分析.39 5.1 3D NoC 与 2D NoC 的功耗对比.39 5.2 不同包格式对 NoC 功耗的影响.48 5.3 三维 NoC 结构的讨论.51 5.4 三种映射优化算法.53 第六章 总结.55 致谢.57 参考文献.59 作者在读期间研究成果.63 第一章 绪论 1 第一章 绪论 1.1 研究背景 1.1.1 三维片上网络的兴起 目前，单核因面临功耗和速度瓶颈，业界已转向多核架构。片上多核芯片按照互联方式大致可分为两类：基于总线(Bus)互联的 SOC 和片上网络(Network on Chip,NoC)。随着工艺的发展，总线结构的三大问题越来越突出。第一，有限的地址空间无法支持两对以上的用户同时通信；第二，总线结构存在扩展性较差的问题；第三，单一时钟实现全局同步非常困难。因为随着深亚微米工艺时代的到来，芯片的特征尺寸日趋减小，而总线结构的工作频率却迅速提高，且要求全局同步，所以总线结构的连线延时越来越显著，以至于无法设计全局时钟树。另外，庞大的时钟树的功耗将成为芯片总功耗的主要组成部分。因此系统采用单一时钟同步全芯片无法适应未来技术的发展。1999 年提出的 NoC 结构，由于其良好的并行通信能力和可扩展能力、全局异步局部同步(Globally Asynchronous Locally Synchronous，GALS)的时钟策略等优势，已经成为集成电路产业界研究的热点之一。目前，已经提出了大量的二维 NoC结构，如规整的二维 Mesh 结构，Torus、Fat Tree 以及层次化的拓扑结构等等。研究内容覆盖了片上网络的拓扑结构、路由器微结构、仿真系统、功耗及性能评估、优化算法以及容错机制等诸多方面。近年来，“穿透硅通道(Through-Silicon Vias)”TSV 技术的出现使集成电路技术走向三维结构(three dimension，3D)，3D NoC逐渐成为新的研究热点。与传统的二维 NoC 相比，3D NoC 主要有五大优势，具体表现在：(1)有效缩短了全局互联线的长度；(2)由于缩短了互联线的长度而降低了功耗；(3)降低了延迟，提高了系统性能；(4)增加了封装密度，减小了芯片面积；(5)有利于实现不同工艺的混合集成1。1.1.2 NoC 功耗研究 IP核的增多和通信量的提升使互联网络的功耗大大增加，同时考虑到电池的使用时间和热预算，功耗问题已成为了NoC设计的焦点。现在已流片成功的NoC芯片的研究结果表明，互联功耗是整个系统功耗的重要组成部分，如MIT的RAW多核处理器，互联部分的功耗占整个系统功耗的36%；Intel 80核的Teraflop芯片中，互联功耗约占30%2。国际半导体技术线路图(ITRS)预测下一代高端超大规模集成电路工作频率将高达10-20GHz，各个核之间的数据传输速率在Gbit/s的数量级3，这2 三维片上网络功耗评估及映射算法 使得IC设计人员将面临更为紧张的功耗预算。因此，NoC低功耗设计的重要性尤其突出。NoC 低功耗研究主要有四个方面：功耗评估，片上网络互联功耗优化，处理器核功耗优化和片上存储功耗优化，其中功耗评估是片上网络低功耗设计的基础。在设计初期，为了验证功耗预算是否满足设计方案的整体及各个组件的设计要求，以及评估各种高级别功耗优化方法的效率，提出了许多体系结构级的功耗模型来实现快速的功耗评估。本论文的研究是基于片上网络的互联仿真器 ORION2.0 建立的功耗模型，在此基础上改进了水平链路的功耗模型，并引入了 TSV 的功耗模型，建立了比较完善的三维片上网络的互联功耗模型。除此之外，本文还采用 Cache功耗仿真器 CACTI5.3 评估了 Cache 的功耗。在功耗评估的基础上，又引入了模拟退火算法、遗传算法和分支界限算法来实现三维片上网络的 IP 核的映射，实现了功耗的高层次优化。1.2 国内外研究现状 2000 年，Guerrier 等人首次提出了片上多核结构的概念，该多核系统基于Fat-Tree 拓扑结构。他们提出了一种片上多核互联结构 SPIN，并建立了周期精确的路由模块的性能模型4。2003 年，美德州大学的奥斯汀分校的一个小组设计出片上网络多核芯片 TRIPS。TRIPS 芯片采用基于虫孔交换技术的 4*10 的二维Mesh 结构5。同年麻省理工学院实现了 16 核的 RAW 处理器，该可重构处理器由 16 个负责处理各种运算的处理核心 Tile 单元和可编程的片上互联网络构成6。在 ISSCC2007 上，Intel 展示了一款基于 65nm 工艺的 80-core 的 Teraflop 处理器，其每个 Tile 单元除了包含计算单元外还包括一个 5 端口路由。各个 Tile 单元之间通过 10*8 的 2D Mesh 网络实现通信，最高工作频率高达 5.67GHz7。Tilera 公司也于 2007 年推出了基于 2D Mesh NoC 的 64 核处理器。该芯片的不同版本的运行速率从 600MHz 到 1GHz，平均功耗为 17-30W。另外，该芯片还集成了两个 PCI Express、四个 DDR2 内存控制器和两个以太网接口，其结构如图 1.1 所示8。Tilera公司于 2010 年推出了同系列的 100 核的版本。对于二维 NoC 功耗方面的研究，首先是 T.T.Ye 等人提出的数据传输的位能量模型。该模型分析计算了每位(bit)数据经由片上网络消耗的能量9。J.Hu 等人在此基础上进行改进，提出了适合 2D Mesh 结构的功耗模型10。N.Eisley 根据链路利用率建立了功耗模型，从电路结构和网络实时性能两方面分析了互联网络的功耗，具有更高的准确度11。在面向功耗优化的映射算法方面，L.lin Zhong 等人提出了功耗感知的模拟退火映射算法，从算法和系统的角度实现了多核任务分配和执行的低功耗问题12，Yanhua Liu 等人实现了基于蚁群算法的片上多核任务分配和映 第一章 绪论 3 射，显著降低了系统功耗13。图 1.1 Tile 公司提出的 64 核处理器结构图 2007 年 4 月，IBM 实验室公布一项突破性的研究成果，即芯片堆叠技术14。从此，三维集成电路成为新的研究热点。2010 年 10 月，三星公司采用 3D-TSV 技术，在 40 纳米工艺实现的 2GB DDR3 DRAM 上搭载了 2 颗集成芯片，制成了 8GB DDR3 RDIMM(Registered Dual Inline Memory)产品。三星计划使用 30nm 工艺生产基于 TSV 技术的内存，以实现更高的性能和更低的功耗。目前，学术界针对 TSV的研究主要集中在建立电学参数模型、研究制造工艺、热效应分析和多 TSV 束的耦合分析等方面15。如 IMEC 的研究人员通过解极坐标下的泊松方程提取了孤立TSV 的 RLC 参数，仿真结果表明误差很小15；Lionel Cadix 等人根据 Response Surface Methodology 方法，提取了 TSV 的 RF 电学参数16；Roshan Weerasekera 建立了完整的TSV电学模型并且考虑了多TSV耦合的情况17；Dae Hyun Kim对TSV之间的耦合进行了研究，计算结果与仿真结果误差控制在 8%18。由于三维集成电路技术的兴起，3D NoC 也逐渐成为研究热点，其中基于 TSV技术的 3D NoC 更是研究的热门。目前，研究已经覆盖 3D NoC 的路由结构、拓扑结构、时钟网络分布、布局布线、功耗建模和温度分布等各个方面。Brett Feero 等人通过仿真对比了 2D/3D Mesh、Stacked Mesh 和 Torus 等结构，证明了 3D NoC结构在吞吐量、互联延迟和功耗等方面的优越性1920。Dongkook Park 等人研究了复杂度较低的 2D/3D NoC 的路由结构，并探讨了布局布线对处理器和 Cache 性能带来的影响21。佐治亚理工学院的 Xin Zhao 等人设计了一种低时钟偏差、低功耗的 3D 时钟分布22。针对 3D IC 中时钟树的失效问题，台湾的 Chiao-Ling Lung 提出了一种新型容错单元(fault-tolerant unit)来解决23。宾夕法尼亚州立大学的 Xie Yuan 教授带领的项目组比较系统的研究了路由器结构、多维映射、动态虚通道、4 三维片上网络功耗评估及映射算法 布局布线、系统级仿真平台等多个方面，并取得了一系列的研究成果。国内自 2003 年开始，片上网络的研究逐渐增多，其中的典型代表是国防科技大学的高性能同构 4 核 DSP 和中科院的同构 64 核的龙芯 3 号芯片。3D NoC 方面，上海交通大学付宇卓教授领导的项目组，研究了 3D NoC 的拓扑结构、仿真平台和散热问题。总的来说，国内对 3D NoC 的研究刚刚起步，还需要投入人力物力。1.3 研究目标及成果 本论文的研究目标是建立完善的三维片上网络互联部分的功耗模型，改进ORION2.0仿真器以实现三维片上网络互联功耗的快速评估。本文还通过CACTI5.3仿真器评估了 Cache 部分的功耗。在功耗评估的基础上，研究了模拟退火算法、遗传算法和分支界限算法三种映射算法，从而实现了三维片上网络互联功耗在算法级上的优化。本论文的研究工作主要包括以下五个方面：1.改进了水平链路的功耗模型：考虑了多层结构对每层的水平链路的电学参数特别是电容参数的影响；2.改进了 TSV 的功耗模型：既考虑了 TSV 之间的耦合电容引起的动态功耗也考虑了 TSV 的静态功耗；3.通过 CACTI5.3 仿真器评估了 Cache 部分的功耗；4.通过改进的功耗仿真器 ORION2.0 评估了两种三维结构在不同注入率下和三种典型应用下的功耗，并与二维结构进行对比，验证了三维结构在功耗方面的优势；并进一步比较了不同包格式下的片上网络的功耗和采用不同端口数路由的片上网络的功耗，分析了进一步优化功耗的可能性；5.实现了模拟退火算法、遗传算法和分支界限算法这种片上网络映射算法，比较了三种算法的优化效率，从而在算法级上优化了片上网络的互联功耗。1.4 本文的结构安排 本论文共分为六个部分，具体章节安排如下：第一章为绪论，首先介绍了片上网络的优势、三维集成电路的兴起和功耗问题的研究，然后在此基础上介绍了该领域国内外的发展和研究现状，最后对论文的研究内容和基本结构做了说明。第二章主要包括两部分。第一部分介绍了与三维片上网络的功耗建模有关的一些基本概念，包括三维片上网络的拓扑结构、路由算法、交换策略、TSV 的基本结构和工艺、Cache 的基本知识等；接着介绍了功耗的基本概念。第二部分主要 第一章 绪论 5 介绍了用于评估片上网络功耗的仿真平台及各个仿真平台的基本特点。第三章是本论文的理论核心，即三维片上网络的互联功耗建模的过程。互联功耗模型主要分为两部分，包括路由模块的功耗模型和链路部分的功耗模型。其中链路部分的功耗又包括水平链路的功耗和垂直链路 TSV 的功耗。每一具体模块的功耗又进一步细分为静态功耗和动态功耗两部分讨论。本章最后简要讨论了Cache 部分的基本结构。第四章介绍了任务图到片上网络的映射问题。首先用数学方法描述了片上网络的映射问题；然后介绍了任务图的表示，目标函数的选择；最后介绍了遗传算法、分支界限算法和模拟退火算法三种映射算法的基本原理和实现步骤。第五章是仿真结果与分析。首先评估了二维片上网络结构、一层 Cache 的三维结构和两层 Cache 的三维结构在不同注入率下的功耗对比，证明了三维结构在功耗方面的优势并从理论上解释了原因；然后讨论了适用于不同包格式的片上网络的结构在不同注入率下的功耗的变化趋势，着重讨论了大小均为 2Kb，但是包格式不同的情况下片上网络的功耗差异；接着在两层 Cache 的三维结构的基础上进一步改进，讨论了七端口路由的三维结构和十端口路由的三维结构的功耗变化趋势；最后对比了遗传算法、分支界限算法和模拟退火算法三种映射算法的优化结果。论文最后总结了本文所做的工作，说明了本文的不足和需要改进的地方。6 三维片上网络功耗评估及映射算法 第二章 3D NOC 基本概念及仿真平台介绍 7 第二章 3D NoC 基本概念及仿真平台介绍 2.1 3D NoC 相关概念 2.1.1 拓扑结构 NoC 的互联部分主要有三个大方向的研究内容，分别是拓扑结构、路由算法、交换策略。NoC 的拓扑结构是指通信节点在芯片内部的分布情况及连接方式。拓扑结构影响了数据包从源节点到目的节点需要经过的跳数和每跳的互联长度，从而影响了数据包的功耗、传输的延迟和吞吐量等参数。拓扑结构也会对网络的可靠性造成影响因为拓扑结构影响了出现错误时路由的备选路径。拓扑结构实现的复杂度取决于两个参数：每个节点的链路数（节点度）和芯片中实现拓扑的难度（所需的线长和金属层数）。由于各个系统的性能需求存在差异，需要根据不同系统的特点权衡选取合适的拓扑结构。图 2.1 是两种常见的二维 NoC 的结构示意图：左图是 2D Mesh 结构，右图是 2D Tours 结构。图 2.1 中每个方块表示一通信节点，黑线表示互联线。这两种拓扑结构规则、易于实现，因此得到比较广泛的应用。2D Mesh 和 2D Tours 的节点度均为 4，节点度越大的结构要求的路由器端口数和链路数越多。2D Tours 因其多出来的连接网络首尾节点的长互联线，相较于 2D Mesh结构有更高的网络吞吐量和更小的网络延时，但功耗也有相应提高。由于有更多的备选路径，2D Tours 的容错能力也更强。图 2.1 16 节点的 2D Mesh 和 2D Torus NoC 拓扑结构 三维片上网络常见的两种拓扑结构是 3D Mesh 结构和 3D Torus 结构，是 2D Mesh 和 2D Torus 结构在三维空间的扩展，该结构如图 2.2 所示。3D Mesh 结构中每层或者层与层之间均采用 2D Mesh 结构相连，同一层内的节点是由普通的导线8 三维片上网络功耗评估及映射算法 相连接的，层与层之间垂直的互联线采用的是 TSV 结构。3D Torus 是在 3D Mesh结构基础上形成的环状结构，即增加连接每一列和行的首尾节点的长互联线。最顶层与最底层的长互联线一般也比每层中的长互联线短。为清楚表现 3D Torus 中各节点的连接关系，图中只画了面向读者的三个面的长互联线。图 2.2 中，黑点表示网络的通信节点，一般是一个路由单元，实现节点之间的通信。图 2.2 64 节点的 3D Mesh 和 3D Torus 拓扑结构 2.1.2 路由算法 路由算法决定了数据包在网络中传播的路径。好的路由算法能均衡整个拓扑的流量，极大的减少网络冲突、从而避免网络热点的产生，并提高网络的通信能力。另外，路由算法可在尽量不影响网络性能的前提下保证数据包能绕过出错的链路和节点，因此路由算法也是实现网络容错的重要途径。片上网络的面积和延时等参数要求路由算法的物理实现不能太复杂，因为复杂的路由结构会导致的大的关键路径延迟和大的面积开销。另外虽然路由的功耗在片上网络总功耗中所占的比例较小，但路由算法选择的路径会直接影响数据包的跳数，进而影响链路功耗。因此，路由算法是影响片上网络性能的一项关键技术。NoC 路由算法根据是否与当前的网络流量和拥塞状况有关，可以分为确定性路由(Deterministic routing)和自适应路由(Adaptive routing)两种。确定性路由算法不考虑整个网络的流量和拥塞情况，只与起始地址和目的地址有关。也就是说，给定起始地址和目的地址，路由路径就确定了，与当前网络的状态无关。虽然确定性路由算法简单、易于实现，但是有一定的盲目性。确定性路由算法主要包括维序路由算法、随机路由算法和洪泛路由算法三种23。为对网络的各种状态进行响应，避开网络热点，绕过错误节点，开发出了能够灵活地选择路由路径的自适应路由算法，也就是说，即使数据包的起始节点和目的节点一致，不同的网络状态可能会导致不同的路由路径。自适应路由算法在网络阻塞的情况下，会获得更好的性能，比如更低的网络传输延时和更高的网络带宽的饱和值。这种算法的缺点 第二章 3D NOC 基本概念及仿真平台介绍 9 是需要的路由逻辑比较复杂，存在死锁问题，而且在网络通畅的情况下开销较大。自适应路由算法主要包括奇偶转弯模型算法、转向路由算法、DyXY 路由算法和SRN 路由算法23。本文采用的是最简单的确定性路由算法，也就是维序路由算法。以二维片上网络结构为例，维序路由算法是指 XY 路由算法，即先沿着一个方向传递数据包，当数据包到达目的节点所在的行或列时，再沿着另一个方向传递。XY 路由算法的具体步骤如图 2.3 所示：先沿着 X 方向传递，直到数据包被传递到目的节点所在的列；再沿 Y 方向将该数据包传递至目的节点。对于 3D NoC，我们采用了拓展的维序路由算法，即 XYZ 路由算法：数据包先沿 X 方向传播，然后是 Y 方向，最后沿着 Z 方向到达目的节点。x=axay=bWESTLOCALybSOUTHNORTHYNNYYNYNEAST 图 2.3 XY 路由算法的路径选择的具体步骤 2.1.3 交换机制 片上网络的数据包的交换机制是指数据包在片上网络中的传递方式，并明确了输出端口将数据包转发出去的时机。片上网络的数据包的交换策略可分为两类:面向连接的和无连接的。最早提出的电路交换是面向连接的交换技术。而无连接的交换策略主要包括分组交换、虚切通和虫孔交换24。下面详细介绍电路交换、分组交换、虚切通和虫孔交换四种交换策略。电路交换：电路交换起源于采用公共交换的电话网。首先，根据信息包的包头信息和选定的路由算法选路，建立路径并预定所经过路径的信道资源。接收端在接收到包头后会沿原路返回一个应答信息。发包端接收到接收端产生的应答信息后，就沿着预定的信道开始传输数据。当数据传输结束后，发包端发送一个结束标志，并依次释放预定的信道。信息包在整个传输过程中，独占整个链路的带宽。对于信息包数目少但包很长的情况下，电路交换可以保证高吞吐和低时延。这是因为电路交换可以独占整个物理带宽，而且当包比较长时,包的传输时间远大于路径建立的时间。另外，由于不需要在路由节点中添加缓存资源，电路交换实现起来面积开销比较小。但是当数据包的数目较多，而且包长比较短的情况，由10 三维片上网络功耗评估及映射算法 于一条链路只能被一个预留通道的应用所使用，建立路径的时间开销将不可容忍，性能会很差。分组交换：分组交换以分组为包交换的基本单元，每个分组的都有一个包头，包含源节点地址、目的节点地址、标志位和一些控制信息，分组大小可以不等。路由节点接收到一个数据包后，先把整个数据包存储在路由端口的缓存中，然后解析包头信息，并根据路由决策单元选择输出通道。输出通道确定后，数据包通过交叉开关传递给下一级的路由单元。采用分组交换，数据包的传输延时及功耗等参数均与数据包在网络中的跳数成线性关系，不太适合大规模的片上网络。并且由于路由端口缓存至少为一个包的大小，因此面积开销也不容忽视。另外分组交换机制还存在乱序和抖动的问题：乱序是指由于分组独立路由，不同的分组在网络中可能经历了不同的路径，不能保证按照原来的先后顺序到达目的节点。抖动是指数据包的到达时间无法预测。尽管有这些缺点，分组交换因其实现简单，在数据量不大的时候能获得不错的性能，因此得到了广泛应用。本文也采用分组的交换方式。虚切通：虚切通交换是指把分组进一步划分为大小通常为若干个比特的微片(flit)，然后将所有的微片按顺序排好。第一个微片称为头微片，存放所需的路由信息。因为只有头微片包含着路由信息，即源节点地址、目的节点地址等信息，所以路由模块不需要等待整个数据包都接收完再转发。因此在网络不阻塞的情况下,路由节点一接收到头微片就立即读取头微片中包含的路由信息，接着路由算法模块和仲裁单元负责选通路径。如果选定的输出通道未被占用，就把头微片转发出去,后续的微片紧随其后。因此本交换机制能大大缩短路由单元缓存的面积和分组交换的时延24。虫孔交换：虫孔交换和虚切通交换策略基本相同，只是在阻塞时略有区别。2.1.4 TSV 结构及工艺 目前 3D 垂直集成的工艺主要有四种，分别是微冲击技术(micro-bump)、无线耦合技术、线键合技术(wire bonded)和垂直过孔互联技术21，其中垂直过孔互联技术 TSV 最有可能成为未来的主流 3D 工艺。TSV 与传统的水平方向导线结构差距很大，是 3D IC 独有的特殊结构。目前，TSV 可以分为导热 TSV 和信号 TSV 两种，其中导热 TSV 仅仅用来降低温度，并不传递电信号；信号 TSV 兼有传递信号和散热的两种用途。本文只考虑信号 TSV。在过去的几年里，工业界和学术界已提出多种制作 TSV 的工艺方法，但没有一种方法得到普遍认可。不过几乎所有人对 TSV 的结构都有一个共识：将铜作为TSV 的填充金属，也可以选择钨和金等其他低应力、无空孔、具有良好热导性和 第二章 3D NOC 基本概念及仿真平台介绍 11 电导性的金属材料；铜的外层是粘附层，一般选择TiN；最外层是环形绝缘介质，作用是保护圆柱形铜金属，一般选择2SiO或者34S N，具体结构如图 2.4 所示。由于粘附层很薄，对整个 TSV 结构的电学参数影响很小，为了简化计算，在后续讨论中暂不考虑粘附层所带来的影响。图 2.4 离子束扫描电子显微镜下的 TSV 结构 2.1.5 Cache 的基本概念 CPU 的运算速度比内存的读/写速度要快很多，这就使得 CPU 在访问内存时要花很长时间来等待内存的操作，这种空等待造成整体系统性能的下降。为解决这种速度不匹配的问题，大多数系统采用分层的存储结构，如图 2.5 所示，即内层为Cache，中间是主存，外层是海量存储器的结构来均衡速度和成本的要求。存储器层次结构的最顶层是寄存器(Register)，速度最快，价格也最昂贵。下一级是基于 SRAM 的高速缓冲存储器，即 Cache，包括一级高速缓存 L1 Cache 和二级高速缓存 L2 Cache 组成。L1 Cache 通常又分为用来存放数据的数据 Cache(D-Cache)和存放各种操作指令的指令 Cache(I-Cache)。L1 Cache 的容量小，但数据存取速度较快，L2 Cache 的容量大，一般比 L1 Cache 大一个或一个以上数量级，数据存取速度较慢。部分系统中也存在三级 Cache 的结构。再下一级是基于 DRAM的主存。在同样容量下，DRAM 的价格只是 SRAM 的 1/4，而且 SRAM 还有大体积和低集成度的缺点。因此主存速度慢，但是成本也低。次外层是本地硬盘，速度和成本进一步降低。最外层是网络服务器硬盘。大量程序的运行结果表明程序存在局部性访问的特性，即在较短的时间范围内，程序产生的地址往往集中在存储器逻辑地址空间的较小范围内。因此，提高程序的运行速度，可以将正在执行的指令地址附近的部分数据和指令从内存调入Cache 中，供 CPU 在一段时间内使用。这样经过若干次的内存访问操作之后，CPU要访问的内容大部分情况下已经存放在 Cache 中了。12 三维片上网络功耗评估及映射算法 registeron-chipL1 cache(SRAM)off-chipL2 cache(SRAM)Main memory(DRAM)Local secondary storage(local disks)remote secondary storage(distributed file systems,Web servers)fastersmallerexpensiverslowerlargercheaper图 2.5 层次化存储器的结构示意图 CPU 可以在零等待状态下快速完成数据的读写操作有两个原因：一是根据局部性原理，CPU 的读写操作主要集中在 CPU 和 Cache 之间；二是 Cache 的速度与CPU 相当35。CPU 在访问内存时，首先判断要访问的内容是否在 Cache 中，如果在，即命中(hit)，此时 CPU 直接从 Cache 中调用内容；否则为未命中(miss)，CPU会通过 Cache 对主存中的相应内容进行操作。也就是说，只有在 Cache 不包含 CPU所需要的内容时，CPU 才需要访问低速的主存。由此可见，Cache 的命中率是提高效率的关键，其计算见式(2-1)。很多因素都会影响 Cache 的命中率，最主要的是映射方式和替换算法。例如，假设 Cache 的命中率为 90%，则意味着只有 10%的存储器访问是对低速主存进行的。也就是说，CPU 可用 90%的总线周期从 Cache中直接读取数据。Cache 的设计目标是使 CPU 的访问尽可能在 Cache 中进行。=100%命中次数命中率存储器访问总次数 式(2-1)Cache 中最受关注的是映射机制、替换算法和写策略。下面就这三方面分别进行讨论。映射机制：因为 Cache 的行数少于主存储器的块数，因此需要映射方式来确定主存储器的某块映射到 Cache 中的哪几行。在硬件上，映射方式的选择决定了Cache 的结构。一般有三种映射方式：直接映射(direct mapping)、全相联映射(fully associative mapping)和组相联映射(set associative mapping)。替换算法：假定计算机开始执行一个程序，它从内存中取指令和数据，同时将这些内容载入 Cache。当 Cache 为空或很少被占用时，这会工作的很好。但是，最终计算机会需要将数据装入已占用的Cache单元。因此要将哪些数据移出Cache，这些数据如何保存到物理内存是很重要的。Cache 中数据的移入移出涉及到替换算 第二章 3D NOC 基本概念及仿真平台介绍 13 法。一般有三种替换策略，即 FIFO、LRU 和 Random。FIFO 即先进先出，是指按照从顶单元到底单元的顺序依次填充 Cache。当数据复制到最后一个单元时，Cache被占满了。然后，返回最顶单元，用下一个要存储的数据替换此单元原有的数据。继续这一过程，按此方法工作到底单元后，再循环至顶单元。这一策略总是替换掉当前所有数据中最早被载入 Cache 的那一个数据。实现这一策略只需要一个寄存器，用来保留指向下一个要被替换单元的指针。LRU 是近期最少使用策略，跟踪单元的访问顺序，用新的数据替换近期最少使用的数据。这需要为每一个 Cache单元配备一个计数器。这种策略常用于组相联的 Cache 结构。Random 代表随机策略。随机策略是指随机的选择一个单元给新的数据使用。写策略：指如何把内存的内容写入 Cache 中，主要有写直达法(write-through)和回写法(write-back)两种方法。写直达法是指每次信息从 CPU 写入 Cache 时，也要将该信息写入相应的物理内存单元。这种方法保证了物理内存总有正确的内容，但这也要求额外的写回物理内存的时间。写回法是指写入 Cache 的内容并不总是要写入物理内存，仅当数据移出 Cache 时，该数据才写回物理内存一次。该方法节省了写直达法中复制数据到物理内存的时间，但造成了物理内存持有无效值的一个时间帧。2.1