Optimal replication for min-cut partitioning
James Hwang, Abbas El Gamal · International Conference on Computer Aided Design · 1992
Heuristics for replicating logic have been shown to reduce pin count and wiring density in partitioned logic networks. We present an efficient algorithm for determining an optimal min-cuf replication set for a k-partitioned graph in O(knmlog(n2/m)) time. For the NP-hard case with limited size partition components, we propose a new replication heuristic which reduces the worst-case running time by a factor of O( k2) over previous methods. Ezperimental results are presented.