Abstract: The Steiner minimum tree is the optimal connection model for solving the routing problem of Very Large-Scale Integration. However, modern chips often contain various obstacles, such as macro cells and IP blocks, making the construction of Steiner minimum trees more challenging. Moreover, considering the excellent wirelength optimization capabilities of X-structure routing and the promising application of the sparrow search algorithm in solving NP-hard problems, this paper proposes a discrete sparrow search optimization-based X-architecture obstacle-avoiding Steiner minimal tree algorithm. First, a sparrow representation method based on edge-point pairs and an efficient fitness calculation method are proposed, coupled with a sparrow population update mechanism based on discrete mutation and crossover operations, which address the discrete X-structure obstacle-avoiding Steiner minimum tree problem. Second, a preprocessing strategy is proposed to avoid redundant calculations. Third, a hybrid initialization strategy is introduced, which combines the greedy approach and the roulette wheel selection method to enhance the diversity of the initial population. Fourth, an adjustment strategy based on detours is developed to meet obstacle constraints. Finally, a mixed refinement strategy is proposed to further minimize the wirelength cost. Experimental results show that the proposed algorithm achieves superior wirelength optimization compared to similar works.

Key words: Steiner minimum tree, X-architecture, obstacle-avoiding, discrete sparrow search optimization, VLSI

摘要： Steiner最小树是求解超大规模集成电路布线问题的最佳连接模型. 然而, 现代芯片中往往存在各种障碍, 如宏单元、IP块等, 这些障碍使得Steiner最小树的构建更为困难. 同时, 考虑到X结构布线具有的良好的线长优化能力以及麻雀搜索算法在求解NP难问题上展现出良好的应用前景, 本文提出了一种基于离散麻雀搜索优化的X结构绕障Steiner最小树算法. 首先, 设计了基于边点对编码的麻雀表示方法与有效的适应度计算方法,以及一种基于离散化变异与交叉运算的麻雀种群更新机制, 能够有效解决离散化的X结构绕障Steiner最小树问题. 其次, 提出了一种预处理策略, 避免了障碍信息的重复计算, 提高了算法的运行效率. 再次, 提出了一种混合初始化策略, 通过结合贪心思想和轮盘赌思想提高初始种群的多样性. 接着, 提出了一种基于绕行的调整策略以满足障碍约束. 最后, 提出了一种混合精炼策略, 其中包含基于公共边的局部精炼策略与基于交叉检测与处理的优化策略, 能够进一步优化线长代价. 实验结果表明, 本文所提算法相比于同类工作取得了更佳的线长优化能力.

关键词: Steiner最小树, X结构, 绕障, 离散麻雀搜索优化, 超大规模集成电路