High Quality Global Routing Algorithm Based on Multi-Stage Optimization

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%.