中文摘要：

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

英文摘要：

With the dramatic increase of integrated circuit scale ,the traditional global routing methods have become infeasible from the computability point of view .In this paper ,the multi-terminal net routing problem is remodeled , a novel method for minimal rectangle Steiner tree construction is proposed , and a discrete particle swarm optimization with mutation to resolving minimum rectangular Steiner tree in very large scale integration global routing is presented （MDPSO -RA in short） .In the improved discrete particle swarm optimization algorithm ,a special encoding and several updating operations are adopted respectively and the mutation of genetic algorithm was introduced to improve the performance of particle swarm optimization on the foundation of its global optimization and fast convergence .The experimental results show that this method has the features of fast global optimization and great robustness ,and it could fast get the optimal or approximate optimal multi-terminal interconnect topology within certain time .