Search papers, labs, and topics across Lattice.
This paper introduces HySpecPro, a novel single-level hypergraph partitioner that leverages spectral projection optimization for end-to-end partitioning in VLSI design. By constructing embeddings from a bipartite Laplacian and utilizing a fully GPU-accelerated implementation, HySpecPro addresses the limitations of traditional multilevel partitioning methods, particularly in handling high-degree hyperedges. Experimental results demonstrate that HySpecPro achieves cut quality on par with leading multilevel techniques while maintaining linear scalability with respect to hyperedge degree.
HySpecPro achieves state-of-the-art cut quality in hypergraph partitioning while scaling linearly with hyperedge degree, challenging the dominance of multilevel methods.
Modern VLSI designs comprise tens of billions of components, making scalable hypergraph partitioning critical for parallel and hierarchical optimization. Although multilevel partitioning remains the dominant paradigm, its coarsening stage can distort structural information, especially in hypergraphs with many high-degree hyperedges, leading to increased refinement overhead and limited scalability. Recent approaches incorporate spectral information to guide coarsening, but only in a heuristic manner, without directly optimizing the partitioning objectives. We introduce HySpecPro, a single-level hypergraph partitioner that performs end-to-end optimization in a spectral embedding space. HySpecPro constructs embeddings from a bipartite Laplacian and performs efficient projection-based search, supported by a fully GPU-accelerated implementation. Experiments show that HySpecPro delivers cut quality comparable to state-of-the-art multilevel methods while scaling linearly with the total hyperedge degree.
