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

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

三维片上网络研究综述

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

一种基于约束优化的虚拟网络映射方法

虚拟网络映射问题将不同的虚拟网络应用映射到相同的基础设施网络中,这是一个极具挑战性的问题.针对该问题,提出了一种基于约束优化的虚拟网络映射方法,将映射问题分解为节点映射和链路映射两个阶段,其中,前者是将虚拟节点映射到物理节点上,后者将虚拟链路映射到物理路径上,它们都是NP难问题.针对节点映射和链路映射分别提出了node-mapping算法和link-mapping算法.node-mapping算法基于贪婪算法的思想,映射时考虑了物理节点所能提供的资源数量以及物理节点间距离两个因素,该算法能够保证基础设施网络中各节点间的负载相对均衡;同时,通过采用访问控制机制,过滤一些异常的虚拟网络请求,能够有效地提高资源的使用效率.link-mapping算法基于人工智能领域中的分布式约束优化思想,其能够保证得到的解是全局最优的,即映射链路的代价最小.最后,通过模拟实验对该方法进行验证,实验结果表明该方法在求解虚拟网络映射问题时的性能良好.     

基于多目标粒子群优化的虚拟网络映射算法

在虚拟网络映射中,多数研究只考虑一个映射目标,不能体现多方的利益。为此,将多目标算法和粒子群算法结合,提出了一种基于多目标粒子群优化（PSO）的虚拟网络映射算法（VNE-MOPSO）。首先,在基本的粒子群算法中引入交叉算子,扩大了种群优化的搜索空间;其次,在多目标优化算法中引入非支配排序、拥挤距离排序,从而加快种群的收敛;最后,以同时最小化成本和节点负载均衡度为虚拟网络映射目标函数,采用多目标粒子群优化算法求解虚拟网络映射问题（VNMP）。实验结果表明,采用该算法求解虚拟网络映射问题,在网络请求接受率、平均成本、平均节点负载均衡度、基础设施提供商的收益等方面具有优势。     

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

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

胖树型片上网络的低能耗映射算法

为解决胖树型片上网络的映射问题,针对该网络不同层路由器间链路长度不同的特点,提出一种低能耗映射优化模型,并设计一种基于捕食搜索策略的差分进化算法(PSDE)进行模型求解.该算法将捕食搜索策略与差分进化算法相结合,弥补了差分进化算法易陷入局部最优的不足,增强了捕食搜索策略的局部搜索能力.仿真实验结果表明,与遗传算法和模拟退火算法相比,PSDE可以缩短运行时间,并获得低能耗、高质量的优化映射结果.     

基于Logistic映射的蜉蝣优化算法

在高维复杂问题上,蜉蝣优化算法存在易陷入局部最优区域且求解精度较差等问题,因而提出基于Logistic映射的蜉蝣优化算法.引入依据Logistic映射的混沌机制,当种群进化停滞时,当前最优蜉蝣通过混沌机制寻找适应度更好的蜉蝣,以激发种群进化能力;建立较劣蜉蝣加速进化机制,激励蜉蝣个体以达到种群寻优要求;采用动态惯性权重均衡算法全局和局部的搜索性能.抽取5个benchmark函数测试算法性能,实验结果验证了所提算法在寻优性能上的有效性.     

二次改进遗传算法与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低功耗映射算法,并对该映射算法进行了仿真实验.实验结果表明,在种群规模较大的条件下,该算法不仅能够继续降低功耗,而且能够大幅度地减少映射算法的运行时间.     

求解约束优化问题的改进灰狼优化算法

针对基本灰狼优化(GWO)算法存在求解精度低、收敛速度慢、局部搜索能力差的问题,提出一种改进灰狼优化(IGWO)算法用于求解约束优化问题。该算法采用非固定多段映射罚函数法处理约束条件,将原约束优化问题转化为无约束优化问题,然后利用IGWO算法对转换后的无约束优化问题进行求解。在IGWO算法中,引入佳点集理论生成初始种群,为算法全局搜索奠定基础;为了提高局部搜索能力和加快收敛,对当前最优灰狼个体执行Powell局部搜索。采用几个标准约束优化测试问题进行仿真实验,结果表明该算法不仅克服了基本GWO的缺点,而且性能优于差分进化和粒子群优化算法。     

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

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