An efficient eigenvector approach for finding netlist partitions

Abstract

A fast eigenvector technique for obtaining good initial node partitions of netlists for use in interchange heuristics is described. The method is based on approximating the netlist or hypergraph by a weighted graph G, such that the sum of the cut edges in G tightly underestimates the number of cut nets in any netlist partition. An eigenvector technique is used to partition the graph G into k blocks of fixed module size. Another feature of this graph underestimation model of the netlist is that it allows one to obtain lower bounds on the actual number of cut nets. A multiblock node interchange heuristic is tested on the one resulting netlist partition obtained by this eigenvector approach on a variety of small to large sized benchmark netlist partitioning problems (between 300 to 12000 modules and nets). Test results on the larger netlists show that in most cases this eigenvector-node interchange approach yields netlist partitions with comparable or fewer cut nets than the best netlist partitions obtained by using node interchange heuristics alone on many random initial netlist partitions.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>