This paper presents effective algorithms for multiway partitioning. Confirming ideas originally due to Hall, the authors demonstrate that geometric embeddings of the circuit netlist can lead to high-quality k-way partitionings. The netlist embeddings are derived via the computation of d eigenvectors of the Laplacian for a graph representation of the netlist. As Hall did not specify how to partition such geometric embeddings, the authors explore various geometric partitioning objectives and algorithms, and find that they are limited because they do not integrate topological information from the netlist. Thus, they also present a new partitioning algorithm that exploits both the geometric embedding and netlist information, as well as a Restricted Partitioning formulation that requires each cluster of the K-way partitioning to be contiguous in a given linear ordering. The authors begin with a d-dimensional spectral embedding and construct a heuristic 1-dimensional ordering of the modules (combining spacefilling curve with 3-Opt approaches originally proposed for the traveling salesman problem). They then apply dynamic programming to efficiently compute the optimal k-way split of the ordering for a variety of objective functions, including Scaled Cost and Absorption. This approach can transparently integrate user-specified cluster size bounds. Experiments show that this technique yields multiway partitionings with lower Scaled Cost than previous spectral approaches.
