用于时分复用技术的多阶段协同优化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比率分配结果。

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

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

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

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

考虑流端口数量约束下的连续微流控生物芯片流路径规划算法

连续微流控生物芯片通常需要构建复杂交错的流路径来支持样本/试剂的运输,也需要大量的流端口来推动液体的有序流动,这阻碍了生物芯片的进一步发展。因此,该文考虑了有限流端口驱动下的流路径规划问题,并提出一个流路径驱动下的连续微流控生物芯片的架构综合设计流程。首先采用基于列表调度算法实现操作的绑定与调度,通过时间窗对调度进行调整,从而满足给定的流端口数量约束;然后采用基于序列对表示的遗传算法求得芯片的布局设计,通过考虑并行任务之间的冲突以及组件之间的连接关系,进一步优化了布局解的质量;最后采用基于A^(*)寻路的优化布线算法规划所需的流路径,以有效减少流通道总长度和交叉点数量,生成具有高执行效率的芯片架构。实验结果表明,该方法在严格满足给定的流端口数量约束条件下,极大地避免了各种液体运输任务的冲突,同时也优化了流通道的总长度以及交叉点的数量,降低了芯片的构造成本。

基于多阶段搜索的约束多目标进化算法

现有约束多目标进化算法的约束处理策略无法有效解决具有大型不可行区域的问题,导致种群停滞在不可行区域的边缘;此外,约束条件下的不连续问题对算法的全局搜索能力以及多样性的维持提出了更高的要求。针对上述问题,提出了一种基于多阶段搜索的约束多目标进化算法(CMOEA-MSS),在该算法的3个阶段采用不同的搜索策略。为使种群快速穿越大型不可行区域并逼近Pareto前沿,所提算法在第一阶段不考虑约束条件,利用一种收敛性指标引导种群搜索;在第二阶段采用一组均匀分布的权重向量来维持种群的多样性,并提出一种改进的epsilon约束处理策略,以保留不可行区域中的高质量解;在第三阶段采用约束优先原则,将搜索偏好集中在可行区域以保证最终解集的可行性。CMOEA-MSS与NSGA-Ⅱ+ARSBX(Nondominated Sorting Genetic Algorithm Ⅱ using Adaptive Rotation-based Simulated Binary crossover)等算法在MW和DASCMOP测试集上对比的结果表明:在MW测试集上,CMOEA-MSS在7个测试问题上获得了最好的IGD(Inverted Generational Distance)值,在5个测试问题上获得了最好的HV(HyperVolume)值;在DASCMOP测试集上,CMOEA-MSS在3个测试问题上获得了最好的IGD值,在2个测试问题上取得了次好的IGD值,在5个测试问题上获得了最好的HV值。可见,CMOEA-MSS在处理不连续以及具有多模态性质的约束多目标问题时具有明显优势。

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

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

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

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

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

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

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最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.

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

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

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

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

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

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

一种面向云环境虚拟机部署的粒子群优化策略

随着数据中心规模的扩大,提升资源利用率的问题日益凸显.如何合理部署虚拟机到数据中心的物理机上是提升数据中心资源利用率的关键问题之一.首先提出相应的资源利用率和响应时间模型,并提出一种结合变异算子的多目标粒子群优化算法(Multi-Objective Particle Swarm Optimization with Mutation Operator,MOPSOM)用于解决虚拟机部署问题.该算法以提高资源利用率和减少响应时间为优化目标,采用线性递减惯性权重寻找最优的虚拟机分配方案.仿真实验结果表明,MOPSOM能够在减小响应时间下提高资源利用率,同时在负载均衡度和能耗之间达到了更好的平衡.

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

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

类别不平衡的通信基站空调故障诊断

为提高通信基站空调故障诊断的准确率,特别是小类样本故障的识别率,本文针对类别不平衡的数据集提出一种单隐层前馈多标签分类算法SLF-CIB.首先在特征空间的低秩假设上构建单隐层前馈神经网络.其次,在最小化误差损失阶段引入非对称阶式损失函数替代平方误差损失函数,通过截断参数和边界参数动态改善类别不平衡问题.根据SLF-CIB模型在训练过程的每一轮迭代的凸特性,应用交替方向乘子方法进行优化.测试过程中多标签输出层可提供故障源偏序向量为软故障的早期排查提供多维度的参考.在UCI标准数据集和通信基站空调数据集上的实验表明,SLF-CIB算法有效地提高了故障诊断精度特别是少数类的识别率.

八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长.使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优.实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.

不同手术方式对腰椎退行性疾病的疗效

目的不同手术方式对腰椎退行性疾病的疗效及对其炎症指标和预后的影响。方法选取2020年10月至2022年7月周口骨科医院收治的72例腰椎退行性疾病患者,根据术式分为两组。研究组患者40例,接受斜外侧腰椎椎间融合术(OLIF)手术治疗,对照组患者32例,接受微创经皮椎管减压后外侧融合手术(mis-PLIF)手术治疗,比较两组患者的临床疗效等差异。结果研究组围手术期指标优于对照组(P<0.05);术前两组的炎症指标比较差异无统计学意义(P>0.05),术后两组炎症指标均较术前降低,且研究组低于对照组(P<0.05);与术前比较,术后两组患者的椎间隙前缘、后缘高度增加,研究组术后的椎间隙前缘高度高于对照组(P<0.05);术前两组椎管矢状径比较差异无统计学意义(P>0.05),术后两组的椎管矢状径均较术前增加,且研究组低于对照组(P<0.05);术前两组视觉模拟评分法(VAS)评分及Oswestry功能障碍指数(ODI)比较差异无统计学意义(P>0.05),术后两组VAS评分及ODI均降低,且研究组低于对照组(P<0.05)。结论OLIF治疗腰椎退行性疾病的效果更佳,值得临床推广应用,但应严格掌握其手术适应证。

一种云环境下的主机负载预测方法

云计算是一种基于信息网络的计算模式和服务模式,它将信息技术资源以服务方式动态、弹性地提供给用户,使用户可以按需使用。由于受到主机的启动时间、资源分配时间以及任务调度时间等因素的影响,在云环境下提供给用户的服务存在时延问题。因此,工作负载预测是云环境下一种重要的能源优化的方式。此外,由于云中工作负载的变化具有十分大的波动性,因此增加了预测模型的预测难度。提出了一种基于自回归模型和Elman神经网络的预测模型(Hybrid Auto Regressive Moving Average model and Elman neural network,HARMA-E),其使用ARMA模型进行预测,再使用ENN模型对ARMA模型的误差进行预测,通过修正ARMA的输出值得到最终的预测值。仿真实验结果表明,该预测模型能够较好地提升主机负载预测值的准确度。