三维片上网络故障及拥塞感知的容错路由器设计

三维片上网络中路由器的输入端口和交叉开关出现故障,将严重影响整个网络的性能,因此文章提出了一种故障及拥塞感知的容错路由器.通过增加一个冗余的输入端口和旁路总线,不仅能实现对输入端口和交叉开关容错的目的,而且还能在没有端口故障的情况下使用冗余端口有效地解决拥塞问题.实验表明此容错机制能够使得网络在故障路由器多、拥塞严重的情况下,仍然保持良好的性能.

三维片上网络研究综述

三维片上网络以其更短的全局互连、更高的封装密度、更小的体积等诸多优势,已引起国内外学术界和产业界的高度重视.对三维片上网络的研究,将直接影响一个国家未来三维集成电路和三维芯片产业的发展,也关系到国家安全.近年来,三维片上网络逐渐成为片上网络研究领域的一个重要方向,已取得了许多研究进展,但仍然存在许多挑战性的课题.对三维片上网络的基本问题作了简介;分析了三维片上网络在国内外的研究现状;讨论了三维片上网络研究中的关键问题,归纳出网络拓扑结构、路由机制、性能评估、通信容错、功耗、映射、测试、交换技术、服务质量、流量控制、资源网络接口等12类研究课题;分类综述了关键问题的研究进展;分析了三维片上网络存在的问题;指出,在三维片上网络拓扑结构方面:个性化拓扑结构设计、仿真平台研究开发、基于新型拓扑结构的三维芯片样片试制以及无线技术的引入等,在路由算法方面:适合3D Torus的路由算法、结合无关路由与自适应路由算法优点的新路由算法、适合各种新型拓扑结构的高效路由算法等,在性能评估方面:永久故障的容错、改进仿真程序增加对物理链路的建模、充分考虑通信的局部性等,在功耗方面:对拓扑结构/映射算法/路由算法和布局进行综合优化、动态和静态控制相结合、更为精确的3D No C功耗模型等,在映射方面:发热均匀性、动态路由策略下映射评估模型的优化、低功耗映射算法、基于优化算法的组合映射等,都将是三维片上网络未来的重要研究课题.

带分复用的三维片上网络测试规划研究

三维片上网络(3D No C)中IP核的测试问题日趋突出,测试规划是提高测试效率的有效方法。基于重用No C作为测试存取机制的并行测试方法,针对IP核测试数据传输带宽与TAM带宽不匹配的问题,提出带分复用方法,对有限带宽的TAM进行动态细分,将多核的测试数据共享同一物理TAM实施并行传输,并结合3D No C结构设计二维编码,建立带宽分配和测试顺序模型,采用多种群遗传模拟退火算法,在总功耗、层功耗双重约束下对IP核的带宽分配和测试顺序进行双重优化,提高并行测试效率以获得最短测试时间。算法中针对测试顺序优化设计移位互换杂交策略,并运用精英配对方法加快种群寻优速度,设计求精操作进一步优化测试时间,通过比较、淘汰、替换机制加强种群间交流,增加种群多样性,避免算法陷入局部最优。以ITC'02标准电路作为测试对象,实验结果表明,该方法通过提高带宽利用率,提升了并行测试效率,降低了资源占用,有效地缩短了测试时间。

动态带分复用的三维片上网络协同优化研究

采用动态带分复用进行三维片上网络测试规划和调度协同优化研究,在测试中,给IP核动态分配带宽固定的TAM,同一时刻可使多个核的测试数据共享同一物理TAM并行传输,解决IP核测试数据传输带宽与TAM带宽不匹配的问题,实现IP核并行测试的最大化。对带宽分配的结果设计多种群云进化算法进行TAM内调度,实施精英种群间交叉变异提高多样性,协同开展测试规划和调度优化以获得最短调度时间。以ITC’02基准电路作为实验对象实施仿真验证,实验结果表明,在满足功耗、带宽约束的条件下,动态带分复用的测试策略通过提高带宽利用率,有效地减小了测试时间,提高了测试效率。

三维片上网络TSV复用容错策略

三维片上网络结合了垂直互连技术所带来的优势和片上网络所具有的可扩展性的优点,大大提高了系统的性能,降低了功耗。但目前的制造工艺使得用于垂直互连的硅通孔(TSV)的产品良率仍然较低,严重影响三维片上网络系统通信的可靠性。以往处理TSV硬故障一般是通过添加一定数目的冗余链路来达到容错的目的,但这种方法会带来较大的面积和功耗的开销,并且只能处理数量有限的TSV故障。不添加冗余链路,通过对故障链路中功能良好TSV的复用,将数据微片多次传输,达到容TSV硬故障的目的。通过添加ECC编码解码模块来达到容瞬时故障的目的。实验分析表明,该设计方案在保证系统可靠性的基础上还具有较高的吞吐量与较低的延时。

一种改进的基于粒子群的三维片上网络优化布局算法

提出了一种改进的基于粒子群算法的优化布局算法(Improved Particle Swarm Optimization,IPSO)来替换原有的基于模拟退火(Simulated Annealing,SA)算法的优化布局算法,使其更加适用于大型三维片上网络的仿真。通过比较这两种算法的基本思想,给出了这两种算法的实现步骤并详细介绍了IPSO算法的改进思路。最后利用一款现有的三维片上网络仿真器进行了仿真验证。结果表明,提出的IPSO算法比原来的SA算法更适用于大型三维片上网络的仿真。

基于Prim初始种群选取优化遗传算法的三维片上网络低功耗映射

针对将计算任务合理地映射到三维片上网络(NoC)的问题,提出了一种基于遗传算法(GA)的改进算法。GA具有快速随机的搜索能力,Prim算法可在加权连通图内得到最小生成树,改进算法结合了两种算法的优势,将计算任务合理地分配到各个网络节点,对于优化三维片上网络功耗和散热等问题具有很高的效率。通过仿真实验,对所提出的基于Prim算法的改进GA与基本GA的3D NoC映射算法进行了对比,仿真结果显示,基于Prim算法的改进GA平均功耗更低,从总体趋势来看,处理单元数量的增加与功耗降低幅度成正相关,在101个处理单元情况下,平均功耗比基本GA降低32%。

三维片上网络映射算法研究综述

三维片上网络(Three-dimensional Network on Chip,3D No C)以其更短的全局互连、更高的封装密度、更小的体积等诸多优势,已成为国内外工业界和学术界一个重要的研究领域.对于3D No C的研究,映射是一个关键问题,对系统的功耗、延迟等性能均有很大的影响.本文介绍了3D No C映射的基本问题;归纳了3D No C映射算法的分类方法,将其分为启发式映射算法和非启发式映射算法两大类,其中,启发式映射算法又分为基于遗传算法、基于粒子群算法、基于模拟退火算法以及基于蚁群算法的映射算法4种类型,非启发式算法具有多样性;另外,对现有的3D No C映射算法进行了分类综述,分析比较了各种映射算法的特点;最后,探讨了3D No C映射的研究方向.

异构三维片上网络布局优化的超图划分算法

片上网络作为一种将大量嵌入式内核集成到单个晶圆片上的可行性技术,与传统片上系统相比,更能应对未来需要更大规模集成内核的挑战,从而得到了更广泛的应用。然而,目前大多数对片上网络的研究是在规则的架构上进行的,即假定所有单元片面积相同,但是这种假设过于理想化。因此,基于异构布局的三维片上网络的研究是非常有必要的,而其中网络单元的合理划分对片上网络的性能有着重要的影响。介绍了基于异构布局的三维片上网络架构,并将超大规模集成网络中的单元映射成一张超图,并且对此超图进行了多级划分。在算法框架的不同阶段,介绍了常见的算法,并且对相应算法的潜在问题进行分析,随后对这几种算法进行改进以提高片上网络的性能。最后,通过对几个常见的超大规模集成单元数据集进行实验分析,比较了不同阶段的算法对该片上网络各个性能的影响,并得出各个数据集上最优的hMetis算法框架。

三维片上网络体系结构研究综述

伴随着三维集成电路的迅速发展,三维片上网络受到国内外研究者的广泛关注.三维片上网络主要用于实现三维堆叠芯片的互连通信,为三维集成电路提供超低的延迟和竖直方向上超高的带宽,从而解决系统集成度增加导致的通信瓶颈问题,有利于克服存储墙问题并提高三维堆叠芯片的性能.文章介绍了三维集成电路研究现状及其结构优势,分析三维片上网络体系结构的特点和存在的问题,包括竖直方向的单跳传播问题、路由器交叉开关的复杂度控制问题以及热效应的控制问题,从系统层、微结构层和电路层对三维片上网络体系结构的研究热点及其实例进行了深入分析,最后对三维片上网络所面临的挑战和设计方法进行了总结和展望.

三维片上网络路由算法的研究

三维集成电路是集成电路发展的一个主要趋势,为了解决大规模三维集成电路的互连问题,三维片上网络应运而生.而三维路由算法决定了每个数据包在传输时所要经历的路径,以及数据包是否能正确地传送到目的地址,是三维片上网络研究的关键技术之一.本文从是否考虑网络流量和拥塞状况的角度,将三维路由算法分为无关路由算法和自适应路由算法,并对目前已提出的三维路由算法的性能进行分析与综述,指出了三维片上网络路由算法的研究方向.

面向非规则三维片上网络的自适应可靠路由方法

面向存在永久性链接故障的非规则三维片上网络,提出一种低成本自适应可靠路由方法.首先根据非规则三维片上网络的拓扑结构,优先选择一条汉密尔顿路径进行容错路由,在没有汉密尔顿路径的情况下,则执行生成树容错路由算法绕过故障链接;然后将基于动态规划的端口选择机制拓展到三维空间,结合前述路由算法来避开网络冲突区域,完成将数据包由源路由器节点传输至目的路由器节点的路由过程.实验结果表明,与之前的AFRA方法和基于生成树的可靠路由方法相比,该方法具有较高的通信性能和可靠性,同时所需的网络开销较低.

基于改进模拟退火的三维片上网络映射算法研究

在基于模拟退火算法的基础上提出了一种改进温度下降函数和自适应的生成邻域解的新型算法.该算法通过新提出的温度下降函数,使得在初始温度较高的时候下降较为平滑,同时在邻域解的生成过程中采用新的生成邻域解的方式,充分实现算法的全局性,克服传统模拟退火算法易陷入局部最优解的困境;同时在温度较低时候,平滑的温度下降方式也有利于进行充分的局部搜索,取得最优解.实验结果表明,与传统的模拟退火算法相比,提出的新型的模拟退火算法在三维片上网络的映射过程中,在功耗和收敛速度两个方面有显著的提升.

三维片上网络正四面体裂变拓扑结构研究

旨在研究新型三维片上网络正四面体裂变拓扑结构,给出了该拓扑结构的生成过程;对该拓扑结构进行了编码设计和路由设计。通过对gpNoCsim片上网络仿真器进行三维扩展,对正四面体裂变拓扑结构进行性能仿真实验。仿真结果表明,在均匀负载模式下,正四面体裂变拓扑结构的平均延时和平均跳数均低于Mesh结构,当注入率为0. 02时,平均延时比Mesh结构低16. 8%、平均跳数比Mesh结构少5. 5%;在局部负载模式下,当注入率大于0. 008时,正四面体裂变拓扑结构的平均延时和平均跳数与Mesh结构相比均有明显改善;当注入率为0. 014时,平均延时比Mesh结构降低18. 7%、平均跳数比Mesh结构减少9. 6%。这说明正四面体裂变拓扑结构可用于三维片上网络拓扑结构设计。

三维片上网络高维超立方裂变拓扑结构研究

三维片上网络是解决片上网络通讯瓶颈的重要途径,拓扑结构是三维片上网络研究中的关键问题之一。针对高维超立方拓扑结构节点度迅速增加,出现通讯瓶颈的问题,提出一种高维超立方裂变拓扑结构,该拓扑在同等网络规模下具有网络直径短、可扩展性强等优点。以五维超立方裂变拓扑结构为例进行了仿真实验,并与3D Mesh拓扑结构进行了对比分析:当两种拓扑结构在均匀负载状态下达到饱和时,五维超立方裂变拓扑结构的吞吐量比3D Mesh拓扑结构高300%,平均延时比3D Mesh拓扑结构低85.1%,平均跳数比3D Mesh拓扑结构少21.5%;在局部负载下,五维超立方裂变拓扑结构的平均延时比3D Mesh拓扑结构低79.1%,平均跳数比3D Mesh拓扑结构少13.3%。仿真实验表明提出的网络拓扑结构既保留了原有超立方体拓扑结构的优点,又解决了高维超立方体拓扑结构的通讯瓶颈问题。

三维片上网络离散量子粒子群布图算法研究

三维片上网络在多种性能上均优于二维片上网络,已成为研究热点。布图算法直接影响芯片的面积和布线长度,成为三维片上网络优化设计的重要方向。提出一种基于离散粒子群算法的三维片上网络布图优化算法,与之前常使用的模拟退火算法相比,不再使用单一解局部扰动的方式得到整个解空间,该算法采用初始化随机种群并不断迭代的进化方式,具有更优的搜索能力和更快的收敛速度。仿真结果表明,采用该算法选择布图方案可以显著降低微片延迟,节省CPU计算时间,尤其是在IP核数量众多的测试用例和高注入率情况下效果更为明显,如对于ami49测试用例当注入率为100%时,基于离散量子粒子群算法的结果和基于模拟退火算法的结果相比,平均微片延迟减少了20.63%,CPU平均时间减少了69.40%。

基于混合混沌大爆炸算法的三维片上网络低功耗映射

三维片上网络(3D NoC)被认为是提高多核处理系统性能的一种方式。对于3D NoC的设计,如何将给定应用特征图(APCG)上的IP核适当地分配到3D NoC架构中是IP核映射的关键问题。一种优秀的映射算法及一次合理的映射可以大幅改善片上网络的通信功耗、发热、延时等指标。大爆炸算法(BB-BC)是一种新型的元启发式群体智能优化算法;混合混沌大爆炸(HCBB-BC)算法是在大爆炸算法基础上进行改进的一种算法,它具有参数简单、收敛速度快等优点。文中提出将混合混沌大爆炸算法用于解决三维片上网络映射问题,这是首次用大爆炸算法的相关算法来解决3D NoC映射问题。仿真实验结果证明,与现有的3D NoC映射算法相比,所提方法可以用更少的迭代次数和时间来找到更好的解决方案,同时有效地降低3D NoC的映射功耗。在经典任务图映射条件下,混合混沌大爆炸算法与遗传算法(GA)相比,收敛速度提高了36.73%,与粒子群算法(PSO)相比,收敛速度提高了22.45%;同时,混合混沌大爆炸算法的平均功耗比遗传算法的平均功耗的最大值低5.75%,并且比粒子群算法的平均功耗的最大值低3.90%。在随机任务图映射条件下,混合混沌大爆炸算法仍然能够保持稳定的功耗优化效率和更快的收敛速度。

三维片上网络(3D NoC)热感知路由算法研究

近年来,堆叠结构的三维片上网络(3D NoC)逐渐兴起,然而,其高集成度导致了大的功率密度和高的系统温度,也可能会导致系统中出现局部过热节点。3D NoC散热不平衡影响着芯片性能和可靠性。提出将改进后的A^(*)算法用于3D NoC热感知路由,能够保证跨过节流节点找到一条相对最短且最冷路径。显然,该算法在解决系统热问题上有显著的优势。

基于拥塞感知的三维片上网络容错路由算法

随着芯片的特征尺寸进入纳米时代,基于传统总线的通信架构出现了性能瓶颈,三维片上网络(3D NoC)架构以其良好的可扩展性,被认为是未来芯片制造最有前途的通信架构之一。3D NoC的容错成为学术界的研究热点,文章提出了一种拥塞感知容错路由算法,可以根据故障程度和拥塞程度来为数据包选择合适路径,同时考虑了温度对通信架构可靠性方面的影响。使用Booksim2.0工具与其他方法的实验结果表明,文中方法的平均数据包时延最大降幅达20%,丢包率平均减少了32%,提高了3D NoC可靠性的同时提升了整体通信性能。

片上网络二维和三维结构的通信性能分析

芯片集成技术的迅猛发展,使得片上网络从二维向三维扩展成为可能。研究表明三维片上网络因拓扑维度的增加而缩短了通信距离,极大地提升了网络的平均通信性能。本文对比分析了k-ary-2-mesh网络及其对应的三维网络在最差情形下的通信性能,得出了以下结论:三维网络的平均通信性能虽然更优,但受垂直信道影响其最差情形下的通信性能可能劣于其对应的二维网络。本文的分析基于网络演算理论,该理论广泛应用于计算信息流穿越各种网络元素的延迟上界。