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

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

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

现有约束多目标进化算法的约束处理策略无法有效解决具有大型不可行区域的问题,导致种群停滞在不可行区域的边缘;此外,约束条件下的不连续问题对算法的全局搜索能力以及多样性的维持提出了更高的要求。针对上述问题,提出了一种基于多阶段搜索的约束多目标进化算法(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在处理不连续以及具有多模态性质的约束多目标问题时具有明显优势。