AN IMPROVED 2-WAY PARTITIONING ALGORITHM WITH STABLE PERFORMANCE

In this paper, we present a two-way partitioning algorithm that significantly improves on the highly unstable results typically obtained from the traditional Kernighan-Lin based algorithms. The algorithm groups highly connected components into clusters and rearranges the clusters into two final subsets with specified sizes. It is known that the grouping operations reduce the complexity, and thus improve the results, of partitioning very large circuits. However, if the grouping is inappropriate, the partitioning results may degenerate. To prevent degeneration, we use a ratio cut approach to do the grouping. By a series of experiments based on the trade-off between cut weight and CPU time, we determine the value which controls the resultant number of groups. Good experimental results have been observed for cut weight and CPU time.