MULTIWAY PARTITIONING VIA GEOMETRIC EMBEDDINGS, ORDERINGS, AND DYNAMIC-PROGRAMMING

This paper presents effective algorithms for multiway partitioning, Co nfirming ideas originally due to Hall, we demonstrate that geometric e mbeddings of the circuit netlist can lead to high-quality k-way partit ionings. The netlist embeddings are derived via the computation of d e igenvectors 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, a nd find that they are limited because they do not integrate topologica l information from the netlist. Thus, we also present a new partitioni ng algorithm that exploits both the geometric embedding and netlist in formation, as well as a Restricted Partitioning formulation that requi res 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 (combinin g spacefilling curve with 3-Opt approaches originally proposed for the traveling salesman problem), We then apply dynamic programming to eff iciently compute the optimal k-way split of the ordering for a variety of objective functions, including Scaled Cost and Absorption, This ap proach can transparently integrate user-specified cluster size bounds. Experiments show that this technique yields multiway partitionings wi th lower Scaled Cost than previous spectral approaches.