TY - JOUR
T1 - Optimal min-area min-cut replication in partitioned circuits
AU - Yang, H. H.
AU - Wong, D. F.
N1 - Funding Information:
Manuscript received April 21, 1998. This work was supported in part by the Texas Advanced Research Program under Grant 003658288, in part by an Intel Foundation Graduate Fellowship, in part by a DAC Design Automation Scholarship, and in part by a grant from AT&T Bell Laboratories. A preliminary version of this paper appeared in the Proceedings of the IEEE International Conference on Computer-Aided Design, Nov. 1995. This paper was recommended by Associate Editor C. K. Cheng.
PY - 1998/11
Y1 - 1998/11
N2 - Previous results show that node replication can be used to reduce the number of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices such as multiple field-programmable gate array. Hwang and El Gamal [4], [5] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a fc-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding mincut replication sets for a fc-way partitioned digraph. However, as pointed out in [5], their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally 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 algorithms 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 MCRep in the TAPIR package on the exact same initial partitions of a set of MCNC Partition93 benchmark circuits. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep.
AB - Previous results show that node replication can be used to reduce the number of cut edges substantially in a partitioned circuit. The node replication approach is particularly useful for fully utilizing pin-limited devices such as multiple field-programmable gate array. Hwang and El Gamal [4], [5] formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a fc-way partition such that the cut size of the partition is minimized after the replication. They gave an optimal algorithm for finding mincut replication sets for a fc-way partitioned digraph. However, as pointed out in [5], their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. Furthermore, their algorithm is not optimal for hypergraphs. In this paper, we optimally 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 algorithms 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 MCRep in the TAPIR package on the exact same initial partitions of a set of MCNC Partition93 benchmark circuits. On average, Hyper-MAMC produces 57.3% fewer cut nets and runs much faster than MC-Rep.
UR - http://www.scopus.com/inward/record.url?scp=0032206224&partnerID=8YFLogxK
U2 - 10.1109/43.736190
DO - 10.1109/43.736190
M3 - Journal article
AN - SCOPUS:0032206224
SN - 0278-0070
VL - 17
SP - 1175
EP - 1183
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 11
ER -