Search papers, labs, and topics across Lattice.
This paper introduces ComPart, a novel framework for hypergraph partitioning that enhances the post-coarsening process by integrating various community detection methods to identify high-quality clusterings. By leveraging these community structures during the uncoarsening phase, ComPart enables the refinement process to escape local optima and explore more globally meaningful solution subspaces. Experimental results show that ComPart consistently outperforms existing state-of-the-art methods, providing superior partitioning solutions for complex embedded systems design.
Community structures can transform hypergraph partitioning, allowing for superior solutions that escape local optima.
Hypergraph partitioning is a critical step in the design of complex embedded systems, essential for optimizing task mapping on heterogeneous MPSoCs and enabling multi-FPGA prototyping. Many existing methods rely on community detection to identify modules with dense internal and sparse external connections, typically utilizing them to constrain the coarsening phase--a widely adopted paradigm. In this work, we propose ComPart, a generalized framework that integrates diverse community detection methods to uncover high-quality clusterings throughout the post-coarsening stages (i.e., initial partitioning and uncoarsening). These discovered clusterings serve as distinct structural guides, enabling the refinement process to identify superior partitioning solutions. Our framework offers two key advantages: (1) it establishes a new paradigm that leverages community structures detected during uncoarsening to escape local optima and explore globally meaningful solution subspaces, transcending the limitations of standard local refinements; and (2) it flexibly accommodates both existing and future community detection methods. Furthermore, we theoretically generalize locally-dense decomposition--originally from graphs--to the hypergraph domain. We provide the formal extension and necessary proofs to apply this technique to hypergraphs, marking its first application in hypergraph partitioning. Specifically, we utilize this rigorously derived decomposition to guide the initial partitioning phase toward superior starting points. Experimental results on standard benchmarks demonstrate that our method consistently outperforms state-of-the-art methods in solution quality.
