skip to main content
10.1145/1120725.1120901acmconferencesArticle/Chapter ViewAbstractPublication PagesaspdacConference Proceedingsconference-collections
Article

Crowdedness-balanced multilevel partitioning for uniform resource utilization

Published: 18 January 2005 Publication History

Abstract

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.

References

[1]
C. J. Alpert and A. B. Kahng, "Recent directions in netlist partitioning: A survey," Integration, the VLSI Journal, pp. 1--81, 1995.
[2]
C. M. Fiduccia and R. M. Mattheyses, "A linear time heuristic for improving network partitions," in Proc. ACM/IEEE Design Automation Conf., pp. 175--181, 1982.
[3]
G. Karypis, R. Aggarwal, V. Kumar, and S. Sheckhar, "Multilevel hypergraph partitioning: Application in VLSI domain," in Proc. ACM/IEEE Design Automation Conf., pp. 526--529, 1997.
[4]
G. Karypis and V. Kumar, "Multilevel k-way hypergraph partitioning," in Proc. ACM/IEEE Design Automation Conf., pp. 343--348, 1999.
[5]
C. Alpert, "The ISPD98 Circuit Benchmark Suite," In Proc. ACM International Symposium on Physical Design, pp. 18--25, 1998.
[6]
N. Selvakkumaran and G. Karypis, "Multi-objective hypergraph partitioning algorithms for cut and maximum subdomain degree minimization," In Proc. Int'l. Conf. on Computer-Aided Design, pp. 726--733, 2003.
[7]
X. Yang, B. Choi and M. Sarrafzadeh, "Routability driven white space allocation for fixed-die standard-cell placement," In Proc. ACM Int'l Symposium on Physical Design, pp. 42--47, 2002.
[8]
C. Li, M. Xie, C-K. Koh, J. Cong and P. Madden, "Routability-driven placement and white space allocation," In Proc. Int'l Conf. Computer-Aided Design, pp. 394--401

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ASP-DAC '05: Proceedings of the 2005 Asia and South Pacific Design Automation Conference
January 2005
1495 pages
ISBN:0780387376
DOI:10.1145/1120725
  • General Chair:
  • Ting-Ao Tang
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 January 2005

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

ASPDAC05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 104
    Total Downloads
  • Downloads (Last 12 months)3
  • Downloads (Last 6 weeks)0
Reflects downloads up to 09 Feb 2025

Other Metrics

Citations

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media