Efficient network flow based min-cut balanced partitioning

Honghua Yang, D. F. Wong

Research output: Contribution to journalConference articlepeer-review

Abstract

We consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. Previously, the Kernighan and Lin type (K&L) heuristics, the simulated annealing approach, and the spectral method were given to solve the problem. However, network flow techniques were overlooked as a viable approach to min-cut balanced bipartition due to its high complexity. In this paper we propose a balanced bipartition heuristic based on repeated max-flow min-cut techniques, and give an efficient implementation that has the same asymptotic time complexity as that of one max-flow computation. We implemented our heuristic algorithm in a package called FBB. The experimental results demonstrate that FBB outperforms the K&L heuristics and the spectral method in terms of the number of crossing nets, and the efficient implementation makes it possible to partition large circuit instances with reasonable runtime. For example, the average elapsed time for bipartitioning a circuit S35932 of almost 20K gates is less than 20 minutes.

Original languageEnglish (US)
Pages (from-to)50-55
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
StatePublished - Dec 1 1994
Externally publishedYes
EventProceedings of the 1994 IEEE/ACM International Conference on Computer-Aided Design - San Jose, CA, USA
Duration: Nov 6 1994Nov 10 1994

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Efficient network flow based min-cut balanced partitioning'. Together they form a unique fingerprint.

Cite this