Multilevel optimization for large-scale circuit placement

Tony Chan, Jason Cong, Tianming Kong, Joseph R. Shinnerl

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

103 Scopus citations


We have designed and implemented a new class of fast and highly scalable placement algorithms that directly handle complex constraints and achieve total wirelengths comparable to the state of the art. Our approach exploits recent advances in (i) multilevel methods for hier-archical computation, (ii) interior-point methods for nonconvex nonlinear programming, and (iii) the Fast Multipole Method for the order N evaluation of sums over the N(N - 1)/2 pairwise interactions of N components. Significant adaptation of these methods for the placement problem is required, and we have therefore developed a set of customized discrete algorithms for clustering, declustering, slot assignment, and local refinement with which the continuous algorithms are naturally combined. Preliminary test runs on benchmark circuits with up to 184,000 cells produce total wirelengths within approximately 5-10% of those of gordian-l [1] in less than one tenth the run time. Such an ultra-fast placement engine is badly needed for timing convergence of the synthesis and layout phases of integrated circuit design.

Original languageEnglish (US)
Title of host publicationIEEE/ACM International Conference on Computer Aided Design
Subtitle of host publicationA Conference for the EE CAD Professional, ICCAD 2000
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)0780364457
StatePublished - Jan 1 2000
EventIEEE/ACM International Conference on Computer Aided Design, ICCAD 2000 - San Jose, United States
Duration: Nov 5 2000Nov 9 2000

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152


ConferenceIEEE/ACM International Conference on Computer Aided Design, ICCAD 2000
Country/TerritoryUnited States
CitySan Jose

ASJC Scopus subject areas

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


Dive into the research topics of 'Multilevel optimization for large-scale circuit placement'. Together they form a unique fingerprint.

Cite this