Ratio cut partitioning for hierarchical designs

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 cases.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>