Crowdedness-balanced multilevel partitioning for uniform resource utilization

Yongseok Cheon, Martin D F Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 Mock 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 Mock 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 (US)
Title of host publicationProceedings of the 2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005
Number of pages6
StatePublished - 2005
Event2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005 - Shanghai, China
Duration: Jan 18 2005Jan 21 2005

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC


Other2005 Asia and South Pacific Design Automation Conference, ASP-DAC 2005

ASJC 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