Highly Efficient Gradient Computation for Density-Constrained Analytical Placement

Recent analytical global placers use density constraints to approximate nonoverlap constraints, and these show very successful results. This paper unifies a wide range of density smoothing techniques called global smoothing and presents a highly efficient method for computing the gradient of such smoothed densities used in several well-known analytical placers. This method reduces the complexity of the gradient computation by a factor of n compared with a naive method, where n is the number of modules. Furthermore, with this efficient gradient computation, it is able to support an efficient nonlinear programming-based placement framework, which supersedes the existing force-directed placement methods. Experiments show that replacing the approximated gradient computation in mPL6 with the exact gradient computation improves wire length by 15% on the IBM-HB+ benchmark and by 3% on average on the modified International Symposium on Physical Design 2005 (ISPD´05) and ISPD´06 placement contest benchmarks with movable macros. The results also show that the augmented Lagrangian method outperforms the quadratic penalty method with the exact gradient computation.