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

Huiqun Liu; D.F. Wong

doi:10.1145/267665.267673

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

Huiqun Liu
, D.F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Chapter › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	1997 international symposium on Physical design, ISPD '97
Publisher	Association for Computing Machinery (ACM)
Pages	12-17
Number of pages	6
ISBN (Print)	9780897919272
DOIs	https://doi.org/10.1145/267665.267673
Publication status	Published - Apr 1997
Event	1997 International Symposium on Physical Design, ISPD 1997 - Napa Valley, United States Duration: 14 Apr 1997 → 16 Apr 1997 https://dl.acm.org/doi/proceedings/10.1145/267665 (Conference proceedings )

Publication series

Name	Proceedings of 1997 international symposium on Physical design, ISPD '97

Symposium

Symposium	1997 International Symposium on Physical Design, ISPD 1997
Country/Territory	United States
City	Napa Valley
Period	14/04/97 → 16/04/97
Internet address	https://dl.acm.org/doi/proceedings/10.1145/267665 (Conference proceedings )

Access to Document

10.1145/267665.267673

Cite this

@inbook{866943e68c064e5fa58e976abd85ff70,

title = "Network flow based multi-way partitioning with area and pin constraints",

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.",

author = "Huiqun Liu and D.F. Wong",

note = "Funding Information: This work was partially supported by a grant from the Avant! Corporation. Publisher Copyright: {\textcopyright} 1997 ACM ; 1997 International Symposium on Physical Design, ISPD 1997 ; Conference date: 14-04-1997 Through 16-04-1997",

year = "1997",

month = apr,

doi = "10.1145/267665.267673",

language = "English",

isbn = "9780897919272",

series = "Proceedings of 1997 international symposium on Physical design, ISPD '97",

publisher = "Association for Computing Machinery (ACM)",

pages = "12--17",

booktitle = "1997 international symposium on Physical design, ISPD '97",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/267665",

}

Liu, H & Wong, DF 1997, Network flow based multi-way partitioning with area and pin constraints. in 1997 international symposium on Physical design, ISPD '97. Proceedings of 1997 international symposium on Physical design, ISPD '97, Association for Computing Machinery (ACM), pp. 12-17, 1997 International Symposium on Physical Design, ISPD 1997, Napa Valley, California, United States, 14/04/97. https://doi.org/10.1145/267665.267673

Network flow based multi-way partitioning with area and pin constraints. / Liu, Huiqun; Wong, D.F.
1997 international symposium on Physical design, ISPD '97. Association for Computing Machinery (ACM), 1997. p. 12-17 (Proceedings of 1997 international symposium on Physical design, ISPD '97).

Research output: Chapter in book/report/conference proceeding › Chapter › peer-review

TY - CHAP

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

AU - Liu, Huiqun

AU - Wong, D.F.

PY - 1997/4

Y1 - 1997/4

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0030651819

U2 - 10.1145/267665.267673

DO - 10.1145/267665.267673

M3 - Chapter

AN - SCOPUS:0030651819

SN - 9780897919272

T3 - Proceedings of 1997 international symposium on Physical design, ISPD '97

SP - 12

EP - 17

BT - 1997 international symposium on Physical design, ISPD '97

PB - Association for Computing Machinery (ACM)

T2 - 1997 International Symposium on Physical Design, ISPD 1997

Y2 - 14 April 1997 through 16 April 1997

ER -

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

Abstract

Publication series

Symposium

Access to Document

Other files and links

Fingerprint

Cite this