Search for: All records

State-of-the-art hypergraph partitioners follow the multilevel paradigm that constructs multiple levels of progressively coarser hypergraphs that are used to drive cut refinements on each level of the hierarchy. Multilevel partitioners are subject to two limitations: (i) Hypergraph coarsening processes rely on local neighborhood structure without fully considering the global structure of the hypergraph. (ii) Refinement heuristics can stagnate on local minima. In this paper, we describe SpecPart, the first supervised spectral framework that directly tackles these two limitations. SpecPart solves a generalized eigenvalue problem that captures the balanced partitioning objective and global hypergraph structure in a low-dimensional vertex embedding while leveraging initial high-quality solutions from multilevel partitioners as hints. SpecPart further constructs a family of trees from the vertex embedding and partitions them with a tree-sweeping algorithm. Then, a novel overlay of multiple tree-based partitioning solutions, followed by lifting to a coarsened hypergraph, where an ILP partitioning instance is solved to alleviate local stagnation. We have validated SpecPart on multiple sets of benchmarks. Experimental results show that for some benchmarks, our SpecPart can substantially improve the cutsize by more than 50% with respect to the best published solutions obtained with leading partitioners hMETIS and KaHyPar. 

Most state-of-the-art hypergraph partitioning algorithms follow a multilevel approach that constructs a hierarchy of coarser hypergraphs that in turn is used to drive partition refinements. These partitioners are widely accepted as the current standard, as they have proven to be quite effective. On the other hand, spectral partitioners are considered to be less effective in cut quality, and too slow to be used in industrial applications. In this work, we revisit spectral hypergraph partitioning and we demonstrate that the use of appropriate solvers eliminates the running time deficiency; in fact, spectral algorithms can compute competing solutions in a fraction of the time needed by standard partitioning algorithms, especially on larger designs. We also introduce several novel modifications in the common spectral partitioning workflow, that enhance significantly the quality of the computed solutions. We run our partitioner on FPGA benchmarks generated by an industry leader, generating solutions that are directly competitive both in runtime and quality.