TY - JOUR
T1 - Network-flow-based multiway partitioning with area and pin constraints
AU - Liu, Huiqun
AU - Wong, D. F.
N1 - Funding Information:
Manuscript received June 20, 1997. This work was supported in part by the Texas Advanced Research Program under Grant 003658288. This paper was recommended by Associate Editor M. Sarrafzadeh. The authors are with the Department of Computer Sciences, University of Texas at Austin, Austin, TX 78712 USA (e-mail: [email protected]; [email protected]). Publisher Item Identifier S 0278-0070(98)02051-X.
PY - 1998/1
Y1 - 1998/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031679348&partnerID=8YFLogxK
U2 - 10.1109/43.673632
DO - 10.1109/43.673632
M3 - Journal article
AN - SCOPUS:0031679348
SN - 0278-0070
VL - 17
SP - 50
EP - 59
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 - 1
ER -