High Quality Global Routing Algorithm Based on Multi-Stage Optimization

被引：0
|
作者：
Genggeng L. [1 ,2 ]
Zhenyu P. [1 ]
Ning X. [3 ]
机构：
[1] College of Computer and Data Science, Fuzhou University, Fuzhou
[2] State Key Laboratory of Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing
[3] School of Information Engineering, Wuhan University of Technology, Wuhan
来源：
Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics | 2024年 / 36卷 / 04期
关键词：
A* algorithm; dynamic adjustment strategy; global routing; multi-stage optimization; VLSI;
D O I：
10.3724/SP.J.1089.2024.19956
中图分类号：
学科分类号：
摘要：
Global routing is a crucial step in VLSI physical design. To address the problems that the low utilization rate of capacity and easy to fall into local optimum in the existing global routing algorithms, a high-quality global routing algorithm based on multi-stage optimization is proposed. First, the virtual capacity dynamic adjustment strategy is introduced in the pre-connection stage and the routing reorganization stage to improve the utilization rate of capacity. Then, in the routing reorganization stage, the routing subarea adaptive expansion strategy is proposed to narrow the search space and improve the routing efficiency. Finally, the A* algorithm heuristic search is combined with the global search capability of the particle swarm algorithm to avoid the algorithm to choose the shortest path in the routing process, and thus avoid the algorithm to fall into the local optimum. Experimental results comparing with existing global routing algorithms on ISPD benchmark circuits show that the routing results of proposed algorithm reduce the wirelength by 6.0% to 22.8%. © 2024 Institute of Computing Technology. All rights reserved.
引用
收藏
页码：607 / 614
页数：7
相关论文
共 20 条
  • [1] Xu Ning, Hong Xianlong, Very large scale integration physical design theory and method, pp. 147-172, (2009)
  • [2] Zhang Sanfeng, Zhou Xiong, Yang Shiheng, Et al., Develop EDA and ensure national network and information security, China Information Security, 5, pp. 62-63, (2020)
  • [3] Yu Xiekang, Issues, challenges and development methods of China’s IC industry, Application of IC, 33, 4, pp. 4-5, (2016)
  • [4] Liu J W, Pui C W, Wang F Z, Et al., CUGR: detailed-routability-driven 3D global routing with probabilistic resource model, Proceedings of the 57th ACM/IEEE Design Automation Conference, pp. 1-6, (2020)
  • [5] Chang Y J, Lee Y T, Gao J R, Et al., NTHU-Route 2.0: a robust global router for modern designs, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 29, 12, pp. 1931-1944, (2010)
  • [6] Liu W H, Kao W C, Li Y L, Et al., NCTU-GR 2.0: multithreaded collision-aware global routing with bounded-length maze routing, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32, 5, pp. 709-722, (2013)
  • [7] Cao Z, Jing T T, Xiong J J, Et al., Fashion: a fast and accurate solution to global routing problem, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27, 4, pp. 726-737, (2008)
  • [8] Cho M, Lu K, Yuan K, Et al., BoxRouter 2.0: a hybrid and robust global router with layer assignment for routability, ACM Transactions on Design Automation of Electronic Systems, 14, 2, pp. 1-21, (2009)
  • [9] Xu Y, Zhang Y H, Chu C., FastRoute 4.0: global router with efficient via minimization, Proceedings of the Asia and South Pacific Design Automation Conference, pp. 576-581, (2009)
  • [10] Ozdal M M, Wong M D F., Archer: a history-based global routing algorithm, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 28, 4, pp. 528-540, (2009)
12