| 摘要: |
| K-团枚举是子图匹配中的一个重要问题, 位图算法被证明是求解K-团枚举问题的有效方法. 目前最先进的K-团枚举算法都采用GPU来加速. 先前工作没有关注真实世界图数据的稀疏性对基于位图的K-团枚举算法的影响, 而是在GPU上采用静态的并行方法和位图构造策略, 这导致GPU计算效率低下. 提出了基于thread并行的位图任务负载均衡调度算法, 在解决线程分歧问题的同时实现位图算法的高并行性. 随后, 提出了一种动态位图构造算法, 使得位图可以在合适的时机被构造并高效启用位图算法. 实现了一个GPU友好的K-团枚举问题求解系统KCMiner, 它可以自适应地选择K-团枚举任务的优化策略. 在GPU架构上的实验结果表明, 方法能够比K-团枚举的基线算法最大实现7.36倍的加速, 与子图匹配系统的基线算法相比最大实现30.2倍的加速. |
| 关键词: K-团枚举 子图匹配 位图算法 GPU 性能优化 |
| DOI：10.13328/j.cnki.jos.007558 |
| 分类号:TP301 |
| 基金项目:国家自然科学基金 (T2125013, 62032023); 国家重点研发计划(2023YFB3001902) |
|
| GPU Optimization Algorithm for Bitmap-oriented K-clique Enumeration Question |
|
CAO Wei-Chen1,2, MENG Ke1,2, LIN Zhi-Heng1,2, TAN Guang-Ming1,2
|
|
1.State Key Lab of Processors (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190, China;2.University of Chinese Academy of Sciences, Beijing 100049, China
|
| Abstract: |
| K-clique enumeration is an important problem in subgraph matching, and the bitmap algorithm has been proven to be an effective method for solving the K-clique enumeration problem. Currently, state-of-the-art K-clique enumeration algorithms are accelerated by GPU. Previous studies have not investigated the impact of sparsity in real-world graph data on bitmap-based K-clique enumeration algorithms. Instead, static parallelization methods and bitmap construction strategies are commonly used on GPU, which result in low computational efficiency. This study proposes a thread-parallel load-balancing scheduling algorithm for bitmap tasks, which resolves the thread divergence problem while achieving high parallelism in the bitmap algorithm. Furthermore, it introduces a dynamic bitmap construction algorithm, enabling bitmaps to be constructed and activated at appropriate times for efficient execution of the bitmap algorithm. A GPU-friendly K-clique enumeration system, KCMiner, is implemented, which adaptively selects optimization strategies for K-clique enumeration tasks. Experimental results on GPU platforms show that the proposed method achieves up to 7.36 times speedup over the baseline K-clique enumeration algorithm and up to 30.2 times speedup over the baseline subgraph matching system. |
| Key words: K-clique enumeration subgraph matching bitmap algorithm GPU performance optimization |
