TY - JOUR
T1 - Balanced partitioning
AU - Yang, Hannah Honghua
AU - Wong, D.F.
N1 - Funding Information:
This work was supported in part by the Texas Advanced Research Program under Grant 003658459, by an Intel Foundation Graduate Fellowship, by a DAC Design Automation Scholarship, and by a Grant from AT&T Bell Laboratories.
Publisher Copyright:
© 1996 IEEE
PY - 1996/12
Y1 - 1996/12
N2 - We consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. Previously, Kernighan and Lin type (K&L) heuristics, simulated annealing approach, and analytical methods were given to solve the problem. However, network flow (max-flow min-cut) techniques were overlooked as viable heuristics to min-cut balanced bipartition due to their 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 K&L heuristics and analytical methods in terms of the number of crossing nets, and our efficient implementation makes it possible to partition large circuit netlists with reasonable runtime. For example, the average elapsed time for bipartitioning a circuit S35932 of almost 20 K gates is less than 20 min on a SPARC10 with 32 MB memory.
AB - We consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. Previously, Kernighan and Lin type (K&L) heuristics, simulated annealing approach, and analytical methods were given to solve the problem. However, network flow (max-flow min-cut) techniques were overlooked as viable heuristics to min-cut balanced bipartition due to their 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 K&L heuristics and analytical methods in terms of the number of crossing nets, and our efficient implementation makes it possible to partition large circuit netlists with reasonable runtime. For example, the average elapsed time for bipartitioning a circuit S35932 of almost 20 K gates is less than 20 min on a SPARC10 with 32 MB memory.
U2 - 10.1109/43.552086
DO - 10.1109/43.552086
M3 - Journal article
SN - 0278-0070
VL - 15
SP - 1533
EP - 1540
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 12
M1 - 552086
ER -