An Enhanced Multilevel Algorithm for Circuit Placement

Tony Chan*, Jason Cong, Tim Kong, Joseph R. Shinnerl, Kenton Sze

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

46 Scopus citations

Abstract

This paper presents several important enhancements to the recently published multilevel placement package mPL. The improvements include (i) unconstrained quadratic relaxation on small, noncontiguous subproblems at every level of the hierarchy; (ii) improved interpolation (declustering) based on techniques from algebraic multigrid (AMG), and (iii) iterated V-cycles with additional geometric information for aggregation in subsequent V-cycles. The enhanced version of mPL, named mPL2, improves the total wirelength result by about 12% compared to the original version. The attractive scalability properties of the mPL run time have been largely retained, and the overall run time remains very competitive. Compared to GORDIAN-L-DOMINO on uniform-cell-size IBM/ISPD98 benchmarks, a speed-up of well over 8× on large circuits (≥ 100,000 cells or nets) is obtained along with an average improvement in total wirelength of about 2%. Compared to Dragon on the same benchmarks, a speed-up of about 5× is obtained at the cost of about 4% increased wirelength. On the recently published PEKO synthetic benchmarks, mPL2 generates surprisingly high-quality placements - roughly 60% closer to the optimal than those produced by Capo 8.5 and Dragon - in run time about twice as long as Capo's and about 1/10th of Dragon's.

Original languageEnglish (US)
Pages (from-to)299-306
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Dec 26 2003
EventIEEE/ACM International Conference on Computer Aided Design ICCAD 2003: IEEE/ACM Digest of Technical Papers - San Jose, CA, United States
Duration: Nov 9 2003Nov 13 2003

Keywords

  • Algebraic Multigrid (AMG)
  • Multilevel Optimization
  • Placement
  • Quadratic Programming (QP)

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'An Enhanced Multilevel Algorithm for Circuit Placement'. Together they form a unique fingerprint.

Cite this