粒子群优化的集成电路多端点线网全局布线方法

集成电路(IC)规模激增,从可计算角度上来看,基于传统图论的全局布线方法对解决多端点线网的布线问题已不可行.针对多端点线网互连问题重新建模,设计了新型的构建最小矩形斯坦纳树方法,提出了一种带变异机制的基于改进离散粒子群优化算法的多端点线网全局布线方法(MDPSO—RA).该方法重新设计了粒子群编码及算法的相关操作,在粒子群优化算法全局寻优、快速收敛的基础上,引入遗传算法变异机制,提高了算法性能.实验结果表明,本方法具有全局寻优能力、鲁棒性强等特点,可在时限内,快速得到最优或近似最优多端点线网布线方案.

改进的Prim启发式算法在VLSI布线中的应用

总体布线在超大规模集成电路的设计中有着举足轻重的作用.为了寻求总体布线图的最优斯坦纳树,改进了普里姆(Prim)算法,提出了一种基于改进的普里姆启发式算法寻求最小矩形斯坦纳树(RST)的方法,不同于以往的先求最小生成树(MST)然后再把树的边矩形化的方法;同时考虑到时延在深亚微米、超深亚微米阶段的重要影响,在算法中又加入了总体布线设计时的时延要求,最后通过仿真实例验证了算法的可行性.