X结构下考虑障碍内布线的Steiner树构建方法

摘要

本发明涉及一种X结构下考虑障碍内布线的Steiner树构建方法，包括以下步骤：步骤S1:初始化粒子群，其中每个粒子表示一个连接所有给定引脚的X结构Steiner树；步骤S2:对粒子群进行预处理，生成包含所有粒子的任意两个引脚之间的所有连接信息的查找表；步骤S3:粒子群飞行，并通过变异策略，交叉策略以及粒子适应值函数迭代,得到优秀粒子;步骤S4:对得到的优秀粒子继续调整，引入障碍物角点为Pseudo‑Steiner点的调整策略，确保所有边在障碍内的连通分量长度都不超过门限值L，得到调整后的优秀粒子；步骤S5:对调整后的优秀粒子进行进一步的精炼，得到最优粒子，即最优的X结构Steiner树。本发明能够充分利用障碍内资源进行布线，显著缩短了总布线长度。