基于动态粒子群优化的X结构Steiner最小树算法

doi:10.19678/j.issn.1000-3428.0068408

摘要/Abstract

摘要：

Steiner最小树(SMT)是总体布线的最佳连接模型, 其构造是1个NP-难问题。粒子群优化(PSO)算法在解决NP-难问题中具有良好的表现, 而PSO算法中种群的拓扑结构及搜索信息的传递机制对其性能有着很大的影响。1个适用于具体问题的种群拓扑结构对算法性能的提升极为显著。因此, 利用PSO求解总体布线问题需要根据具体布线问题的特性来选择合适的粒子拓扑结构策略, 以提升PSO的性能。提出基于动态PSO的X结构Steiner最小树(XSMT) 算法以解决总体布线问题。首先, 设计动态子群与信息交换策略, 对种群进行子群划分, 引入信息交换的概念, 让子群在保持独立性的同时与其他子群进行信息交换, 增加子群多样性; 其次, 设计粒子学习与变异策略, 通过设置子群中粒子的学习对象使子群趋向于全局最优, 并选择每个子群中适应度值最好的粒子进行变异, 使粒子更易于跳出局部最优; 最后, 设计从多群局部学习过渡到单群全局学习策略, 使算法在迭代次数到达阈值之后从局部学习过渡到全局学习, 使得粒子在较优拓扑结构的基础上内部连接以获得更好的线长优化率。实验结果表明, 与现有的2种R结构SMT(RSMT)算法相比, 所提算法在优化线长方面分别优化了10.25%、8.24%;与现有的3种XSMT算法相比, 该算法在优化线长方面分别优化了2.44%、1.46%、0.48%, 验证了算法的有效性。

关键词: 动态粒子群优化, 信息交换, X结构Steiner最小树, 超大规模集成电路布线, 粒子群优化离散化

Abstract:

The Steiner Minimum Tree (SMT) is the best connection model for global routing; its construction is an NP-hard problem. The Particle Swarm Optimization (PSO) algorithm performs well on solving NP-hard problems. The topological structure of the population and the transmission mechanism of search information in the PSO algorithm significantly influence its performance. A population topology structure suitable for specific problems significantly improves the algorithm performance. Therefore, using PSO to solve the overall routing problem requires the selection of an appropriate particle topology strategy based on the characteristics of the specific routing problem to improve PSO performance. Therefore, an X-architecture SMT (XSMT) algorithm based on the dynamic PSO is proposed herein, to solve the overall routing problem. First, a dynamic subgroup and information exchange strategy is designed to divide the population into subgroups, and the information exchange concept is introduced to enable subgroups to exchange information with other subgroups while maintaining their independence, thus increasing subgroup diversity. Second, a particle learning and mutation strategy is designed. By setting the learning objects of particles in the subgroup, the subgroup tends toward the global optimum, and particles with the best adaptation value in each subgroup are selected for mutation such that they can jump out of the local optimum in a more straightforward manner. Finally, a transition strategy from multi-group local learning to single-group global learning is designed to ensure the algorithm transitions from local to global learning after the number of iterations reaches a certain threshold. The particles are internally connected based on an excellent topological structure to obtain an improved routing length optimization rate. Experimental results demonstrate that compared with two existing R-architecture SMT (RSMT) algorithms, the proposed algorithm achieves 10.25% and 8.24% optimization in terms of routing length, respectively. Similarly, compared with three existing XSMT algorithms, the proposed algorithm achieves 2.44%, 1.46%, and 0.48% optimizations regarding routing length. This confirms the effectiveness of the proposed algorithm.

Key words: dynamic Particle Swarm Optimization(PSO), information exchange, X-architecture Steiner Minimum Tree(XSMT), Very Large Scale Integration circuit (VLSI) routing, Discretization of Particle Swarm Optimization(DPSO)

王景熠, 朱予涵, 周茹平, 刘耿耿. 基于动态粒子群优化的X结构Steiner最小树算法[J]. 计算机工程, 2024, 50(9): 226-234.

WANG Jingyi, ZHU Yuhan, ZHOU Ruping, LIU Genggeng. X-Architecture Steiner Minimum Tree Algorithm Based on Dynamic Particle Swarm Optimization[J]. Computer Engineering, 2024, 50(9): 226-234.

https://www.ecice06.com/CN/Y2024/V50/I9/226

图/表 11

图1 X结构的互连线模型

Fig.1 Interconnect model of X-architecture

图2 标准粒子群优化算法流程

Fig.2 Procedure of standard particle swarm optimization algorithm

图3 已初始化的X结构的Steiner最小树

Fig.3 The initialized X-architecture Steiner minimum tree

图4 粒子的两两交换示意图

Fig.4 Schematic diagram of pairwise exchange of particles

图5 普通粒子和子群最优粒子的学习方向

Fig.5 The learning direction of ordinary particles and subgroup optimum particles

图6 从多群局部学习过渡到单群全局学习示意图

Fig.6 Schematic diagram of transition from multi-group local learning to single-group global learning

参考文献 25

1	刘耿耿, 郭文忠. 超大规模集成电路布线设计理论与算法. 北京: 清华大学出版社, 2022.
	LIU G G, GUO W Z. Theory and algorithm for very large scale integration routing. Beijing: Tsinghua University Press, 2022.
2	屈通, 盖天洋, 王书涵, 等. VLSI详细布线算法研究进展. 微电子学与计算机, 2021, 38 (11): 1- 6. doi: 10.3969/j.issn.1000-7180.2021.11.wdzxyjsj202111001
	QU T, GAI T Y, WANG S H, et al. Research progress of VLSI detailed routing algorithm. Microelectronics & Computer, 2021, 38 (11): 1- 6. doi: 10.3969/j.issn.1000-7180.2021.11.wdzxyjsj202111001
3	刘耿耿, 陈志盛, 郭文忠, 等. 基于自适应PSO和混合转换策略的X结构Steiner最小树算法. 模式识别与人工智能, 2018, 31 (5): 398- 408. URL
	LIU G G, CHEN Z S, GUO W Z, et al. Self-adapting PSO algorithm with efficient hybrid transformation strategy for X-architecture Steiner minimal tree construction algorithm. Pattern Recognition and Artificial Intelligence, 2018, 31 (5): 398- 408. URL
4	HOUSSEIN E H, GAD A G, HUSSAIN K, et al. Major advances in particle swarm optimization: theory, analysis, and application. Swarm and Evolutionary Computation, 2021, 63, 100868. doi: 10.1016/j.swevo.2021.100868
5	刘耿耿, 郭文忠, 陈国龙. X结构下VLSI多层绕障Steiner最小树算法. 计算机辅助设计与图形学学报, 2015, 27 (3): 523- 532. URL
	LIU G G, GUO W Z, CHEN G L. VLSI multilayer obstacle-avoiding Steiner minimal tree construction algorithms in X-architecture. Journal of Computer-Aided Design & Computer Graphics, 2015, 27 (3): 523- 532. URL
6	KAHNG A B, MANDOIU I I, ZELIKOVSKY A Z. Highly scalable algorithms for rectilinear and octilinear Steiner trees[C]//Proceedings of the ASP-DAC Asia and South Pacific Design Automation Conference. Washington D. C., USA: IEEE Press, 2003: 827-833.
7	CHU C, WONG Y C. FLUTE: fast lookup table based rectilinear Steiner minimal tree algorithm for VLSI design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27 (1): 70- 83. doi: 10.1109/TCAD.2007.907068
8	WONG Y C, CHU C. A scalable and accurate rectilinear Steiner minimal tree algorithm[C]//Proceedings of the IEEE International Symposium on VLSI Design, Automation and Test (VLSI-DAT). Washington D. C., USA: IEEE Press, 2008: 29-34.
9	CHIANG C, CHIANG C S. Octilinear Steiner tree construction[C]//Proceedings of the 45th Midwest Symposium on Circuits and Systems. Washington D. C., USA: IEEE Press, 2003: 1-10.
10	LIU G G, ZHU W D, XU S J, et al. Efficient VLSI routing algorithm employing novel discrete PSO and multi-stage transformation. Journal of Ambient Intelligence and Humanized Computing, 2020, 13, 1- 16.
11	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. PeerJ Computer Science, 2021, 7, e473. doi: 10.7717/peerj-cs.473
12	COULSTON C S. Constructing exact octagonal Steiner minimal trees[C]//Proceedings of the 13th ACM Great Lakes Symposium on VLSI. New York, USA: ACM Press, 2003: 1-6.
13	CLERC M, KENNEDY J. The particle swarm-explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 2002, 6 (1): 58- 73. doi: 10.1109/4235.985692
14	RATNAWEERA A, HALGAMUGE S K, WATSON H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 2004, 8 (3): 240- 255. doi: 10.1109/TEVC.2004.826071
15	ZHAN Z H, ZHANG J, LI Y, et al. Adaptive particle swarm optimization. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39 (6): 1362- 1381. doi: 10.1109/TSMCB.2009.2015956
16	LIM W H, MAT ISA N A. Particle swarm optimization with adaptive time-varying topology connectivity. Applied Soft Computing, 2014, 24, 623- 642. doi: 10.1016/j.asoc.2014.08.013
17	LIANG J J, SUGANTHAN P N. Dynamic multi-swarm particle swarm optimizer[C]//Proceedings of IEEE Swarm Intelligence Symposium. Washington D. C., USA: IEEE Press, 2005: 124-129.
18	ALI NAGRA A, HAN F, LING Q H, et al. An improved hybrid method combining gravitational search algorithm with dynamic multi swarm particle swarm optimization. IEEE Access, 2019, 7, 50388- 50399. doi: 10.1109/ACCESS.2019.2903137
19	XIONG H, QIU B W, LIU J Z. An improved multi-swarm particle swarm optimizer for optimizing the electric field distribution of multichannel transcranial magnetic stimulation. Artificial Intelligence in Medicine, 2020, 104, 101790. doi: 10.1016/j.artmed.2020.101790
20	SHAMI T M, EL-SALEH A A, ALSWAITTI M, et al. Particle swarm optimization: a comprehensive survey. IEEE Access, 2020, 10, 10031- 10061.
21	LI G Q, WANG W L, ZHANG W W, et al. Grid search based multi-population particle swarm optimization algorithm for multimodal multi-objective optimization. Swarm and Evolutionary Computation, 2021, 62, 100843. doi: 10.1016/j.swevo.2021.100843
22	GAD A G. Particle swarm optimization algorithm and its applications: a systematic review. Archives of Computational Methods in Engineering, 2022, 29 (5): 2531- 2561. doi: 10.1007/s11831-021-09694-4
23	LIU G G, CHEN G L, GUO W Z. DPSO based octagonal Steiner tree algorithm for VLSI routing[C]//Proceedings of the 15th International Conference on Advanced Computational Intelligence. Washington D. C., USA: IEEE Press, 2012: 383-387.
24	WU H L, XU S J, ZHUANG Z, et al. X-architecture Steiner minimal tree construction based on discrete differential evolution[C]//Proceedings of the International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. Berlin, Germany: Springer, 2020: 433-442.
25	LIU G G, CHEN Z S, ZHUANG Z, et al. A unified algorithm based on HTS and self-adapting PSO for the construction of octagonal and rectilinear SMT. Soft Computing, 2020, 24 (6): 3943- 3961. doi: 10.1007/s00500-019-04165-2

[1]	乔英, 高岳林, 江巧永. 改进的多目标和声搜索算法[J]. 计算机工程, 2012, 38(18): 144-146.
[2]	逄金梅, 郑向伟, 王智昊. 保持多样性的自适应动态粒子群算法及其应用[J]. 计算机工程, 2012, 38(16): 167-169.
[3]	刘洪江;桑楠;罗惠琼. 基于检测信息交换的WMNs入侵检测模型[J]. 计算机工程, 2008, 34(22): 171-173.

选择文件类型/文献管理软件名称

选择包含的内容