Logic replication has been shown empirically to reduce pin count and partition size in partitioned networks. This paper presents the first theoretical treatment of the min-cut replication problem, which is to determine replicated logic that minimizes cut size. A polynomial time algorithm for determining min-cut replication sets for k-partitioned graphs is derived by reducing replication to the problem of finding a maximum flow. The algorithm is extended to hypergraphs and replication heuristics are proposed for the NP-hard problem with size constraints on partition components. These heuristics, which reduce the worst-case running time by a factor of O(k/sup 2/) over previous methods, are applied to designs that have been partitioned into multiple FPGA's. Experimental results demonstrate that min-cut replication provides substantial reductions in the numbers of FPGA's and pins required.>

Heuristics for replicating logic have been shown to reduce pin count and wiring density in partitioned logic networks. An efficient algorithm for determining an optimal min-cut replication set for a k-partitioned graph in O(knm log (n/sup 2//m)) time is presented. For the NP-hard case with limited size partition components, a replication heuristic which reduces the worst-case running time by a factor of O(k/sup 2/) over previous methods is proposed. Experimental results are presented.>