MIN-CUT REPLICATION IN PARTITIONED NETWORKS

Logic replication has been shown empirically to reduce pin count and p artition size in partitioned networks. This paper presents the first t heoretical treatment of the min-cut replication problem, which is to d etermine replicated logic that minimizes cut size. A polynomial time a lgorithm for determining min-cut replication sets for k-partitioned gr aphs is derived by reducing replication to the problem of finding a ma ximum how. The algorithm is extended to hypergraphs and replication he uristics are proposed for the NP-hard problem with size constraints on partition components. These heuristics, which reduce the worst-case r unning time by a factor of O(k(2)) over previous methods, are applied to designs that have been partitioned into multiple FPGA's. Experiment al results demonstrate that min-cut replication provides substantial r eductions in the numbers of FPGA's and pins required.