考虑布线资源松弛的X结构Steiner最小树算法

为了进一步考虑X结构,并充分利用障碍内可用布线资源,文中提出考虑布线资源松弛的X结构Steiner最小树算法.为了能够求解离散问题,在粒子的更新操作中引入交叉算子和变异算子.通过构建查找表,为整个算法流程提供快速的信息查询.提出角点选取策略,通过引入一些障碍角点,使粒子满足约束.最后构建精炼策略,进一步提高最终布线树的质量.实验表明,文中算法充分利用障碍内可用布线资源,有效缩短总布线长度,取得较佳的总布线长度.

X-architecture Steiner Minimum Tree Algorithm Considering Routing Resource Relaxation

To further study X-architecture and make full use of routing resources within the obstacle, an X-architecture Steiner minimum tree algorithm considering routing resource relaxation is proposed in this paper. Firstly, crossover and mutation operators are introduced in the update operation of particles to solve the discretization problem. Secondly, look-up tables are presented for the whole algorithm process to provide a fast information query. Thirdly, a corner point selection strategy is proposed to introduce some obstacle corner points and satisfy the constraints. Finally, a refinement strategy is implemented to further improve the quality of the final routing tree. Experimental results show that the proposed algorithm makes full use of the routing resources within the obstacle, shortens the total wirelength effectively and achieves a better total wirelength.