Quadratic placement revisited

C. J. Alpert*, T. Chan, D. J.H. Huang, I. Markov, K. Yan

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

33 Scopus citations


The 'quadratic placement' methodology is rooted in [6] [14] [16] and is reputedly used in many commercial and in-house tools for placement of standard-cell and gate-array designs. The methodology iterates between two basic steps: solving sparse systems of linear equations, and repartitioning. This work dissects the implementation and motivations for quadratic placement. We first show that (i) Krylov subspace engines for solving sparse systems of linear equations are more effective than the traditional successive over-relaxation (SOR) engine [15] and (ii) order convergence criteria can maintain solution quality while using substantially fewer solver iterations. We then discuss the motivations and relevance of the quadratic placement approach, in the context of past and future algorithmic technology, performance requirements, and design methodology. We provide evidence that the use of numerical linear systems solvers with quadratic wirelength objective may be due to the pre-1990's weakness of min-cut partitioners, i.e., numerical engines were needed to provide helpful hints to min-cut partitioners. Finally, we note emerging methodology drivers in deep-submicron design that may require new placement approaches to the placement problem.

Original languageEnglish (US)
Pages (from-to)752-757
Number of pages6
JournalProceedings - Design Automation Conference
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 34th Design Automation Conference - Anaheim, CA, USA
Duration: Jun 9 1997Jun 13 1997

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering


Dive into the research topics of 'Quadratic placement revisited'. Together they form a unique fingerprint.

Cite this