面向位图的K-团枚举问题GPU优化算法
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

TP301

基金项目:

国家自然科学基金 (T2125013, 62032023); 国家重点研发计划(2023YFB3001902)


GPU Optimization Algorithm for Bitmap-oriented K-clique Enumeration Question
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    K-团枚举是子图匹配中的一个重要问题, 位图算法被证明是求解K-团枚举问题的有效方法. 目前最先进的K-团枚举算法都采用GPU来加速. 先前工作没有关注真实世界图数据的稀疏性对基于位图的K-团枚举算法的影响, 而是在GPU上采用静态的并行方法和位图构造策略, 这导致GPU计算效率低下. 提出了基于thread并行的位图任务负载均衡调度算法, 在解决线程分歧问题的同时实现位图算法的高并行性. 随后, 提出了一种动态位图构造算法, 使得位图可以在合适的时机被构造并高效启用位图算法. 实现了一个GPU友好的K-团枚举问题求解系统KCMiner, 它可以自适应地选择K-团枚举任务的优化策略. 在GPU架构上的实验结果表明, 方法能够比K-团枚举的基线算法最大实现7.36倍的加速, 与子图匹配系统的基线算法相比最大实现30.2倍的加速.

    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.

    参考文献
    相似文献
    引证文献
引用本文

曹炜辰,孟轲,林志恒,谭光明.面向位图的K-团枚举问题GPU优化算法.软件学报,,():1-17

复制
相关视频

分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2025-01-22
  • 最后修改日期:2025-04-15
  • 录用日期:
  • 在线发布日期: 2026-01-14
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号