Faster minimization of linear wirelength for global placement

Abstract

A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool minimizes linear wirelength by first approximating the linear wirelength objective by a modified squared wirelength objective, then executing the following loop - (1) minimize the current objective to yield some approximate solution, and (2) use the resulting solution to construct a more accurate objective - until the solution converges. In this paper, we first show that the GORDIAN-L loop can be viewed as a special case of a new algorithm that generalizes a 1937 iteration due to Weiszfeld. Specifically, we formulate the Weiszfeld iteration using a regularization parameter to control the tradeoff between convergence and solution accuracy; the GORDIAN-L iteration is equivalent to setting this regularization parameter to zero. Other novel numerical methods described in the paper, the Primal Newton iteration and the Primal-Dual Newton iteration, further improve upon the linearly convergent Weiszfeld iteration. Our Primal-Dual Newton iteration stably attains quadratic convergence, making it a superior choice for implementing a placer such as GORDIAN-L, or for any linear wirelength optimization.