基于自适应PSO和混合转换策略的X结构Steiner最小树算法
|
摘要
X结构Steiner最小树(XSMT)是非曼哈顿结构总体布线算法中多端线网的最佳连接模型,属于NP难问题.文中基于混合转换策略和自适应粒子群优化算法,提出XSMT构造算法.首先设计有效的混合转换策略,扩大算法寻优空间,提高算法收敛效率.为了满足粒子编码的健全性,算法的更新方式引入带并查集策略的交叉和变异算子,同时采取自适应调整学习因子的策略,加快粒子群优化算法的收敛速度.实验表明,文中算法能得到较好的XSMT求解方案,获得多种不同拓扑的XSMTs,有利于VLSI总体布线阶段的拥挤度优化.
X-architecture Steiner minimal tree( XSMT) problem is an NP-hard problem,and it is the best connection model for a multi-terminal net in non-Manhattan global routing problem. An XSMT construction algorithm based on hybrid transformation strategy and self-adapting particle swarm optimization( PSO) is proposed. Firstly,an effective hybrid transformation strategy is designed to enlarge the search space and enhance the convergence of the algorithm. Secondly,the crossover and mutation operators based on union-find sets and a self-adapting strategy to adjust the learning factors are proposed to satisfy the robustness of particle coding and further speed up the convergence of algorithm. The experimental results show that the proposed algorithm efficiently produces a better solution than others.Moreover,it obtains a series of XSMTs with different topology but same length. Thus,it provides a variety of options for global routing and opportunities to reduce congestion.
X-architecture Steiner minimal tree( XSMT) problem is an NP-hard problem,and it is the best connection model for a multi-terminal net in non-Manhattan global routing problem. An XSMT construction algorithm based on hybrid transformation strategy and self-adapting particle swarm optimization( PSO) is proposed. Firstly,an effective hybrid transformation strategy is designed to enlarge the search space and enhance the convergence of the algorithm. Secondly,the crossover and mutation operators based on union-find sets and a self-adapting strategy to adjust the learning factors are proposed to satisfy the robustness of particle coding and further speed up the convergence of algorithm. The experimental results show that the proposed algorithm efficiently produces a better solution than others.Moreover,it obtains a series of XSMTs with different topology but same length. Thus,it provides a variety of options for global routing and opportunities to reduce congestion.
引文
[1]徐宁,洪先龙.超大规模集成电路物理设计理论与算法.北京:清华大学出版社,2009.(XU N,HONG X L.Very Large Scale Integration Physical Design Theory and Method.Beijing,China:Tsinghua University Press,2009.)
[2]SIDDIQI U F,SAIT S M.A Game Theory Based Post-Processing Method to Enhance VLSI Global Routers.IEEE Access,2017,5:1328-1339.
[3]HELD S,MULLER D,ROTTER D,et al.Global Routing with Timing Constraints.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2018,37(2):406-419.
[4]SCHEIFELE R.RC-Aware Global Routing//Proc of the 35th IEEE/ACM International Conference on Computer-Aided Design.Washington,USA:IEEE,2016.DOI:10.1145/2966986.2967067.
[5]SCHEIFELE R.Steiner Trees with Bounded RC-Delay//Proc of the International Workshop on Approximation and Online Algorithms.Berlin,Germany:Springer,2014:224-235.
[6]COULSTON C S.Constructing Exact Octagonal Steiner Minimal Tree//Proc of the 13th ACM Great Lakes Symposium on VLSI.New York,USA:ACM,2003:1-6.
[7]THURBER A P,XUE G L.Computing Hexagonal Steiner Trees Using PCX for VLS//Proc of the 6th IEEE International Conference on Electronics,Circuits and Systems.Washington,USA:IEEE,1999,I:381-384.
[8]SAMANTA T,GHOSAL P,RAHAMAN H,et al.A Heuristic Method for Constructing Hexagonal Steiner Minimal Trees for Routing in VLS//Proc of the International Symposium on Circuits and Systems.Washington,USA:IEEE,2006:1788-1791.
[9]ZHU Q,ZHOU H,JING T,et al.Spanning Graph-Based Nonrectilinear Steiner Tree Algorithms.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems,2005,24(7):1066-1075.
[10]YAN J T.Timing-Driven Octilinear Steiner Tree Construction Based on Steiner-Point Reassignment and Path Reconstruction.ACM Transactions on Design Automation of Electronic Systems,2008,13(2):26:1-26:18.
[11]SAMANTA T,RAHAMAN H,DASGUPTA P.Near-Optimal Y-Routed Delay Trees in Nanometric Interconnect Design.IET Computers&Digital Techniques,2011,5(1):36-48.
[12]GAREY M R,JOHNSON D S.The Rectilinear Steiner Tree Problem Is NP-Complete.SIAM Journal on Applied Mathematics,1977,32(4):826-834.
[13]BHATTACHARYA P,KHAN A,SARKAR S K.A Global Routing Optimization Scheme Based on ABC Algorithm//KUNDU M K,MOHAPATRA D P,KONAR A,et al.,eds.Advanced Computing,Networking and Informatics.Berlin,German:Springer,2014,II:189-197.
[14]KHAN A,LAHA S,SARKAR S K.A Novel Particle Swarm Optimization Approach for VLSI Routing//Proc of the 3rd IEEE International Advance Computing Conference.Washington,USA:IEEE,2013:258-262.
[15]LIU G G,CHEN G L,GUO W Z,et al.DPSO-Based Rectilinear Steiner Minimal Tree Construction Considering Bend Reduction//Proc of the 7th International Conference on Natural Computation.Washington,USA:IEEE,2011.DOI:10.1109/ICNC.2011.6022221.
[16]LIU G G,CHEN G L,GUO W Z.DPSO Based Octagonal Steiner Tree Algorithm for VLSI Routing//Proc of the 5th IEEE International Conference on Advanced Computational Intelligence.Washington,USA:IEEE,2012.DOI:10.1109/ICACI.2012.6463191.
[17]LIU G G,HUANG X,GUO W Z,et al.Multilayer Obstacle-Avoiding X-Architecture Steiner Minimal Tree Construction Based on Particle Swarm Optimization.IEEE Transactions on Cybernetics,2015,45(5):989-1002.
[18]EBERHART R,KENNEDY J.A New Optimizer Using Particles Swarm Theory//Proc of the 6th International Symposium on Micro Machine and Human Science.Washington,USA:IEEE,1995:39-43.
[19]HUANG X,GUO W Z,LIU G G,et al.FH-OAOS:A Fast FourStep Heuristic for Obstacle-Avoiding Octilinear Steiner Tree Construction.ACM Transactions on Design Automation of Electronic Systems,2016.DOI:10.1145/2856033.
[20]HUANG X,GUO W Z,LIU G G,et al.MLXR:Multi-layer Obstacle-Avoiding X-Architecture Steiner Tree Construction for VLSI Routing.Science China Information Sciences,2017,60(1):19102:1-19102:3.
[21]LIU G G,GUO W Z,LI R R,et al.XGRouter:High-Quality Global Router in X-Architecture with Particle Swarm Optimization.Frontiers of Computer Science,2015,9(4):576-594.
[22]马军,杨波,马绍汉.近乎最佳的Manhattan型Steiner树近似算法.软件学报,2000,11(2):260-264.(MA J,YANG B,MA S H.A Near-Optimal Approximation Algorithm for Manhattan Steiner Tree.Journal of Software,2000,11(2):260-264.)
[23]RUDOLPH G.Convergence Analysis of Canonical Genetic Algorithms.IEEE Transactions on Neural Networks,1994,5(1):96-101.
[24]WARME D,WINTER P,ZACHARIASEN M.Geo Steiner Homepage[DB/OL].[2017-11-30].http://geosteiner.net.
[25]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.
[2]SIDDIQI U F,SAIT S M.A Game Theory Based Post-Processing Method to Enhance VLSI Global Routers.IEEE Access,2017,5:1328-1339.
[3]HELD S,MULLER D,ROTTER D,et al.Global Routing with Timing Constraints.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2018,37(2):406-419.
[4]SCHEIFELE R.RC-Aware Global Routing//Proc of the 35th IEEE/ACM International Conference on Computer-Aided Design.Washington,USA:IEEE,2016.DOI:10.1145/2966986.2967067.
[5]SCHEIFELE R.Steiner Trees with Bounded RC-Delay//Proc of the International Workshop on Approximation and Online Algorithms.Berlin,Germany:Springer,2014:224-235.
[6]COULSTON C S.Constructing Exact Octagonal Steiner Minimal Tree//Proc of the 13th ACM Great Lakes Symposium on VLSI.New York,USA:ACM,2003:1-6.
[7]THURBER A P,XUE G L.Computing Hexagonal Steiner Trees Using PCX for VLS//Proc of the 6th IEEE International Conference on Electronics,Circuits and Systems.Washington,USA:IEEE,1999,I:381-384.
[8]SAMANTA T,GHOSAL P,RAHAMAN H,et al.A Heuristic Method for Constructing Hexagonal Steiner Minimal Trees for Routing in VLS//Proc of the International Symposium on Circuits and Systems.Washington,USA:IEEE,2006:1788-1791.
[9]ZHU Q,ZHOU H,JING T,et al.Spanning Graph-Based Nonrectilinear Steiner Tree Algorithms.IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems,2005,24(7):1066-1075.
[10]YAN J T.Timing-Driven Octilinear Steiner Tree Construction Based on Steiner-Point Reassignment and Path Reconstruction.ACM Transactions on Design Automation of Electronic Systems,2008,13(2):26:1-26:18.
[11]SAMANTA T,RAHAMAN H,DASGUPTA P.Near-Optimal Y-Routed Delay Trees in Nanometric Interconnect Design.IET Computers&Digital Techniques,2011,5(1):36-48.
[12]GAREY M R,JOHNSON D S.The Rectilinear Steiner Tree Problem Is NP-Complete.SIAM Journal on Applied Mathematics,1977,32(4):826-834.
[13]BHATTACHARYA P,KHAN A,SARKAR S K.A Global Routing Optimization Scheme Based on ABC Algorithm//KUNDU M K,MOHAPATRA D P,KONAR A,et al.,eds.Advanced Computing,Networking and Informatics.Berlin,German:Springer,2014,II:189-197.
[14]KHAN A,LAHA S,SARKAR S K.A Novel Particle Swarm Optimization Approach for VLSI Routing//Proc of the 3rd IEEE International Advance Computing Conference.Washington,USA:IEEE,2013:258-262.
[15]LIU G G,CHEN G L,GUO W Z,et al.DPSO-Based Rectilinear Steiner Minimal Tree Construction Considering Bend Reduction//Proc of the 7th International Conference on Natural Computation.Washington,USA:IEEE,2011.DOI:10.1109/ICNC.2011.6022221.
[16]LIU G G,CHEN G L,GUO W Z.DPSO Based Octagonal Steiner Tree Algorithm for VLSI Routing//Proc of the 5th IEEE International Conference on Advanced Computational Intelligence.Washington,USA:IEEE,2012.DOI:10.1109/ICACI.2012.6463191.
[17]LIU G G,HUANG X,GUO W Z,et al.Multilayer Obstacle-Avoiding X-Architecture Steiner Minimal Tree Construction Based on Particle Swarm Optimization.IEEE Transactions on Cybernetics,2015,45(5):989-1002.
[18]EBERHART R,KENNEDY J.A New Optimizer Using Particles Swarm Theory//Proc of the 6th International Symposium on Micro Machine and Human Science.Washington,USA:IEEE,1995:39-43.
[19]HUANG X,GUO W Z,LIU G G,et al.FH-OAOS:A Fast FourStep Heuristic for Obstacle-Avoiding Octilinear Steiner Tree Construction.ACM Transactions on Design Automation of Electronic Systems,2016.DOI:10.1145/2856033.
[20]HUANG X,GUO W Z,LIU G G,et al.MLXR:Multi-layer Obstacle-Avoiding X-Architecture Steiner Tree Construction for VLSI Routing.Science China Information Sciences,2017,60(1):19102:1-19102:3.
[21]LIU G G,GUO W Z,LI R R,et al.XGRouter:High-Quality Global Router in X-Architecture with Particle Swarm Optimization.Frontiers of Computer Science,2015,9(4):576-594.
[22]马军,杨波,马绍汉.近乎最佳的Manhattan型Steiner树近似算法.软件学报,2000,11(2):260-264.(MA J,YANG B,MA S H.A Near-Optimal Approximation Algorithm for Manhattan Steiner Tree.Journal of Software,2000,11(2):260-264.)
[23]RUDOLPH G.Convergence Analysis of Canonical Genetic Algorithms.IEEE Transactions on Neural Networks,1994,5(1):96-101.
[24]WARME D,WINTER P,ZACHARIASEN M.Geo Steiner Homepage[DB/OL].[2017-11-30].http://geosteiner.net.
[25]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.