Faster minimization of linear wirelength for global placement

Charles J. Alpert*, Tony Chan, Andrew B. Kahng, Igor L. Markov, Pep Mulet

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

24 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)3-13
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume17
Issue number1
DOIs
StatePublished - Dec 1 1998

Keywords

  • Analytic placement, gordian-l, interconnect delay, linear placement, linear wirelength, newton, primal dual, quadratic placement, weiszfeld

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Faster minimization of linear wirelength for global placement'. Together they form a unique fingerprint.

Cite this