A simple yet effective technique for partitioning
- 1 September 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 1 (3) , 380-386
- https://doi.org/10.1109/92.238449
Abstract
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.Keywords
This publication has 12 references indexed in Scilit:
- An improved objective function for mincut circuit partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Performance of a new annealing schedulePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An experimental evaluation of partitioning algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Congestion-driven placement using a new multi-partitioning heuristicPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- New spectral methods for ratio cut partitioning and clusteringIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- A general purpose multiple way partitioning algorithmPublished by Association for Computing Machinery (ACM) ,1991
- An evolution-based approach to partitioning ASIC systemsPublished by Association for Computing Machinery (ACM) ,1989
- Multiple-way network partitioningIEEE Transactions on Computers, 1989
- An Improved Min-Cut Algonthm for Partitioning VLSI NetworksIEEE Transactions on Computers, 1984
- Optimization by Simulated AnnealingScience, 1983