Network-flow-based multiway partitioning with area and pin constraints

Huiqun Liu, D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

36 Citations (Scopus)

Abstract

Network flow is an excellent approach to finding min-cuts because of the celebrated max-flow min-cut theorem. For a long time, however, it was perceived as computationally expensive and deemed impractical for circuit partitioning. Recently, the algorithm FBB [1], [2] successfully applied network flow to two-way balanced partitioning. It 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 multiway partitioning with area and pin constraints. Experimental results show that FBB-MW outperforms previous approaches for multiple field programmable gate array partitioning. In particular, although FBB-MW does not employ logic replication and logic resynthesis, it still outperforms [5] and [6], which allow replication and resynthesis for optimization.

Original languageEnglish
Pages (from-to)50-59
Number of pages10
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume17
Issue number1
DOIs
Publication statusPublished - Jan 1998

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Network-flow-based multiway partitioning with area and pin constraints'. Together they form a unique fingerprint.

Cite this