Ratio cut partitioning for hierarchical designs
- 1 July 1991
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 10 (7) , 911-921
- https://doi.org/10.1109/43.87601
Abstract
Circuit partitioning for hierarchical VLSI design is addressed. A partitioning approach called ratio cut is proposed. It is demonstrated that the ratio cut algorithm can locate the clustering structures in the circuit. Finding the optimal ratio cut is NP-complete. However, in certain cases the ratio cut can be solved by linear programming techniques via the multicommodity flow formulation. Also proposed is a fast heuristic algorithm running in linear time with respect to the number of pins in the circuit. Experiments show good results in all tested casesKeywords
This publication has 11 references indexed in Scilit:
- An improved objective function for mincut circuit partitioningPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- 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
- Computer-Aided Partitioning of Behavioral Hardware DescriptionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- A Linear-Time Heuristic for Improving Network PartitionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Clustering and linear placementPublished by Association for Computing Machinery (ACM) ,1972
- On feasibility conditions of multicommodity flows in networksIEEE Transactions on Circuit Theory, 1971
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970
- Efficient partitioning of componentsPublished by Association for Computing Machinery (ACM) ,1968