论文部分内容阅读
随着集成电路规模不断增加,集成度不断提高,芯片特征尺寸不断减小,势不可挡的集成电路发展趋势,导致片上互连线长度越来越长,分布越来越密集,占用面积越来越大,布线工作越来越复杂,此外,片上开关速度也在不断加快。以上诸多因素使得互连线带来的时延占整个芯片时延的60%以上[2],对芯片性能产生严重影响。互连线效应成为集成电路性能的瓶颈,高效精准的布线是提高电路性能的关键。布线环节中,全局布线(Global Routing)是详细布线(Detailed Routing)的基础,从宏观角度保证布线结果的可行性、合理性、连通性和优良性。全局布线方法的优劣直接对整个布线过程乃至芯片性能产生巨大影响,是物理设计(Physical Design)阶段极为重要的环节。传统全局布线方法无法适应超大规模集成电路(Very Large Scale Integration,简称VLSI)布线问题,从可计算角度来看传统方法在VLSI环境下不可行。基于启发式智能优化算法的全局布线策略能够在一定时限内找到满足需要的全局最优或极优解,是解决VLSI布线的有效方法。粒子群优化算法(Particle Swarm Optimization,简称PSO)是基于群智能(Swarm Intelligence)理论的随机优化算法,是一种新型启发式算法。该算法参数设置简单,鲁棒性强,易于实现,具有全局寻优和快速收敛的特点。为提高算法性能,PSO改进算法层出不穷,以适用于不同工程领域。本文以设计高效精准的全局布线策略为研究目标,深入广泛的探讨了目前提出的全局布线方法及存在问题；深入研究PSO算法工作机理,分析算法改进方式,提出可根据优化问题特征自适应调整算法收敛速度和寻优能力的改进PSO算法,提出适用于VLSI布线问题的带变异机制改进离散PSO算法,为多端点线网构造最小矩形斯坦纳树(Minimum Rectangular Steiner Tree,简称MRST),再以并行方式为整个电路实现全局互连。本文主要研究工作及创新点如下：(1)提出基于惯性权值自适应调整的粒子群优化算法(SAW-PSO)。本文深入研究PSO算法中惯性权值及其他参数对算法性能的影响,为粒子赋予各自的惯性权值,该惯性权值是关于粒子适应度、种群规模及搜索解空间维度的函数,以便更好的控制粒子全局搜索能力和局部搜索能力,起到加快算法收敛,防止早熟,提高全局搜索能力的目的。(2)提出基于加速系数自适应调整的粒子群优化算法(SAC-PSO)。本文深入研究PSO算法中加速系数及其他各参数对算法性能的影响,为粒子根据自身适应度值调整加速系数,该加速系数是关于粒子适应度的函数,从而更好的控制粒子全局搜索能力和局部搜索能,提高算法的全局搜索能力,并加快算法收敛速度。(3)提出将带变异机制的改进离散PSO算法应用于VLSI多端点线网全局布线(MDPSO-RA)。通过对粒子编码,定义各操作,算法能够在一定时限内为多端点线网构造最小矩形斯坦纳树,实验表明,该算法能够更加快速精准的为多端点线网构建最小矩形斯坦纳树或近似最小矩形斯坦纳树。(4)提出基于带变异机制的改进离散PSO算法的并行全局布线方法(MDPSO-GR),结合遗传算法变异操作及离散PSO算法特点,对粒子重新编码、定义各操作、调整参数,在满足一定约束条件下,以并行方式为全局线网寻找全局最优或近似最优布线解,从而实现整个电路互连。采用标准测试函数对SAW-PSO和SAC-PSO算法进行测试,实验表明,该算法具有匀速收敛,防止早熟,快速寻优等特点；通过对MCNC和GSRC标准电路测试,实验表明,基于改进离散PSO算法的两阶段全局布线策略能快速为VLSI全局线网并行布线,并得到好的全局布线解。