Minimum replication min-cut partitioning

Wai-Kei Mak, D. F. Wong

Research output: Chapter in book/report/conference proceedingChapterpeer-review

6 Citations (Scopus)

Abstract

Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. L.T. Liu et al. (1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference of their required amounts of replication can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes and determine an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any heuristic replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set.

Original languageEnglish
Title of host publication1996 IEEE/ACM International Conference on Computer-Aided Design
PublisherIEEE
Pages1221-1227
Number of pages7
ISBN (Print)0818675977
DOIs
Publication statusPublished - Nov 1997
Event1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996 - San Jose, United States
Duration: 10 Nov 199614 Nov 1996
https://ieeexplore.ieee.org/xpl/conhome/4215/proceeding (Link to conference proceedings)

Publication series

NameProceedings of 1996 IEEE/ACM International Conference on Computer-Aided Design

Conference

Conference1996 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 1996
Country/TerritoryUnited States
CitySan Jose
Period10/11/9614/11/96
Internet address

Scopus Subject Areas

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

Fingerprint

Dive into the research topics of 'Minimum replication min-cut partitioning'. Together they form a unique fingerprint.

Cite this