New algorithms for min-cut replication in partitioned circuits

Hannah Honghua Yang, Martin D F Wong

Research output: Contribution to journalConference article

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 languageEnglish (US)
Pages (from-to)216-222
Number of pages7
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Dec 1 1995
Externally publishedYes
EventProceedings of the 1995 IEEE/ACM International Conference on Computer-Aided Design - San Jose, CA, USA
Duration: Nov 5 1995Nov 9 1995

    Fingerprint

ASJC Scopus subject areas

  • Software

Cite this