先进制程下基于多策略融合的时延优化层分配算法

引入层分配算法能够有效地优化物理设计过程中的时延和通孔数等指标,提高电路性能.为此,提出一种同时考虑非默认规则线和耦合效应的基于多策略融合的时延优化层分配算法.首先针对现有工作对线网差异性考虑不细致的问题,提出线网异化策略;然后针对网格边拥塞情况评估不够合理的问题,提出段分级策略;再对非法线网进行拆线重绕时更注重考虑拥塞约束而导致时延过高的问题,提出重绕调整策略;最后提出多目标驱动排序策略,对布线顺序不够合理的问题设计多种新颖的确定布线顺序的方法.在2.60 GHzCPU和64 GB内存的Linux环境下,使用DAC12基准电路得到的实验结果表明,在保证不发生溢出的情况下,所提算法能够有效地优化时延和通孔数.

基于多阶段优化的高质量总体布线算法

总体布线是VLSI物理设计中关键的一个环节.针对现有总体布线算法的布线容量利用率低和布线结果容易陷入局部最优的问题,提出一种基于多阶段优化的高质量总体布线算法.首先在预连接阶段和全局考量下的布线重组阶段中引入虚拟容量动态调整策略,提高布线容量利用率;然后在布线重组阶段引入布线子区域自适应扩展策略,缩小算法全局搜索的空间,提高算法的布线效率;最后采用A*算法启发式搜索并结合粒子群算法全局搜索的能力,避免算法在布线过程中单一地选择最短路径,陷入局部最优.与现有总体布线算法在ISPD基准电路上的实验结果表明,所提算法的布线结果取得了6.0%~22.8%的线长优化.

采用改进多目标粒子群算法的斜拉桥阻尼器参数优化

为克服大跨度斜拉桥黏滞阻尼器优化设计效率低、多个相互制约的减震控制目标的问题难以权衡,基于遗传算法的“变异”方法,提出了改进多目标粒子群算法来进行阻尼器参数优化设计。建立大跨度斜拉桥的有限元模型,开展了全桥地震响应分析,根据抗震需求在桥梁纵向设置黏滞阻尼器;分别建立了塔底弯矩、阻尼力和梁端位移的减震响应与阻尼器参数之间的响应面数学模型;以减震响应面模型为研究对象,通过该算法进行阻尼器参数全局自动寻优分析,确定了阻尼器的最优参数,并与采用参数敏感性分析方法确定的一组阻尼参数进行对比分析。研究结果表明:该优化方法具有计算精度好、优化效率高和更好地权衡多个相互制约的减震控制目标的优点;通过优化算法获得的阻尼器参数组合相比采用参数敏感性分析方法获得的阻尼参数组合的减震响应,塔底弯矩增大1.73%,阻尼力减小5.97%,梁端位移减小1.66%;在无需多次有限元试算的基础上确定了更高精度的阻尼器优化参数组合,在提高减震效果的同时大大提升了计算效率。

基于混合离散粒子群优化的控制模式分配算法

连续微流控生物芯片是生物化学实验自动化、微型化的革命性技术.多路复用器的控制模式分配作为连续微流控生物芯片自动化设计的关键环节之一,是难的NP(Non-deterministic Polynomial)优化问题.现有工作采用粒子群优化算法求解控制模式分配问题存在过早陷入局部最优解、收敛速度慢以及算法稳定性差的缺点.为此,本文提出一种连续微流控生物芯片下基于混合离散粒子群优化的控制模式分配算法.首先,为了加快算法收敛速度及避免过早陷入局部最优解,提出了离散的自适应区域搜索策略.其次,通过基于样例的社会学习机制提高了算法的稳定性.然后,采用等距抽值的方式筛选出自适应区域搜索策略中重要参数的最佳组合,以进一步提高分配方案的质量.最终实验结果表明,所提算法在多路复用器中阀门使用数量上平均优化了19.01%,在算法稳定性上提高了29.18%,且在现实的生化应用中有良好的性能表现.

基于动态粒子群优化的X结构Steiner最小树算法

Steiner最小树(SMT)是总体布线的最佳连接模型,其构造是1个NP-难问题。粒子群优化(PSO)算法在解决NP-难问题中具有良好的表现,而PSO算法中种群的拓扑结构及搜索信息的传递机制对其性能有着很大的影响。1个适用于具体问题的种群拓扑结构对算法性能的提升极为显著。因此,利用PSO求解总体布线问题需要根据具体布线问题的特性来选择合适的粒子拓扑结构策略,以提升PSO的性能。提出基于动态PSO的X结构Steiner最小树(XSMT)算法以解决总体布线问题。首先,设计动态子群与信息交换策略,对种群进行子群划分,引入信息交换的概念,让子群在保持独立性的同时与其他子群进行信息交换,增加子群多样性;其次,设计粒子学习与变异策略,通过设置子群中粒子的学习对象使子群趋向于全局最优,并选择每个子群中适应度值最好的粒子进行变异,使粒子更易于跳出局部最优;最后,设计从多群局部学习过渡到单群全局学习策略,使算法在迭代次数到达阈值之后从局部学习过渡到全局学习,使得粒子在较优拓扑结构的基础上内部连接以获得更好的线长优化率。实验结果表明,与现有的2种R结构SMT(RSMT)算法相比,所提算法在优化线长方面分别优化了10.25%、8.24%;与现有的3种XSMT算法相比,该算法在优化线长方面分别优化了2.44%、1.46%、0.48%,验证了算法的有效性。

完全可编程阀门阵列生物芯片下容错导向的高阶综合算法

作为新一代流式微流控生物芯片,完全可编程阀门阵列(FPVA)生物芯片具有更高的灵活性和可编程性,已经成为一种流行的生物化学实验平台。然而,由于环境或人为因素,制造过程中通常存在一些物理故障,如通道阻塞和泄漏,这无疑会影响生化检测的结果。此外,高阶综合作为架构综合的首要阶段,其结果的质量直接影响着后续设计的优劣。因此,该文首次研究了FPVA生物芯片高阶综合过程中的容错问题,提出了单元功能转换方法、双向冗余方法、故障映射方法等动态容错技术,为实现高效的容错设计提供了技术保障。通过将这些技术集成到高阶综合设计中,进一步实现了一种高质量的FPVA生物芯片下容错导向的高阶综合算法,包括故障感知的实时绑定策略和故障感知的优先级调度策略,为实现芯片架构的鲁棒性和检测结果的准确性奠定了良好的基础。实验结果显示,所提算法能够得到一个FPVA生物芯片下高质量且容错的高阶综合方案,为后续实现容错物理设计方案提供了有力保障。

基于离散变邻域蜉蝣优化的装配作业车间调度算法

由于受到疫情影响,企业迫切地需要通过升级改造自动化柔性生产线来实现降本增效。在这一背景下,装配作业车间调度问题(Assembly Job Shop Scheduling Problem,AJSSP)再一次成为学术界和企业界的研究热点。AJSSP比普通作业车间调度问题多了一道装配阶段,故其存在前后工序相互制约和多机并行现象,问题求解也更加复杂。针对该问题,提出了一种基于离散变邻域蜉蝣优化算法(Discrete Variable Neighborhood Mayfly Algorithm,D-VNMA)的调度方法,主要工作如下:1)采用符合Lamarkian特性的编码解码机制,实现个体有效信息的迭代继承;2)使用Circle映射融合常见启发式算法初始化蜉蝣种群,保证种群的多样性;3)加入新的邻域探索策略,采用多种不同的邻域结构和搜索策略的差异组合,增加搜索方案的多样性,提高寻找局部最优解的搜索效率;4)提出改进的雌雄蜉蝣交配策略,提高算法全局探索能力,加快算法整体收敛速度。在实验过程中,通过试验设计(Design of Experiment,DOE)方法获得D-VNMA的最佳参数设置,并在不同规格AJSSP算例数据上将D-VNMA和其他算法进行比较。实验结果表明,D-VNMA得到最优解的概率提升了30%,且收敛效率最高可提升62.15%。

求解VLSI布线问题的离散粒子群优化算法

最小矩形Steiner树问题是VLSI布线的一个关键问题,且是一个典型的NP完全问题。为了有效地解决VLSI布线中考虑障碍物的最小矩形Steiner树问题,提出了一种改进的离散粒子群优化算法。考虑到存在障碍物,设计了一个基于惩罚的适应度函数。引入了遗传算法的变异和交叉算子,增加了种群的多样性并适当地扩展了粒子的寻优范围。实验结果表明,算法是有效的,实现简单,且相对遗传算法能更有效迅速地收敛。

基于自适应PSO和混合转换策略的X结构Steiner最小树算法

X结构Steiner最小树(XSMT)是非曼哈顿结构总体布线算法中多端线网的最佳连接模型,属于NP难问题.文中基于混合转换策略和自适应粒子群优化算法,提出XSMT构造算法.首先设计有效的混合转换策略,扩大算法寻优空间,提高算法收敛效率.为了满足粒子编码的健全性,算法的更新方式引入带并查集策略的交叉和变异算子,同时采取自适应调整学习因子的策略,加快粒子群优化算法的收敛速度.实验表明,文中算法能得到较好的XSMT求解方案,获得多种不同拓扑的XSMTs,有利于VLSI总体布线阶段的拥挤度优化.

面向超大规模集成电路物理设计的通孔感知的并行层分配算法

随着集成电路规模的日益增长,需要处理的线网数量显著增多,层分配算法运行时间增大成为限制高效设计布线方案的重要因素;此外在生产工艺中,通孔的制造成本较高.针对以上两个问题,本文提出了两种新颖的策略分别用于优化算法运行时间和通孔数量:(1)一种高效的基于区域划分的并行策略,实现各区域在并行布线阶段负载均衡,以提高并行布线的效率;(2)基于线网等效布线方案感知的通孔优化策略,决定各线网对布线资源使用的优先级,进而减少层分配方案的通孔数量.最终将上述两种策略相结合,提出了一种面向超大规模集成电路物理设计的通孔感知的并行层分配算法.实验结果表明该算法对通孔数量和运行时间均有良好的优化效果.

基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法

Steiner最小树是超大规模集成电路中布线阶段的最佳模型,进一步考虑能够有效防止信号失真的电压转换速率(Slew)约束这一个更为贴近实际芯片设计模型和更具线长优化能力的X结构,首次提出基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法.首先,为了避免频繁的Slew约束计算,提出了高效的预处理策略,并且提出一种能够有效考虑Slew约束的针对性的惩罚机制.其次,为了能够有效求解该离散问题,基于遗传算子重新设计了粒子群优化算法的离散更新机制,并提出一种更适合遗传算子的引脚对编码方式.然后,为了进一步优化布线树的长度,提出一种有效的精炼策略.最终,提出一种混合修正策略以完全满足Slew约束.实验表明,所提算法可完全满足电压转换速率约束并取得同类工作中最佳的布线结果.

WSN中一种新颖的基于预测机制的事件检测容错算法

考虑到无线传感器网络中传感器节点经常部署在恶劣的环境中以及节点自身资源具有有限性,节点在运行的过程中容易产生错误数据,造成漏警和虚警错误,从而影响网络的正常运行.本文提出了一种基于预测机制的事件检测容错算法.首先利用事件的时空关联性对监测区域进行事件检测,对事件是否发生还是节点异常进行准确判断.然后针对错误的数据进行具体分析,当节点出现异常的时候,利用KNN-PSOELM预测机制进行估计,以排除错误数据对融合结果的影响,执行有效的容错算法.因此,准确地区分节点数据的类型,排除错误数据的影响,提高事件检测的准确度.

VLSI中高性能X结构多层总体布线器

X结构带来物理设计诸多性能的提高,该结构的引入和多层工艺的普及,使得总体布线算法更复杂.为此,在XGRouter布线器的基础上,本文设计了三种有效的加强策略,包括:1)增加新类型的布线方式;2)粒子群优化(Particle swarm optimization,PSO)算法与基于新布线代价的迷宫布线的结合;3)初始阶段中预布线容量的缩减策略,继而引入了多层布线模型,简化了XGRouter的整数线性规划模型,最终构建了一种高性能的X结构多层总体布线器,称为ML-XGRouter.在标准测试电路的仿真实验结果表明,ML-XGRouter相对其他各类总体布线器,在多层总体布线中最重要的优化目标|溢出数和线长总代价两个指标上均取得最佳.

X结构下VLSI多层绕障Steiner最小树算法

Steiner最小树作为VLSI布线的基础模型,应进一步考虑到X结构、障碍物、多层等条件,文中基于粒子群优化提出了多层绕障X结构Steiner最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.

考虑总线时序匹配的多策略层分配算法

在总体布线的过程中,层分配阶段通过控制总线线网的层次影响总线的时序匹配效果.为此,提出考虑总线时序匹配的多策略层分配算法.首先基于线网属性的线网优先级策略,针对线网不同属性的特点得到一个兼顾线长和总线偏差的布线顺序;然后基于贪心策略的初始布线策略,每次布线都对正在布线的线网选择当前最短路径,使相同总线内的线网都尽可能等长;最后基于总线线长的局部调整策略对初始的布线结果进行拆线重绕,延长部分线网以缩短其与最长的总线线网之间的线长差距.算法在2.60GHzCPU和64 GB内存的Linux环境下运行,使用ISPD竞赛中提供的测试数据进行算法的有效性验证.实验结果表明,所提算法产生的总线偏差降低了23.5%,能够显著优化总线时序匹配效果.

用于时分复用技术的多阶段协同优化FPGA布线方法

时分复用(Time-Division Multiplexing,TDM)技术被广泛地运用于解决IO瓶颈问题,以提高现场可编程门阵列(Field Programmable Gate Array,FPGA)系统的可布线性,但TDM比率的增大会导致系统时延的显著增加。因此,为了优化FPGA系统时延以及可布线性,该文提出一种用于时分复用技术的多阶段协同优化FPGA布线(Multi-Stage Co-Optimization FPGA Routing,MSCOFRouting)方法。首先,设计自适应布线算法,以减少布线拥塞情况,提高可布线性,解决FPGA间的布线优化问题,为后续的TDM比率分配提供高质量的布线结果。其次,为了避免因大规模线网组的TDM比率过大而导致系统时延劣化的情况,提出基于拉格朗日松弛(Lagrangian Relaxation,LR)的TDM比率分配算法,为布线图的边分配系统时延更小的初始TDM比率。此外,为了进一步减小最大线网组的TDM比率,通过一种多层次的TDM比率优化算法,缩减线网组和FPGA连接对的TDM比率。同时,为了提高MSCOFRouter的运行效率,在上述3个算法中使用多线程并行化方法,有效缩减运行时间。实验结果表明,MSCOFRouting可以获得满足TDM比率约束的结果,取得同类工作中最佳的布线优化结果和TDM比率分配结果。

连续微流控生物芯片下一种多阶段启发式的流层物理协同设计算法

为了提高连续微流控生物芯片(CFMBs)中的流层物理协同设计质量和效率,该文分3阶段实现布局布线协同设计。(1)布局预处理阶段:通过提出的逻辑布局和组件方向布局调整方法,得到组件优异的逻辑位置和逻辑方向。(2)组件映射和包围盒间隙布局调整阶段:基于包围盒策略,把布局预处理结果映射到实际物理设计空间中,并通过包围盒间隙布局调整,获得最佳包围盒间隙。(3)收缩布局调整阶段:基于组件间的连通图关系,提出了沿流通道收缩和多图收缩两种新的布局调整方法。实验结果表明,与现有最佳的启发式算法对比,该文算法在芯片流层整体面积、流通道交叉点数和流通道总长度上分别优化20.22%,54.66%和71.62%,加速比为177.12,显著提升了设计质量和效率。

基于双向长短期记忆网络的共享单车流量预测

近年来,共享单车逐渐成为流行于城市的交通出行手段,过量投放是其目前面临的最大问题,准确预测共享单车流量能有效调节共享单车投放,且能维护城市的交通秩序和形象.考虑到共享单车流量是一种时间序列,当前流量与过去和将来的流量具有密切的联系,本文提出一种基于双向长短期记忆的深度网络模型以预测未来的共享单车流量.该模型的时间步长设置为12,即以过去12个小时的数据作为输入,预测未来一个小时的共享单车流量数据,以此类推,每次向后推移一个小时,从而预测下一个数据.为了验证模型的性能,本文选取人工神经网络,循环神经网络以及长短期记忆网络作为对比模型.实验结果显示,所提出的模型在预测未来的共享单车流量的性能最佳.

非默认规则线技术下基于多策略的时延驱动层分配算法

层分配作为超大规模集成电路物理设计中的关键环节,在决定布线方案的时延起到非常重要作用.为了优化集成电路的时延性能,现有的层分配工作通常注重优化互连时延和通孔数量,但要么未考虑到对线网中时序关键段的分配问题,要么对线网段的时序关键性的表示不够合理,最终使得算法的时延优化不够理想.为此,本文提出一种非默认规则线技术下基于多策略的时延驱动层分配算法,主要包含4种关键策略:(1)提出轨道数感知的层选择策略,增强层分配器为线网段选择合适布线层的能力;(2)提出多指标驱动的初始线网排序策略,综合考虑线长、信号接收器数和可布线轨道资源等多个指标为线网确定层分配优先级,从而获得高质量的初始层分配结果;(3)提出线网段调整策略,通过重绕线网,将时序关键段调整至上层布线层,优化线网时延;(4)提出线网段时延优化策略,对存在溢出线网进行拆线重绕,从而可同时优化时延和溢出数.实验结果表明,本文提出的算法相比于现有的层分配算法能够在时延和通孔数两个指标上均取得最佳,并且保证不产生溢出.

基于混合离散粒子群优化的轨道分配算法

现有的轨道分配工作大多忽略局部线网问题,并且容易陷入局部极值.为此,文中基于离散粒子群优化、遗传操作和基于协商的精炼策略,综合考虑局部线网、重叠冲突、线长和障碍物,提出轨道分配算法.算法抽象局部线网,构建对应的线段模型.为了扩大种群多样性,混合遗传操作以提高全局搜索效率.同时,设计简单高效的适应度函数.最后,使用基于协商的精炼策略进一步减少线段重叠.实验表明文中算法的有效性,该算法可以获得较佳的重叠代价指标优化值,减少关键布线区域的拥挤情况.