Algorithms for simultaneous satisfaction of multiple constraints and objective optimization in a placement flow with application to congestion control

This paper addresses the problem of tackling multiple constraints simultaneously during a partitioning driven placement (PDP) process, where a larger solution space is available for constraint-satisfying optimization compared to post-placement methods. A general methodology of multi-constraint satisfaction that balances violation correction and primary optimization is presented. A number of techniques are introduced to ensure its convergence and enhance its solution search capability with intermediate relaxation. Application of our approach to congestion control modeled as pin density and external net distribution balance constraints shows it effectively reduces overall congestion by 14.3% and improves chip area by 8.9%, with reasonable running time and only 1.6% increase in wire length. As far as we know, this is the first time an approach to congestion reduction during placement optimization produced good congestion improvement with very small wire length increase.