一种考虑布线资源松弛的X结构Steiner最小树构造方法

摘要

本发明涉及一种考虑布线资源松弛的X结构Steiner树构造方法，在传统的直角Steiner树的基础上，设计了5种有效的加强策略，包括（1）改变了传统布线结构，增加新的布线方向；（2）限制Steiner树在障碍中的布线长度，充分利用了障碍内可布线资源；（3）使用了一种结合经典遗传算子的特殊粒子群优化算法；（4）建立了为整个算法流程提供快速信息查询的查找表，（5）设计了角点选取和精炼两个启发式策略，以进一步提高布线树的质量。在标准测试电路的仿真实验中表明，考虑布线资源松弛的X结构Steiner树构造方法相较于同类算法，充分利用了障碍内可布线资源，有效缩短了总布线长度，取得最佳的总布线长度。