DocumentCode :
1344839
Title :
Minimum replication min-cut partitioning
Author :
Mak, Wai-Kei ; Wong, D.F.
Author_Institution :
Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
Volume :
16
Issue :
10
fYear :
1997
fDate :
10/1/1997 12:00:00 AM
Firstpage :
1221
Lastpage :
1227
Abstract :
Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. Liu et al. (see IEEE Trans. Computer-Aided Design, vol. 14, p. 623-30, May 1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference in the required amount of replication by these solutions can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes giving an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any existing size-constrained replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set
Keywords :
VLSI; circuit layout CAD; circuit optimisation; directed graphs; integrated circuit layout; integrated logic circuits; logic CAD; logic partitioning; VLSI design; circuit partitioning problem; logic replication; minimum replication min-cut partitioning; network-flow based algorithm; partitioned circuits; Costs; Logic circuits; Partitioning algorithms; Very large scale integration;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/43.662685
Filename :
662685
Link To Document :
بازگشت