Fast and Effective Placement Refinement for Routability

In this brief, we propose congestion refinement of placement (CROP) for improving the congestion of mixed-size placement solutions. CROP consists of a congestion-driven module shifting technique and a congestion-driven detailed placement (CDDP) technique. The shifting technique is proposed for better allocation of routing resources. We shift modules based on the shifting of G-cell boundaries. Shifting in each direction can be formulated as a linear program (LP) for resizing each cell in the global routing grid (i.e., G-cell). We degenerate and solve the LP by a very efficient longest path computation. Then the CDDP technique is proposed for distributing the routing demands better. Congestion reduction is realized by weighting the half-perimeter wirelength with the congestion factor during detailed placement. Theoretically, our tool is capable of handling most mixed-size placement benchmarks with movable and/or fixed macro (FM) blocks. In order to better analyze its performance, the ISPD-GR benchmark suite (ISPD05/06 derived global routing benchmarks) with FM modes is developed. The experimental results show that CROP effectively alleviates congestion for unroutable placement solutions in short runtimes for different placers.