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

Huiqun Liu, Martin D F Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the International Symposium on Physical Design
PublisherACM
Pages12-17
Number of pages6
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1997 1st International Symposium on Physical Design, ISPD - Napa Valley, CA, USA
Duration: Apr 14 1997Apr 16 1997

Other

OtherProceedings of the 1997 1st International Symposium on Physical Design, ISPD
CityNapa Valley, CA, USA
Period4/14/974/16/97

Fingerprint

Networks (circuits)

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Liu, H., & Wong, M. D. F. (1997). Network flow based multi-way partitioning with area and pin constraints. In Proceedings of the International Symposium on Physical Design (pp. 12-17). ACM.

Network flow based multi-way partitioning with area and pin constraints. / Liu, Huiqun; Wong, Martin D F.

Proceedings of the International Symposium on Physical Design. ACM, 1997. p. 12-17.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Liu, H & Wong, MDF 1997, Network flow based multi-way partitioning with area and pin constraints. in Proceedings of the International Symposium on Physical Design. ACM, pp. 12-17, Proceedings of the 1997 1st International Symposium on Physical Design, ISPD, Napa Valley, CA, USA, 4/14/97.
Liu H, Wong MDF. Network flow based multi-way partitioning with area and pin constraints. In Proceedings of the International Symposium on Physical Design. ACM. 1997. p. 12-17
Liu, Huiqun ; Wong, Martin D F. / Network flow based multi-way partitioning with area and pin constraints. Proceedings of the International Symposium on Physical Design. ACM, 1997. pp. 12-17
@inproceedings{7b83100617a04c0eb4f61a7d939ca2b1,
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 Wong, {Martin D F}",
year = "1997",
language = "English (US)",
pages = "12--17",
booktitle = "Proceedings of the International Symposium on Physical Design",
publisher = "ACM",

}

TY - GEN

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

AU - Liu, Huiqun

AU - Wong, Martin D F

PY - 1997

Y1 - 1997

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 - http://www.scopus.com/inward/record.url?scp=0030651819&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030651819&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0030651819

SP - 12

EP - 17

BT - Proceedings of the International Symposium on Physical Design

PB - ACM

ER -