Wk. Mak et Df. Wong, MINIMUM REPLICATION MIN-CUT PARTITIONING, IEEE transactions on computer-aided design of integrated circuits and systems, 16(10), 1997, pp. 1221-1227
Logic replication has been shown to be very effective in reducing the
number of cut nets in partitioned circuits, Liu et al. in [8] consider
ed the circuit partitioning problem with logic replication for separat
ing two given nodes and presented an algorithm to determine a partitio
ning of the minimum possible cut size. In general, there are many poss
ible partitioning solutions with the minimum cut size and the differen
ce in the required amount of replication by these solutions can be sig
nificant. Since there is a size constraint on each component of the pa
rtitioning 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 require
s minimum replication, And we show that the algorithm can be generaliz
ed to separate two given subsets of nodes giving an optimum partitioni
ng of the minimum possible cut size using the least possible amount of
replication, We also show that our algorithm can be used to improve t
he solutions produced by any existing size-constrained replication min
-cut partitioning algorithm by reducing the cut size and shrinking the
replication set.