Multilevel generalized force-directed method for circuit placement

Tony Chan*, Jason Cong, Kenton Sze

*Corresponding author for this work

Research output: Contribution to conferencePaperpeer-review

154 Scopus citations

Abstract

Automatic circuit placement has received renewed interest recently given the rapid increase of circuit complexity, increase of interconnect delay, and potential sub-optimality of existing placement algorithms [13]. In this paper we present a generalized force-directed algorithm embedded in mPL2's [12] multilevel framework. Our new algorithm, named mPL5, produces the shortest wirelength among all published placers with very competitive runtime on the IBM circuits used in [29]. The new contributions and enhancements are: (1) We develop a new analytical placement algorithm using a density constrained minimization formulation which can be viewed as a generalization of the force-directed method in [16]; (2) We analyze and identify the advantages of our new algorithm over the force-directed method; (3) We successfully incorporate the generalized force-directed algorithm into a multilevel framework which significantly improves wirelength and speed. Compared to Capo9.0, our algorithm mPL5 produces 8% shorter wirelength and is 2X faster. Compared to Dragon3.01, mPL5 has 3% shorter wirelength and is 12X faster. Compared to Fengshui5.0, it has 5% shorter wirelength and is 2X faster. Compared to the ultrafast placement algorithm: FastPlace, mPL5 produces 8% shorter wirelength but is 6X slower. A fast mode of mPL5 (mPL5-fast) can produce 1% shorter wirelength than FastPlace1.0 and is only 2X slower. Moreover, mPL5-fast has demonstrated better scalability than FastPlace1.0.

Original languageEnglish (US)
Pages185-192
Number of pages8
DOIs
StatePublished - 2005
Externally publishedYes
Event2005 International Symposium on Physical Design, ISPD'05 - San Francisco, CA, United States
Duration: Apr 3 2005Apr 6 2005

Conference

Conference2005 International Symposium on Physical Design, ISPD'05
Country/TerritoryUnited States
CitySan Francisco, CA
Period04/3/0504/6/05

Keywords

  • Forced-directed Method
  • Multilevel
  • Standard Cell Placement

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Multilevel generalized force-directed method for circuit placement'. Together they form a unique fingerprint.

Cite this