Accelerating k-Core Decomposition by a GPU
Accelerating k-Core Decomposition by a GPU
复制标题
DOI：
10.1109/icde55515.2023.00142
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Akhlaque Ahmad;Lyuheng Yuan;Da Yan;Guimu Guo;Jieyang Chen;Chengcui Zhang
中科院分区：
文献类型：
--
作者：
Akhlaque Ahmad;Lyuheng Yuan;Da Yan;Guimu Guo;Jieyang Chen;Chengcui Zhang
图的k-核是最小度k的最大导出子图，k-核分解问题是对k的所有有效值寻找图的k-核，它在网络分析、计算生物学、图可视化等领域有着广泛的应用。目前，k-core分解的并行算法有两种：(1)基于度的顶点剥离算法和(2)迭代h-index求精算法。然而，关于使用GPU加速k核分解的研究很少。在本文中，我们提出了一种在GPU上高度优化的剥离算法，并将其与在类顶点图并行GPU系统上的可能实现以及在CPU上现有的串行和并行k-core分解算法进行了比较。大量的实验表明，我们的GPU算法在时间和空间上都是全面的赢家。我们的源代码在https://github.com/akhlaqueak/KCoreGPU.上发布
The k-core of a graph is the largest induced sub-graph with minimum degree k. The problem of k-core decomposition finds the k-cores of a graph for all valid values of k, and it has many applications such as network analysis, computational biology and graph visualization. Currently, there are two types of parallel algorithms for k-core decomposition: (1) degree-based vertex peeling, and (2) iterative h-index refinement. There is, however, few studies on accelerating k-core decomposition using GPU. In this paper, we propose a highly optimized peeling algorithm on a GPU, and compare it with possible implementations on top of think-like-a-vertex graph-parallel GPU systems as well as existing serial and parallel k-core decomposition algorithms on CPUs. Extensive experiments show that our GPU algorithm is the overall winner in both time and space. Our source code is released at https://github.com/akhlaqueak/KCoreGPU.