New algorithms for min-cut replication in partitioned circuits

Hannah Honghua Yang; D. F. Wong

doi:10.1109/ICCAD.1995.480015

New algorithms for min-cut replication in partitioned circuits

Hannah Honghua Yang, D. F. Wong

Office of the Provost

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

16 Citations (Scopus)

Abstract

Hwang and El Gamal [HE92, HE95] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package [HE95]. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.

Original language	English
Title of host publication	1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995
Publisher	IEEE
Pages	216-222
Number of pages	7
ISBN (Print)	0818672137, 0818682000
DOIs	https://doi.org/10.1109/ICCAD.1995.480015
Publication status	Published - Nov 1995
Event	1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995 - San Jose, United States Duration: 5 Nov 1995 → 9 Nov 1995 https://ieeexplore.ieee.org/xpl/conhome/3472/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

Conference

Conference	1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995
Country/Territory	United States
City	San Jose
Period	5/11/95 → 9/11/95
Internet address	https://ieeexplore.ieee.org/xpl/conhome/3472/proceeding (Link to conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.1995.480015

Cite this

@inbook{1ec70a31c13047ad8e4db2f1ac2f7609,

title = "New algorithms for min-cut replication in partitioned circuits",

abstract = "Hwang and El Gamal [HE92, HE95] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package [HE95]. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.",

author = "Yang, {Hannah Honghua} and Wong, {D. F.}",

note = "Funding Information: *This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by an Intel Foundation Graduate Fellowship, and by a DAC Design Automation Scholarship. Publisher Copyright: {\textcopyright} 1995 IEEE ; 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995 ; Conference date: 05-11-1995 Through 09-11-1995",

year = "1995",

month = nov,

doi = "10.1109/ICCAD.1995.480015",

language = "English",

isbn = "0818672137",

series = "Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995",

publisher = "IEEE",

pages = "216--222",

booktitle = "1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/3472/proceeding",

}

Yang, HH & Wong, DF 1995, New algorithms for min-cut replication in partitioned circuits. in 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995. Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995, IEEE, pp. 216-222, 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995, San Jose, California, United States, 5/11/95. https://doi.org/10.1109/ICCAD.1995.480015

New algorithms for min-cut replication in partitioned circuits. / Yang, Hannah Honghua; Wong, D. F.
1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995. IEEE, 1995. p. 216-222 (Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995).

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

TY - CHAP

T1 - New algorithms for min-cut replication in partitioned circuits

AU - Yang, Hannah Honghua

AU - Wong, D. F.

N1 - Funding Information: *This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by an Intel Foundation Graduate Fellowship, and by a DAC Design Automation Scholarship. Publisher Copyright: © 1995 IEEE

PY - 1995/11

Y1 - 1995/11

N2 - Hwang and El Gamal [HE92, HE95] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package [HE95]. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.

AB - Hwang and El Gamal [HE92, HE95] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. However, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. We implemented our algorithms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package [HE95]. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep in the TAPIR package, on the same initial partitions of a set of MCNC Partition93 benchmark circuits.

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

U2 - 10.1109/ICCAD.1995.480015

DO - 10.1109/ICCAD.1995.480015

M3 - Chapter

AN - SCOPUS:0029516534

SN - 0818672137

SN - 0818682000

T3 - Proceedings of 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

SP - 216

EP - 222

BT - 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

PB - IEEE

T2 - 1995 IEEE International Conference on Computer-Aided Design, ICCAD 1995

Y2 - 5 November 1995 through 9 November 1995

ER -

New algorithms for min-cut replication in partitioned circuits

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this