高级检索

    Saturn: 面向Multi-GPU平台的高性能图模式挖掘系统

    Saturn: High Performance Graph Pattern Mining System on Multi-GPU platform

    • 摘要: 图模式挖掘作为分析实体关系的核心任务,在社区检测、药物发现等领域具有广泛应用.但由于其非多项式时间复杂度,大规模图数据处理面临搜索空间爆炸与计算效率低下的挑战.现有基于GPU的加速方案虽利用并行计算提升性能,但受限于图数据幂律分布导致的线程空闲问题,以及多GPU场景下频繁的CPU介入通信开销,难以充分释放硬件算力.本文提出GPU图模式挖掘系统Saturn,通过计算与通信协同优化突破上述瓶颈:在计算层面,将集合操作的装载与查询阶段解耦,采用细粒度并行批处理策略动态适配哈希与二分查找算法,并结合共享内存缓存优化访存效率,显著提升线程利用率;在通信层面,构建CPU无感的全GPU通信模式,利用NVLink高带宽链路与统一内存机制实现跨设备数据直接访问,通过顶点缓存与消息聚合调度降低冗余传输与链路竞争.实验结果表明,Saturn在真实数据集上相比主流GPU图挖掘系统,实现了更高的计算并行效率与跨设备通信能效,为大规模图模式挖掘任务提供了高效解决方案.

       

      Abstract: Graph pattern mining, as a core task for analyzing entity relationships, finds extensive applications in fields such as community detection and drug discovery. However, due to its non-polynomial time complexity, large-scale graph processing encounters challenges related to search space explosion and low computational efficiency. Existing GPU-accelerated solutions utilize parallel computing to enhance performance but often suffer from thread idleness caused by the power-law distribution of graph data and excessive CPU intervention in multi-GPU communication, which impede the full utilization of hardware capabilities. This paper presents Saturn, a GPU-based graph pattern mining system, which overcomes the above bottlenecks through computation-communication co-optimization. At computation level, Saturn decouples the loading and querying phases of set operations, employs fine-grained parallel batch processing to dynamically adapt hash and binary search algorithms, and optimizes memory access efficiency via shared memory caching, significantly improving thread utilization. At communication level, it establishes a CPU-free GPU communication model, leveraging high-bandwidth NVLink interconnect and unified memory mechanism for direct cross-device data access, while reducing redundant transmission and link contention through vertex caching and message aggregation scheduling. Experimental results demonstrate that Saturn outperforms state-of-the-art GPU-based graph mining systems on real-world datasets, achieving superior computational parallel efficiency and cross-device communication effectiveness for large-scale graph pattern mining tasks.

       

    /

    返回文章
    返回