An Improvement On Nonlinear Conjugate Gradient Algorithm For Bonding Box Constrained Solver In Global Placer

Global placement in fact is one box constraint problem while the widely used optimization method is the unconstraint nonlinear conjugate gradient(CG) algorithm. When we apply the unstrained CG to solve the bonding box constrained placement problem, there must be some cells are put outside of the chip. We call these cells illegal cells. Then when to project the illegal cells in is the key.Through the Matlab analysis using the collected outliner percentage statistics on many designs, we found 1) the same trend and character for the outliners 2) figured out one practical and efficient method is to project in the outliners at the end of each partition level. After improving current unconstrained nonlinear CG algorithm and applying some mathematic skills, the final quality metrics are proven to be better on average through the verification on the Mesh designs using CG_DESCENT.We improved current unconstraint conjugate gradient(CG) algorithm with faster convergence rate, and this speedup is achieved without significant increasing in the number of function or gradient evaluations. It is worthy to improve current unconstrained CG solver algorithm so that we can help customers to shorten the time-to-market period and reduce the final total cost like wire length at the same time.