A simple yet effective technique for partitioning

Partitioning is an important step in the top-down design of large complicated integrated circuits. In this paper, a simple yet effective partitioning technique is described. It is based on the clustering of "closely" connected cells and the gradual enforcement of size-constraints. At the beginning, clusters are formed in the bottom-up fashion to reduce the problem size. Then the clusters are partitioned using several different parameters to find a good starting point. The best result achieved during the cluster partitioning is used as the initial solution for the lower level partitioning. The gradual constraint enforcement technique is used to cope with the local minimum problems. It allows cells or clusters to move with more freedom among the subsets during earlier iterations and thus may effectively find a near optimum solution. Several experimental results show that the new partitioning technique produces favorable results. In particular, the method outperforms the F&M method by more than 60% in the number of crossing nets on average.<>