Towards efficient hierarchical designs by ratio cut partitioning

Abstract

A partitioning approach called ratio cut is proposed. The authors demonstrate 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 problem. They also propose 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, and as much as 70% improvement over the Kernighan-Lin algorithm in terms of the proposed ratio metric.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>