Analytical Engines are Unnecessary in Top-down Partitioning-based Placement

C. J. Alpert, A. E. Caldwell, T. F. Chan, D. J.H. Huang, A. B. Kahng*, I. L. Markov, M. S. Moroz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The top-down "quadratic placement" methodology is rooted in such works as [36, 9, 32] and is reputedly the basis of commercial and in-house VLSI placement tools. This methodology iterates between two basic steps: solving sparse systems of linear equations to achieve a continuous placement solution, and "legalization" of the placement by transportation or partitioning. Our work, which extends [5], studies implementation choices and underlying motivations for the quadratic placement methodology. We first recall some observations from [5], e.g., that (i) Krylov subspace engines for solving sparse linear systems are more effective than traditional successive over-relaxation (SOR) engines [33] and (ii) that correlation convergence criteria can maintain solution quality while using substantially fewer solver iterations. The focus of our investigation is the coupling of numerical solvers to iterative partitioners that is a hallmark of the quadratic placement methodology. We provide evidence that this coupling may have historically been motivated by the pre-1990's weakness of min-cut partitioners, i.e., numerical engines were needed to provide helpful hints to weak min-cut partitioners. In particular, we show that a modern multilevel FM implementation [2] derives no benefit from such coupling. We also show that most insights obtained from study of individual min-cut partitioning instances (within the top-down placement) also hold within the overall context of a complete top-down placer implementation.

Original languageEnglish (US)
Pages (from-to)99-116
Number of pages18
JournalVLSI Design
Issue number1
StatePublished - 1999
Externally publishedYes


  • Hierarchical top-down placement
  • Multi-level min-cut partitioning
  • Quadratic placement

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Analytical Engines are Unnecessary in Top-down Partitioning-based Placement'. Together they form a unique fingerprint.

Cite this