Pathfinding Model and Lagrangian-Based Global Routing

Global routing is a critical step in VLSI physical design. This paper proposes a novel pathfinding model based on integer linear programming for VLSI global routing. The Lagrangian relaxation method combined with a direction-aware weighted A*-algorithm is developed to quickly solve the model to obtain a better initial routing solution, which is further optimized by a designed multi-stage rip-up & rerouting algorithm. In each stage of rip-up & rerouting, different routing algorithms and cost functions are used to optimize the overflow and wire length. SPRoute and CUGR are two state-of-the-art global routers. Our proposed global routing algorithm outperforms SPRoute 1.0 & 2.0 in both the wire length and the number of vias on the ISPD08 benchmarks. On the ISPD18 benchmarks, compared to CUGR, our algorithm has about 5.1% reduction in the number of vias, and the average runtime is 4.89× speedup; compared to SPRoute 2.0, our algorithm has about 1.7% reduction on the average wire length, and the number of vias is comparable.