Multiway partitioning via geometric embeddings, orderings, and dynamic programming

Abstract

This paper presents effective algorithms for multiway partitioning. Confirming ideas originally due to Hall (1970), we 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, we explore various geometric partitioning objectives and algorithms, and find that they are limited because they do not integrate topological information from the netlist. Thus, we 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. We 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). We 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 Sealed Cost than previous spectral approaches