Design hierarchy guided multilevel circuit partitioning

Yongseok Cheon, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

4 Citations (Scopus)


In this paper, we present a new multilevel circuit partitioning algorithm (dhml) which is guided by design hierarchy. In addition to flat netlist hypergraph, we use user design hierarchy as a hint for partitioning because it already has some implications on connectivity information between logical blocks in the design. Using design hierarchy in partitioning is nontrivial since hierarchical elements in design hierarchy does not necessarily have strong internal connectivity, hence we need to determine whether it is preferable to break up or preserve the hierarchical elements. In order to identify and select the hierarchical elements with strong connectivity, Rent exponent is used. Then, the selected hierarchical elements are used as effective clustering scopes during multilevel coarsening phase. The scopes are dynamically updated (enlarged) while building up a clustering tree so that the clustering tree resembles the densely connected portions of the design hierarchy. We tested our algorithm on a set of large industrial designs in which the largest one has 1.8 million cells, 2.8 million nets, and 11 levels of hierarchy. By exploiting design hierarchy, our algorithm produces higher quality partitioning results than the state-of-the-art multilevel partitioner hMetis. Furthermore, experimental results show that dhml yields significantly more stable solutions, which is helpful in practice to reduce the number of runs to obtain the best result.
Original languageEnglish
Title of host publicationISPD '02
Subtitle of host publicationProceedings of the 2002 international symposium on Physical design
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Print)9781581134605
Publication statusPublished - Apr 2002
Event11th International Symposium on Physical Design, ISPD 2002 - Hilton Hotel San Diego, Del Mar, United States
Duration: 7 Apr 200210 Apr 2002 (Conference website) (Conference proceedings)

Publication series

NameProceedings of The ACM International Symposium on Physical Design, ISPD


Symposium11th International Symposium on Physical Design, ISPD 2002
Country/TerritoryUnited States
CityDel Mar
Internet address

Scopus Subject Areas

  • Electrical and Electronic Engineering

User-Defined Keywords

  • Circuit partitioning
  • Clustering
  • Design hierarchy
  • Rent's rule


Dive into the research topics of 'Design hierarchy guided multilevel circuit partitioning'. Together they form a unique fingerprint.

Cite this