用谱方法提升超图划分质量,显著减少连接边数。
SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning
- 基于流与有效电阻的谱聚类策略进行超图粗化
- 在真实VLSI设计数据集上实现更优的划分质量
- 适合大规模超图划分任务及电路设计领域研究者
现有超图划分器采用多层粗化策略,逐层构建更粗糙的超图以指导切割优化。传统方法依赖启发式粗化,忽略超图结构特征。本文提出多层谱框架SHyPar,结合超边有效电阻与基于流的社区检测技术,将大规模超图分解为跨分区超边极少(切割大小小)的子图。其核心是基于最大流的局部聚类算法,生成导通性显著提升的簇;同时利用有效电阻评分函数合并强连接节点。在真实VLSI设计数据集上的大量实验表明,相较现有最优方法,SHyPar能更高效地划分超图,达到当前最优解质量。
原文摘要 · Abstract (English)
State-of-the-art hypergraph partitioners utilize a multilevel paradigm to construct progressively coarser hypergraphs across multiple layers, guiding cut refinements at each level of the hierarchy. Traditionally, these partitioners employ heuristic methods for coarsening and do not consider the structural features of hypergraphs. In this work, we introduce a multilevel spectral framework, SHyPar, for partitioning large-scale hypergraphs by leveraging hyperedge effective resistances and flow-based community detection techniques. Inspired by the latest theoretical spectral clustering frameworks, such as HyperEF and HyperSF, SHyPar aims to decompose large hypergraphs into multiple subgraphs with few inter-partition hyperedges (cut size). A key component of SHyPar is a flow-based local clustering scheme for hypergraph coarsening, which incorporates a max-flow-based algorithm to produce clusters with substantially improved conductance. Additionally, SHyPar utilizes an effective resistance-based rating function for merging nodes that are strongly connected (coupled). Compared with existing state-of-the-art hypergraph partitioning methods, our extensive experimental results on real-world VLSI designs demonstrate that SHyPar can more effectively partition hypergraphs, achieving state-of-the-art solution quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。