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 [19] 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. This paper shows how to apply a generalization [5], [6] of a 1937 algorithm due to Weiszfeld [22] to placement with a linear wirelength objective and that the main GORDIAN-L loop is actually a special case of this algorithm. We then propose applying a regularization parameter to the generalized Weiszfeld algorithm to control the tradeoff between convergence and solution accuracy; the GORDIAN-L iteration is equivalent to setting this regularization parameter to zero. We also apply novel numerical methods, such as the primal-Newton and primal-dual Newton iterations, to optimize the linear wirelength objective. Finally, we show both theoretically and empirically that the primal-dual Newton iteration stably attains quadratic convergence, while the generalized Weiszfeld iteration is linear convergent. Hence, primal-dual Newton is a superior choice for implementing a placer such as GORDIAN-L, or for any linear wirelength optimization. © 1998 IEEE.