Min-cut replication 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, and a polynomial time algorithm for determining min- cut replication sets for k-partitioned graphs is derived.

Abstract

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.>