Ratio cut partitioning for hierarchical designs

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 cases