An efficient eigenvector approach for finding netlist partitions

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