延迟优化的片上网络低功耗映射*

片上网络（NoC）是解决传统基于总线的片上系统（SoC）所面临的功耗、延迟、同步和信号完整性等挑战的有效解决方案。功耗和延迟是NoC设计中的重要约束和性能指标,在设计的各个阶段都存在着优化空间。基于蚁群优化算法,通过通信链路上并发通信事件的均匀分布来降低NoC映射阶段的功耗和延迟。仿真实验表明,与链路通信量负载均衡的方法相比,该方案能进一步在拓扑映射阶段优化功耗和延迟。     

基于改进遗传算法的3DNoC低功耗映射研究

二维片上网络（Two-Dimensional Network-on-Chip,2D NoC）在面积、功耗、布局布线、封装密度等方面都已达到了瓶颈。与2D NoC相比,三维片上网络（Three-dimensional Network-on-Chip,3D NoC）有着诸多优势,因此3D NoC逐渐成为一个重要的研究方向。随着3D NoC集成度的提高,低功耗映射逐渐成为研究热点。将贪心算法的思想与遗传算法相结合提出一种改进的遗传算法,用以解决3D NoC低功耗映射问题,相对于传统遗传算法,改进遗传算法具有更优的搜索能力。仿真结果表明,采用改进后的遗传算法解决3D NoC映射问题可以降低功耗,从总体趋势来看随着处理单元数量的增加功耗降低幅度逐渐增大,在120个处理单元情况下总功耗可降低14%。     

基于云自适应遗传算法的NoC映射研究

NoC映射是NoC设计中的重要步骤,映射结果的优劣对NoC的QoS约束和通信功耗有着很大的影响。提出一种采用云自适应遗传算法实现NoC映射的方案,该算法利用云模型对传统遗传算法加以改进,以此新方法自动调整遗传算法过程中的交叉概率和变异概率,从而达到优化遗传算法的目的。结合NoC映射中的具体问题,在功耗和延时约束的限制条件下,建立了延时约束下的NoC映射功耗数学模型。实验表明,该方法在NoC映射中取得了良好的效果,降低了通信功耗。     

基于改进遗传算法的片上网络低功耗映射方法

针对规模庞大的应用如何在NoC平台上低功耗地运行,本文提出了一种基于改进遗传算法的片上网络低功耗映射方法。该方法利用任务节点的通信权重和映射平台的结构特征,对任务节点进行优先级划分并根据任务节点优先级及其连接关系获取较优初始映射解集。在此基础上,在遗传操作中加入轮盘转赌、最优邻居选择、进化逆转等操作,同时每次迭代中都以一定的概率选择初始解,防止算法停滞。实验结果表明,在相同任务模型和映射平台下,改进遗传算法对比于传统遗传算法和随机映射方法,都大幅度降低了功耗。     

片上互连网络的功耗特征分析与优化

随着处理器核数的增加,片上互连网络NoC结构日趋复杂,导致片上互连网络功耗所占的比重和功耗分析的难度也在增加。片上互连网络的任务映射,既要保证多处理器核心之间通信的高性能,又要保证耗费尽可能少的功耗和面积,即在有限的功耗和面积开销下获得较高的性能。在进行任务映射时,核心之间的通信距离是减少任务通信功耗的关键。连续且近凸的区域有助于缩短任务的通信距离。分析了一种功耗最优的片上互连网络启发式映射算法（INC）,该算法由区域选择算法和节点映射算法组成。对区域选择算法的2个因子进行了改进,使应用总的通信开销最小化且保证后续应用以很小的通信代价进行区域选择。提出了新的基于选择区域的映射算法。它们在动态到达程序映射问题中的实验结果表明,新的区域选择算法和节点映射算法相比于INC,可以减少12.10%的通信功耗,并且带来11.23%的通信延迟优化。     

面向实时复杂系统的基于片上网络多核平台的映射技术研究

为了提高通信与信号处理系统向片上网络(NoC)平台映射的性能,提出一种面向系统能耗和响应时间的新型NoC映射模型。该模型改进了传统映射算法中能耗的计算方法,同时考虑交换网络的能耗和处理节点的能耗,采用多对多映射技术,在带宽约束的基础上,结合复杂通信系统特有的注入率、迭代边界等约束,同时优化能耗和响应时间,提高了映射算法的实用性。仿真实例证明,该映射模型得到的优化方案能降低约15%的系统能耗,能够获得综合的最优性能。     

一种基于遗传算法的片上网络映射算法

片上网络NoC以其高可扩展性成为片上多核的互连解决方案。IP核到NoC结点的映射是片上网络设计的重要阶段。映射对芯片的性能和功耗有重要的影响。本文详细阐述了映射算法的研究现状,给出了映射算法的分类方法,并且分析各种方法的特点。最后,给出一种采用顺序表示的基于遗传算法的NoC映射算法。实验结果表明,该映射算法能够取得较好的准确性和较高的效率。     

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

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

片上网络映射问题的改进禁忌搜索算法

为求解通信时延受约束的低能耗片上网络(NoC)映射问题,提出一种改进禁忌搜索算法.该算法由局部搜索和精英重组2个步骤经过多次迭代完成,局部搜索采用简化的robust tabu search (RoTS),精英重组步骤选用COHX交叉操作.实验结果表明:文中算法与RoTS相比具有优化性能好、搜索空间小的优点,映射结果比分支限界法平均节能16.1%,适于求解大规模NoC映射问题.     

二次改进遗传算法与3D NoC低功耗映射

随着集成电路技术的迅速发展,芯片的集成度不断提高,片上众多处理单元间的高效互连成为关键问题,因而相继出现了片上系统(system-on-chip,SoC)和二维片上网络(two-dimensional network-on-chip,2D NoC).当二维片上网络在多方面达到瓶颈时,三维片上网络(three-dimensional network-on-chip,3D NoC)应运而生.三维片上网络已引起学术界和产业界的高度重视,三维片上网络低功耗映射是其中的1个关键问题.之前的研究曾提出过一种基于改进遗传算法的3D NoC低功耗映射算法,并收到了良好的仿真效果.但当问题规模变大时,计算量随之增大、运行效率明显降低.针对这一问题,对3D NoC中面向功耗优化的二次改进遗传算法任务映射机制进行研究,提出了一种新的3D NoC低功耗映射算法,并对该映射算法进行了仿真实验.实验结果表明,在种群规模较大的条件下,该算法不仅能够继续降低功耗,而且能够大幅度地减少映射算法的运行时间.     

基于NoC系统级平面规划图的网格划分

常规基于片上网络(NoC)的网格划分没有考虑链路功耗,导致对具有内部链接结构的系统进行总功耗估计时会产生较大偏差。针对该问题,提出一种改进的网格划分方法,从IP核到路由的映射过程中产生相应NoC,并运用系统级平面规划图进行象征性网格划分。仿真结果表明,改进方法可降低链路功耗的同时,获得更低的总功耗和更小的碰撞区域。     

面向时延的NoC映射技术研究

针对NoC任务映射问题中时延难以预测和启发式算法效率低的问题,提出一个时延改进模型和近邻随机遗传算法。该模型从宏观的链路负载分布和单个节点的排队时延两方面来构建NoC映射的时延模型,通过引入时延因子、权重系数来刻画不同映射方案对时延性能的影响,避免了NoC通信时延精确建模的难题。提出近邻随机思想来构建遗传算法的初始种群,并且运用该算法实现了面向时延的NoC映射,在达到全局最优的情况下,比经典遗传算法效率提升将近20%。实验结果表明,该算法优于现有的经典遗传算法和随机映射方案。     

Application mapping to mesh NoCs using a Tabu-search based swarm optimization

A hybrid optimization scheme is presented that combines Tabu-search, communication volume based core swapping and Discrete Particle Swarm Optimization (DPSO) for NoC (Network-on-Chip) mapping. The main goal of the optimization is to map an application core-graph such that the overall communication latency of the NoC is minimal. It is assumed that the target NoC has a 2D-mesh topology. DPSO is used as the main optimization technique where each swarm particle move is influenced by the global and local best, previous visited search space locations, and a deterministic method to reduce communication volume of existing mapping. We employ a Tabu-list to discourage swarm particles to re-visit the explored search space and propose an alternative direction towards the intended movement direction. The methodology is tested for some multimedia applications as well as randomly generated large network of synthetic cores-graphs. For larger applications, our hybrid scheme generates high quality NoC mapping solutions as compared to DPSO based existing techniques.     

可靠电压频率岛感知的异步片上网络能耗优化

针对采用2D-Torus拓扑结构且支持电压频率岛（VFI）的异步片上网络能耗优化问题,提出了具有可靠性的、基于电压频率岛的划分和分配及片上网络任务映射的能耗优化方法．该方法采用递进优化的方式,根据IP核的动态处理能耗,不同电压频率岛之间的转换能耗和可靠性带来的能耗开销定义了IP核在电压频率岛之间移动的阈值函数,并通过对阈值函数进行判断完成电压频率岛的划分和分配,应用基于三元相关性量子粒子群优化算法完成处理单元到资源节点的映射,在映射中考虑保证系统可靠性的通信开销,对异步片上网络系统的可靠性进行优化．实验结果表明,该算法可以在不过多消耗能耗的情况下显著的改善片上网络系统的可靠性,且可有效降低NOC系统的能耗.     

拓扑结构感知的片上网络体系结构应用映射与优化

应用映射是片上网络体系结构研究的关键问题之一,映射结果的好坏会极大地影响体系结构的性能。现有的应用映射方法大多基于特定的网络结构,如2d-mesh、2d-torus等,研究NoC性能或功耗约束的应用映射与优化方法。本文提出了一种拓扑结构感知的基于高层代码转换的片上网络应用映射与优化方法。该方法采用多面体模型对应用的核心循环进行自动并行和局部性优化,并将网络拓扑结构抽象成带权重的有向图,使用该有向图对任务流图进行覆盖,以提高任务的并行性,降低任务间同步和通信开销。实验结果表明,采用优化的映射方法后任务节点间的并行性被充分利用,通信开销降低,整体上提高了片上网络系统性能。     

有向无环图的高效归约算法

将一个应用程序部署到给定的片上网络上执行时,需要将应用程序中的每一个子任务都指派给片上网络中的一个节点执行。该问题一般被建模成一组子任务作为顶点的有向无环图,任务在片上网络上的部署过程就等同于一个有向无环图的顶点向一个片上网络拓扑映射的过程。而随着应用程序和片上网络规模的增大,计算一个最优的映射方案是典型的难解问题。为了加速有向无环图到片上网络拓扑的映射过程,提出了有向无环图的归约算法,使归约后的图中的顶点数量尽可能地与给定片上网络中的节点数量相同。提出的图归约算法可以有效地识别出所有可归约子图,这些可归约子图可被归约为单一顶点。新算法的适用范围从嵌套图扩展到了任意图,并且拥有与原算法相同的复杂度量级。还提出了一种并行化的算法思想来加速可归约子图的搜索过程。     

Evaluation of energy and buffer aware application mapping for networks-on-chip

Networks-on-Chip (NoC) is a communication paradigm for Systems-on-Chip (SoC). NoC design flow contains many problems, one of which is called as application mapping problem, which is generally solved in the literature by considering minimization of the communication energy consumption only. Energy and Buffer Aware Application Mapping (EBAM) is a recently proposed method, which handles the application mapping issue as a joint optimization problem for minimizing the energy consumption and buffer utilization simultaneously. EBAM avoids possible high input loads on router buffers at the early mapping stage by using a priori traffic characteristics of the application. Self similarity is already an accepted model in local and wide area networks and many on-chip applications have also been proven to have self similar characteristics. EBAM therefore employs self similar traffic in its joint optimization process and a genetic algorithm is already proposed for its solution.