基于离散麻雀搜索优化的X结构绕障Steiner最小树算法

doi:10.3778/j.issn.1673-9418.2407017

摘要/Abstract

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

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

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-architecture 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 (DSSA_OAXSMT). Firstly, 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-architecture obstacle-avoiding Steiner minimum tree problem. Secondly, a preprocessing strategy is proposed to avoid redundant calculations. Thirdly, 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. Fourthly, an adjustment strategy based on detours is developed to meet obstacle constraints. Finally, a mixed refinement strategy is proposed, which incorporates a local refinement strategy based on shared edges and an optimization strategy based on crossover detection and handling, enabling further optimization of the wirelength cost. Experimental results show that the proposed algorithm achieves superior wirelength optimization compared with similar works.

Key words: Steiner minimum tree, X-architecture, obstacle-avoiding, discrete sparrow search optimization, very large-scale integration

郑瀚, 周茹平, 刘耿耿. 基于离散麻雀搜索优化的X结构绕障Steiner最小树算法[J]. 计算机科学与探索, 2025, 19(6): 1494-1507.

ZHENG Han, ZHOU Ruping, LIU Genggeng. Discrete Sparrow Search Optimization-Based Obstacle-Avoiding X-architecture Steiner Minimum Tree Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(6): 1494-1507.

参考文献

[1] 刘耿耿, 郭文忠. 超大规模集成电路布线设计理论与算法[M]. 北京: 清华大学出版社, 2022.
LIU G G, GUO W Z. Theory and algorithm for very large scale integration routing[M]. Beijing: Tsinghua University Press, 2022.
[2] VENKATAIAH C, JAYAMMA M, RAO Y M, et al. An advanced technique for performance improvement in VLSI inter-connects[J]. Journal of VLSI Design and Signal Processing, 2023, 9(1): 1-6.
[3] RAZIF R A M, MAHARUM S M M, HASANI A H, et al. Mitigation techniques for crosstalk in ICs[J]. IOP Conference Series: Materials Science and Engineering, 2019, 701(1): 012037.
[4] 刘耿耿, 黄逸飞, 王鑫, 等. 基于混合离散粒子群优化的Slew约束下X结构Steiner最小树算法[J]. 计算机学报, 2021, 44(12): 2542-2559.
LIU G G, HUANG Y F, WANG X, et al. Hybrid discrete particle swarm optimization algorithm for X-architecture Steiner minimal tree construction with slew constraints[J]. Chinese Journal of Computers, 2021, 44(12): 2542-2559.
[5] ZHOU R P, LIU G G, GUO W Z, et al. An X-architecture SMT algorithm based on competitive swarm optimizer[C]//Proceedings of the 2021 International Conference on Web Information Systems and Applications. Cham: Springer, 2021: 393-404.
[6] WARME D M, WINTER P, ZACHARIASEN M. Exact algorithms for plane Steiner tree problems: a computational study[M]//Advances in Steiner trees. Boston: Springer US, 2000: 81-116.
[7] CHU C, WONG Y C. FLUTE: fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(1): 70-83.
[8] LIN S D, KIM D H. Construction of all rectilinear Steiner minimum trees on the hanan grid and its applications to VLSI design[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39(6): 1165-1176.
[9] KHAN A, LAHA S, SARKAR S K. A novel particle swarm optimization approach for VLSI routing[C]//Proceedings of the 2013 3rd IEEE International Advance Computing Conference. Piscataway: IEEE, 2013: 258-262.
[10] JULSTROM B A. A scalable genetic algorithm for the rectilinear Steiner problem[C]//Proceedings of the 2002 Congress on Evolutionary Computation. Piscataway: IEEE, 2002: 1169-1173.
[11] GREENE W A. A tree-based genetic algorithm for building rectilinear Steiner arborescences[C]//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2006: 1179-1186.
[12] AJWANI G, CHU C, MAK W K. FOARS: flute based obstacle-avoiding rectilinear Steiner tree construction[C]//Proceedings of the 2010 International Symposium on Physical Design. New York: ACM, 2010: 27-34.
[13] LI L, YOUNG E F Y. Obstacle-avoiding rectilinear Steiner tree construction[C]//Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design. Piscataway: IEEE, 2008: 523-528.
[14] LIN K W, LIN Y S, LI Y L, et al. A maze routing-based methodology with bounded exploration and path-assessed retracing for constrained multilayer obstacle-avoiding rectilinear Steiner tree construction[J]. ACM Transactions on Design Automation of Electronic Systems, 2018, 23(4): 1-26.
[15] HU Y, JING T, HONG X L, et al. An-OARSMan: obstacle-avoiding routing tree construction with good length performance[C]//Proceedings of the 2005 Asia and South Pacific Design Automation Conference. Piscataway: IEEE, 2005: 7-12.
[16] UTYAMISHEV D, PARTIN-VAISBAND I. Multiterminal pathfinding in practical VLSI systems with deep neural networks[J]. ACM Transactions on Design Automation of Electronic Systems, 2023, 28(4): 1-19.
[17] KUNDU S, ROY S, MUKHERJEE S. An efficient obstacle-avoiding rectilinear Steiner tree construction method using PB-SAT[J]. IETE Journal of Research, 2023, 69(6): 3346-3356.
[18] ZHANG T C, Lü Z P, DING J W. Guiding solution based local search for obstacle-avoiding rectilinear Steiner minimal tree problem[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2024, 8(1): 440-453.
[19] TEIG S. Session details: the X architecture: not your father’s diagonal wiring[C]//Proceedings of the 2002 International Workshop on System-Level Interconnect Prediction. New York: ACM, 2002: 33-37.
[20] COULSTON C S. Constructing exact octagonal Steiner minimal trees[C]//Proceedings of the 13th ACM Great Lakes Symposium on VLSI. New York: ACM, 2003: 1-6.
[21] SAMANTA T, GHOSAL P, RAHAMAN H, et al. A heuristic method for constructing hexagonal Steiner minimal trees for routing in VLSI[C]//Proceedings of the 2006 IEEE International Symposium on Circuits and Systems. Piscataway: IEEE, 2006: 1788-1791.
[22] CHIANG C, CHIANG C S. Octilinear Steiner tree construction[C]//Proceedings of the 2002 45th Midwest Symposium on Circuits and Systems. Piscataway: IEEE, 2002: 603-606.
[23] 张一帆, 宋威. 极限学习决策网络指导的多目标粒子群算法[J]. 计算机科学与探索, 2024, 18(6): 1513-1525.
ZHANG Y F, SONG W. Multi-objective particle swarm optimization algorithm guided by extreme learning decision network[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(6): 1513-1525.
[24] 赵晓妍, 宋威. 聚集度指标引导的注意力学习粒子群优化算法[J]. 计算机科学与探索, 2023, 17(8): 1852-1866.
ZHAO X Y, SONG W. Attention learning particle swarm optimization algorithm guided by aggregation indicator[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(8): 1852-1866.
[25] XIE P, MA B, WANG B, et al. 3D path planning of the solar powered UAV in the urban-mountainous environment with multi-objective and multi-constraint based on the enhanced sparrow search algorithm incorporating the Levy flight strategy[J]. Guidance, Navigation and Control, 2024, 4(1):2450005.
[26] LI Z, GUO J, GAO X, et al. A multi-strategy improved sparrow search algorithm of large-scale refrigeration system: optimal loading distribution of chillers[J]. Applied Energy, 2023, 349: 121623.
[27] MA X, LIU Q. An artificial fish swarm algorithm for Steiner tree problem[C]//Proceedings of the 2009 IEEE International Conference on Fuzzy Systems. Piscataway: IEEE, 2009: 59-63.
[28] LIU G G, CHEN G L, GUO W Z. DPSO based octagonal Steiner tree algorithm for VLSI routing[C]//Proceedings of the 2012 IEEE 5th International Conference on Advanced Computational Intelligence. Piscataway: IEEE, 2012: 383-387.
[29] HUANG X, LIU G G, GUO W Z, et al. Obstacle-avoiding algorithm in X-architecture based on discrete particle swarm optimization for VLSI design[J]. ACM Transactions on Design Automation of Electronic Systems, 2015, 20(2): 1-28.
[30] HUANG X, GUO W Z, LIU G G, et al. FH-OAOS[J]. ACM Transactions on Design Automation of Electronic Systems, 2016, 21(3): 1-31.
[31] LIU G G, YANG L L, XU S J, et al. X-architecture Steiner minimal tree algorithm based on multi-strategy optimization discrete differential evolution[J]. PeerJ Computer Science, 2021, 7: e473.
[32] LIU G G, CHEN X H, ZHOU R P, et al. Social learning discrete particle swarm optimization based two-stage X-routing for IC design under intelligent edge computing architecture[J]. Applied Soft Computing, 2021, 104: 107215.
[33] XUE J K, SHEN B. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.
[34] FEO T A, RESENDE M G C. Greedy randomized adaptive search procedures[J]. Journal of Global Optimization, 1995, 6(2): 109-133.
[35] LIU G G, ZHU Y H, XU S J, et al. Performance-driven X-architecture routing algorithm for artificial intelligence chip design in smart manufacturing[J]. ACM Transactions on Management Information Systems, 2022, 13(4): 1-20.
[36] LIU G G, ZHU Y H, XU S J, et al. PSO-based power-driven X-routing algorithm in semiconductor design for predictive intelligence of IoT applications[J]. Applied Soft Computing, 2022, 114: 108114.