Optimal min-area min-cut replication in partitioned circuits

Hannah Honghua Yang, D. F. Wong

Research output: Contribution to journalArticlepeer-review

Abstract

Previous results show that node replication can be used to reduce the number of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices such as multiple field-programmable gate array. Hwang and El Gamal [4], [5] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a fc-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding mincut replication sets for a fc-way partitioned digraph. However, as pointed out in [5], 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 important, 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 [5]. We compared the replication results by Hyper-MAMC with those obtained by MCRep in the TAPIR package on the exact same initial partitions of a set of MCNC Partition93 benchmark circuits. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep.

Original languageEnglish (US)
Pages (from-to)1175-1183
Number of pages9
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume17
Issue number11
DOIs
StatePublished - Dec 1 1998
Externally publishedYes

Keywords

  • -circuit netlist
  • Hypergraph
  • Min-area
  • Min-cut
  • Network flow
  • Partitioning
  • Replication

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Optimal min-area min-cut replication in partitioned circuits'. Together they form a unique fingerprint.

Cite this