中文摘要：

Steiner最小树作为VLSI布线的基础模型,应进一步考虑到X结构、障碍物、多层等条件,文中基于粒子群优化提出了多层绕障X结构Steiner最小树算法.首先引入边变换操作以改变布线树的拓扑,使其具有较强的绕障能力;为了避免边变换操作带来的布线树环路问题,结合并查集策略设计新的操作算子;为了保证布线边不违反约束,提出一个与绕障情况及通孔数相关的惩罚函数策略,从而优化了多层布线中布线总代价这一最重要的目标.实验结果表明,相对于同类算法,该算法在布线总代价的优化能力上是最强的.

英文摘要：

Steiner minimal tree is a fundamental model in VLSI routing. Further considering X-architecture, the presence of obstacles, and the requirements of multilayer routing, this paper presented an efficient algorithm based on particle swarm optimization for constructing the multilayer obstacle-avoiding X-architecture Steiner minimal tree. Edge transformation was designed to make the particles have the greater ability to change the topology of the routing tree and avoided the obstacles. The new operators combined with union-find set were designed to prevent the generation of the loops. In order to avoid obstacle and discourage the generation of vias, the penalty function related to obstacle-avoiding and vias was proposed. The proposed algorithm finally optimizes the total cost of routing tree which is the most important optimization target of the multilayer routing. The experimental results show that, the proposed algorithm is effective and superior to state-of-the-art multilayer routing algorithms on the total cost.