SpecPart: A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement
SpecPart: A Supervised Spectral Framework for Hypergraph Partitioning Solution Improvement
复制标题
SpecPart：用于改进超图分区解决方案的监督谱框架
DOI：
10.1145/3508352.3549390
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Wang, Zhiang
中科院分区：
文献类型：
--
作者：
Bustany, Ismail;Kahng, Andrew B.;Koutis, Ioannis;Pramanik, Bodhisatta;Wang, Zhiang
最先进的超图划分器遵循多级范式，该范式构造多个级别的逐渐粗糙的超图，这些超图用于驱动层次结构的每个级别上的切割细化。多级划分器受到两个限制：（i）超图粗化过程依赖于局部邻域结构，而没有充分考虑超图的全局结构。(ii)精化算法可能会停滞在局部最小值上。在本文中，我们描述SpecPart，SpecPart是第一个直接解决这两个限制的监督谱框架。SpecPart解决了一个广义特征值问题，该问题在低维顶点嵌入中捕获平衡划分目标和全局超图结构，同时利用来自多级划分器的初始高质量解决方案作为提示。SpecPart进一步从顶点嵌入构建了一个树族，并用树进行划分。扫描算法然后，一种新的覆盖多个基于树的分区解决方案，然后提升到一个粗超图，其中一个ILP分区实例被解决，以减轻局部停滞。我们已经验证了SpecParton多套基准测试。实验结果表明，对于一些基准测试，我们的SpecPart可以大大提高cutsize超过50%的最佳公布的解决方案与领先的partitionershMETI和KaHyPar。
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 describeSpecPart, the first supervised spectral framework that directly tackles these two limitations.SpecPartsolves 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.SpecPartfurther 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 validatedSpecParton multiple sets of benchmarks. Experimental results show that for some benchmarks, ourSpecPartcan substantially improve the cutsize by more than 50% with respect to the best published solutions obtained with leading partitionershMETISandKaHyPar.
登录
查看更多内容
直接 k 路超图分区的工程初始分区算法
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
Tobias Heuer
通讯作者：
Tobias Heuer
2.5D FPGA 结构架构的布局策略
DOI：
--
发表时间：
2018
期刊：
International Conference on Field-Programmable Logic and Applications
影响因子：
--
作者：
C. Ravishankar;D. Gaitonde;T. Bauer
通讯作者：
T. Bauer
PaToH（超图分区工具）
影响因子：
2.5
作者：
Ümit V. Çatalyürek;C. Aykanat
通讯作者：
C. Aykanat
DOI：
10.1145/3329872
发表时间：
2018
期刊：
Journal of Experimental Algorithmics (JEA)
影响因子：
--
作者：
Tobias Heuer;P. Sanders;Sebastian Schlag
通讯作者：
Sebastian Schlag