X-architecture Steiner Minimum Tree Algorithm Considering Routing Resource Relaxation
TANG Hao1,2, LIU Genggeng1,2,3, GUO Wenzhong1,2,3, CHEN Guolong1,2
1. College of Mathematics and Computer Sciences, Fuzhou University, Fuzhou 350116; 2. Key Laboratory of Networking Computing and Intelligent Information Processing, Fujian Province, Fuzhou University, Fu-zhou 350116; 3. Key Laboratory of Spatial Data Mining and Information Sharing, Ministry of Education, Fuzhou University, Fuzhou 350108
Abstract：To further study X-architecture and make full use of routing resources within the obstacle, an X-architecture Steiner minimum tree algorithm considering routing resource relaxation is proposed in this paper. Firstly, crossover and mutation operators are introduced in the update operation of particles to solve the discretization problem. Secondly, look-up tables are presented for the whole algorithm process to provide a fast information query. Thirdly, a corner point selection strategy is proposed to introduce some obstacle corner points and satisfy the constraints. Finally, a refinement strategy is implemented to further improve the quality of the final routing tree. Experimental results show that the proposed algorithm makes full use of the routing resources within the obstacle, shortens the total wirelength effectively and achieves a better total wirelength.
[1] 刘耿耿,郭文忠,陈国龙.X结构下 VLSI 多层绕障 Steiner 最小树算法.计算机辅助设计与图形学学报, 2015, 27(3): 523-532. (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 and Computer Graphics, 2015, 27(3): 523-532.) [2] BORAH M, OWENS R M, IRWIN M J. An Edge-Based Heuristic for Steiner Routing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994, 13(12): 1563-1568. [3] ZHOU H. Efficient Steiner Tree Construction Based on Spanning Graphs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23(5): 704-710. [4] CINEL S, BAZLAMACCI C F. A Distributed Heuristic Algorithm for the Rectilinear Steiner Minimal Tree Problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(11): 2083-2087. [5] KAHNG A B, MANDOIU I I, ZELIKOVSKY A Z. Highly Scalable Algorithms for Rectilinear and Octilinear Steiner Trees // Proc of the Asia and South Pacific Design Automation Conference. Washington, USA: IEEE, 2003: 827-833. [6] 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. [7] VANI V, PRASAD G R. Augmented Line Segment Based Algorithm for Constructing Rectilinear Steiner Minimum Tree // Proc of the International Conference on Communication and Electronics Systems. Washington, USA: IEEE, 2016. DOI: 10.1109/CESYS.2016.7889854. [8] NAIR L R, PRASAD G R. Wirelength and Memory Optimized Rectilinear Steiner Minimum Tree Routing // Proc of the 2nd IEEE International Conference on Recent Trends in Electronics, Information and Communication Technology. Washington, USA: IEEE, 2017: 1493-1497. [9] TU P, CHOW W K, YOUNG E F Y, Timing Driven Routing Tree Construction // Proc of the ACM/IEEE International Workshop on System Level Interconnect Prediction. Washington, USA: IEEE, 2017. DOI: 10.1109/SLIP.2017.7974908. [10] YAN J T. Timing-Driven Octilinear Steiner Tree Construction Ba-sed on Steiner-Point Reassignment and Path Reconstruction. ACM Transactions on Design Automation of Electronic Systems, 2008, 13(2). DOI: 10.1145/1344418.1344422. [11] LIU G G, GUO W Z, NIU Y Z, et al. A PSO-Based Timing-Driven Octilinear Steiner Tree Algorithm for VLSI Routing Considering Bend Reduction. Soft Computing, 2015, 19(5): 1153-1169. [12] 洪先龙,朱 祺,经 彤,等.非直角互连——布线技术发展的新趋势.半导体学报, 2003, 24(3): 225-233. (HONG X L, ZHU Q, JING T, et al. Non-rectilinear On-Chip Interconnect-An Efficient Routing Solution with High Performance. Chinese Journal of Semiconductors, 2003, 24(3): 225-233.) [13] ZHU Q, ZHOU H, JING T, et al. Spanning Graph-Based Nonrectilinear Steiner Tree Algorithms. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(7): 1066-1075. [14] HO T Y, CHANG C F, CHANG Y W, et al. Multilevel Full-Chip Routing for the X-Based Architecture // Proc of the 42nd Annual Design Automation Conference. Washington, USA: IEEE, 2005: 597-602. [15] 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. [16] AJWANI G, CHU C, MAK W K. FOARS: FLUTE Based Obstacle-Avoiding Rectilinear Steiner Tree Construction. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(2): 194-204. [17] LIN K W, LIN Y S, LI Y L, et al. A Maze Routing-Based Algorithm for ML-OARST with Pre-selecting and Re-building Steiner Points // Proc of the ACM Great Lakes Symposium on VLSI. New York, USA: ACM, 2017: 399-402. [18] WANG R Y, PAI C C, WANG J J, et al. Efficient Multi-layer Obstacle-Avoiding Region-to-Region Rectilinear Steiner Tree Construction // Proc of the 55th Annual Design Automation Confe-rence. New York, USA: ACM, 2018. DOI: 10.1109/DAC.2018.8465783. [19] 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. ACM Transactions on Design Automation of Electronic Systems, 2015, 20(2): 1-28. [20] HUANG X, GUO W Z, LIU G G, et al. FH-OAOS: A Fast Four-Step Heuristic for Obstacle-Avoiding Octilinear Steiner Tree Construction. ACM Transactions on Design Automation of Electronic Systems, 2016, 21(3): 1-31. [21] 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). DOI: 10.1007/s11432-015-0850-4. [22] MÜLLER-HANNEMANN M, PEYER S. Approximation of Rectilinear Steiner Trees with Length Restrictions on Obstacles // Proc of the Workshop on Algorithms and Data Structures. Berlin, Germany: Springer, 2003: 207-218. [23] MEHLHORN K. A Faster Approximation Algorithm for the Steiner Problem in Graphs. Information Processing Letters, 1988, 27(3): 125-128. [24] HELD S, SPIRKL S T. A Fast Algorithm for Rectilinear Steiner Trees with Length Restrictions on Obstacles // Proc of the International Symposium on Physical Design. New York, USA: ACM, 2014: 37-44. [25] CLARKSON K L, KAPOOR S, VAIDYA P M. Rectilinear Shortest Paths through Polygonal Obstacles in O(n(logn)2) Time // Proc of the 3rd Annual Symposium on Computational Geometry. New York, USA: ACM, 1987: 251-257. [26] ZHANG Y L, CHAKRABORTY A, CHOWDHURY S, et al. Reclaiming Over-the-IP-Block Routing Resources with Buffering-Aware Rectilinear Steiner Minimum Tree Construction // Proc of the IEEE/ACM International Conference on Computer-Aided Design. Washington, USA: IEEE, 2012: 137-143. [27] HUANG T, YOUNG E F Y. Construction of Rectilinear Steiner Minimum Trees with Slew Constraints Over Obstacles // Proc of the IEEE/ACM International Conference on Computer-Aided Design. Washington, USA: IEEE, 2012: 144-151. [28] ZHANG H, YE D Y, GUO W Z. A Heuristic for Constructing a Rectilinear Steiner Tree by Reusing Routing Resources over Obstacles. Integration, 2016, 55: 162-175. [29] EBERHART R, KENNEDY J. A New Optimizer Using Particle Swarm Theory // Proc of the 6th International Symposium on Micro Machine and Human Science. Washington, USA: IEEE, 1995: 39-43. [30] FENG L, ALI A, IQBAL M, et al. Optimal Haptic Communications over Nanonetworks for E-Health Systems. IEEE Transactions on Industrial Informatics, 2019, 15(5): 3016-3027. [31] YAZDANINEJADI A, GOLSHANNAVAZ S, NAZARPOUR D, et al. Dual-Setting Directional Overcurrent Relays for Protecting Automated Distribution Networks. IEEE Transactions on Industrial Informatics, 2019, 15(2): 730-740. [32] 刘耿耿,陈志盛,郭文忠,等.基于自适应PSO和混合转换策略的X结构Steiner最小树算法.模式识别与人工智能, 2018, 31(5): 398-408. (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.) [33] ZHOU H Y, WANG X G, CUI N G. A Novel Reentry Trajectory Generation Method Using Improved Particle Swarm Optimization. IEEE Transactions on Vehicular Technology, 2019, 68(4): 3212-3223. [34] 郭文忠,陈晓华,刘耿耿,等.基于混合离散粒子群优化的轨道分配算法.模式识别与人工智能, 2019, 32(8): 758-770. (GUO W Z, CHEN X H, LIU G G, et al. Track Assignment Algorithm Based on Hybrid Discrete Particle Swarm Optimization. Pattern Recognition and Artificial Intelligence, 2019, 32(8): 758-770.) [35] 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.
2020, Vol. 33 
