Ci. Park et Yb. Park, AN EFFICIENT ALGORITHM FOR VLSI NETWORK PARTITIONING PROBLEM USING A COST FUNCTION WITH BALANCING FACTOR, IEEE transactions on computer-aided design of integrated circuits and systems, 12(11), 1993, pp. 1686-1694
This paper presents an efficient algorithm for network partitioning pr
oblem, which improves Fiduccia and Mattheyses' (F-M's) algorithm [1].
We have noticed that the main problem of F-M's algorithm is that the c
ell move operation is largely influenced by the balancing constraint.
In order to handle this kind of inherent limitation in F-M's algorithm
, a cost function similar to the penalty function used in [121 is adop
ted which reflects balance degree of a partition as well as its cutset
size. The weighting factor R is introduced in the cost function to de
termine the relative importances of the two factors: cutset size and b
alance degree. Using this cost function, we propose an iterative impro
vement algorithm which has the time complexity of O (b (m + c2)), wher
e b is the number of blocks, m is the size of network, and c is the nu
mber of cells. It is proven that the proposed algorithm guarantees to
find a balanced partition if the value of R satisfies a certain condit
ion. Experimental results show that the proposed algorithm outperforms
F-M's algorithm in most cases.