NEW SPECTRAL METHODS FOR RATIO CUT PARTITIONING AND CLUSTERING

Partitioning of circuit netlists is important in many phases of VLSI design, ranging from layout to testing and hardware simulation. The ratio cut objective function [291 has received much attention since it naturally captures both min-cut and equipartition, the two traditional goals of partitioning. In this paper, we show that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approximation of the optimal ratio cut partition cost. We also demonstrate that fast Lanczos-type methods for the sparse symmetric eigenvalue problem are a robust basis for computing heuristic ratio cuts based on the eigenvector of this second eigenvalue. Effective clustering methods are an immediate byproduct of the second eigenvector computation, and are very successful on the "difficult" input classes proposed in the CAD literature. Finally, we discuss the very natural intersection graph representation of the circuit netlist as a basis for partitioning, and propose a heuristic based on spectral ratio cut partitioning of the netlist intersection graph. Our partitioning heuristics were tested on industry benchmark suites, and the results compare favorably with those of Wei and Cheng [29], [32] in terms of both solution quality and runtime. This paper concludes by describing several types of algorithmic speedups and directions for future work.