Network flow based multi-way partitioning with area and pin constraints

Huiqun Liu, Martin D F Wong

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

Abstract

Network flow is an excellent approach to finding min-cuts because of the celebrated max-flow min-cut theorem. However, for a long time, it was perceived as computationally expensive and deemed impractical for circuit partitioning. Only until recently, FBB successfully applied network flow to two-way balanced partitioning and for the first time demonstrated that network flow was a viable approach to circuit partitioning. In this paper, we present FBB-MW, which is an extension of FBB, to solve the problem of multi-way partitioning with area and pin constraints. Experimental results show that FBB-MW outperforms the FM-based MW-part program in the TAPIR package.

Original languageEnglish (US)
Title of host publicationProceedings of the International Symposium on Physical Design
PublisherACM
Pages12-17
Number of pages6
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 1st International Symposium on Physical Design, ISPD - Napa Valley, CA, USA
Duration: Apr 14 1997Apr 16 1997

Other

OtherProceedings of the 1997 1st International Symposium on Physical Design, ISPD
CityNapa Valley, CA, USA
Period4/14/974/16/97

    Fingerprint

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Liu, H., & Wong, M. D. F. (1997). Network flow based multi-way partitioning with area and pin constraints. In Proceedings of the International Symposium on Physical Design (pp. 12-17). ACM.