X-Architecture Steiner Minimum Tree Algorithm Based on Dynamic Particle Swarm Optimization
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.
dynamic Particle Swarm Optimization(PSO)information exchangeX-architecture Steiner Minimum Tree(XSMT)Very Large Scale Integration circuit(VLSI)routingDiscretization of Particle Swarm Optimization(DPSO)
万方数据
维普
