Crowdedness-balanced multilevel partitioning for uniform resource utilization

Yongseok Cheon, Martin D. F. Wong

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


In this paper, we propose a new multi-objective multilevel K-way partitioning which is aware of resource utilization distribution, assuming the resource utilization for a partitioned block is proportional to the logic occupation and the interconnections required for the block. A new quality of the partitioning solution, crowdedness, is defined as a virtual complexity metric where the physical size and the local connectivity of a partitioned block are considered simultaneously in the form of a weighted sum. The partitioning solutions driven by overall cut quality minimization tend to have wide variances of local interconnections for different blocks. The difference of block sizes, combining with the variance of the interconnections, potentially leads to the significant imbalance of the crowdedness (equivalently, resource utilization), even though the feasibility imposed by a block-size constraint is satisfied.

Using the crowdedness metric, we explore the new partitioning solution space where the local interconnections are adaptively adjusted according to the block sizes, still under the same objective of overall interconnections minimization. By the carefully designed prioritized cell move policy, the proposed crowdedness-based partitioning achieves near-optimal solutions in terms of resource utilization distribution, while the overall interconnection quality also is improved but the feasibility is barely violated. The proposed approach is practically beneficial to multi-FPGA applications, in which excessive interconnections for a FPGA generate additional logics inside of the FPGA.

Original languageEnglish
Title of host publicationASP-DAC '05
Subtitle of host publicationProceedings of the 2005 Asia and South Pacific Design Automation Conference
Place of PublicationUnited States
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
ISBN (Electronic)9780780387379
Publication statusPublished - Jan 2005
Event10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Hotel Equatorial, Shanghai, China
Duration: 18 Jan 200521 Jan 2005 (Conference website)


Conference10th Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Crowdedness-balanced multilevel partitioning for uniform resource utilization'. Together they form a unique fingerprint.

Cite this