Quadratic placement revisited

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

28 Scopus citations

Abstract

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)
Title of host publicationQuadratic placement revisited
Pages752-757
Number of pages6
StatePublished - Jan 1 1997
Externally publishedYes
EventProceedings of the 1997 34th Design Automation Conference - Anaheim, CA, USA
Duration: Jun 9 1997Jun 13 1997

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

ConferenceProceedings of the 1997 34th Design Automation Conference
CityAnaheim, CA, USA
Period06/9/9706/13/97

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering

Fingerprint

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

Cite this