Optimal min-area min-cut replication in partitioned circuits

Previous results show that node replication can be used to reduce the numbe r of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices su ch as multiple field-programmable gate array. Hwang and El Gamal [4], [5] f ormulated the min-cut replication problem, which is to determine min-cut re plication sets for the components of a k-way partition such that the cut si ze of the partition is minimized after the replication. They gave an optima l algorithm for finding min-cut replication sets for a k-way partitioned di graph, However, as pointed out in [5], their optimal min-cut replication al gorithm does not guarantee min-cut replication sets of minimum sizes; Furth ermore, their algorithm is not optimal for hypergraphs. In this paper, we o ptimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. More important, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model, We implemented our algori thms in a package called Hyper-MAMC, and interfaced Hyper-MAMC to the TAPIR package [5]. We compared the replication results by Hyper-MAMC with those obtained by MC-Rep in the TAPIR package on the exact same initial partition s of a set of MCNC Partition93 benchmark circuits. On average, Hyper-MAMC p roduces 57.3% fewer cut nets and runs much faster than MC-Rep.