Generalized Augmented Lagrangian and Its Applications to VLSI Global Placement^*

摘要

Global placement dominates the circuit placement process in its solution quality and efficiency. With increasing design complexity and various design constraints, it is desirable to develop an efficient, high-quality global placement algorithm for modern large-scale circuit designs. In this paper, we first analyze the properties of four nonlinear optimization methods (the quadratic penalty method, the Lagrange multiplier method, and two augmented Lagrangian methods) for global placement, and then develop a generalized augmented Lagrangian method to solve this problem. Our proposed method preserves the advantages of the quadratic penalty method and the augmented Lagrangian method, and provides a smooth progress from the quadratic penalty method to the augmented Lagrangian method. We prove that the proposed generalized augmented Lagrangian method is globally convergent for the original global placement problem, even with different constraints. Compared with the other four popular optimization methods, experimental results show that our method achieves the best quality and is robust for handling different objectives. In particular, our generalized augmented Lagrangian formulation is theoretically sound and can solve generic large-scale constrained nonlinear optimization problems, which are widely used in many fields.