论文标题
一种用于中间性中心计算的细粒杂交CPU-GPU算法
A Fine-Grained Hybrid CPU-GPU Algorithm for Betweenness Centrality Computations
论文作者
论文摘要
中心中心（BC）是大规模图的重要图分析应用。尽管在多核CPU和多核GPU上平行中间性中心算法有许多努力，但在这项工作中，我们提出了一种新型的细粒度CPU-GPU混合算法，该算法将图形分配到CPU和GPU分区中，并在CPU CPU和GPU中执行较小的CPU和GPU资源的图形，并将其划分为GPU和GPU的图形。混合BC算法中的远期阶段利用BC问题固有的多源属性。我们还执行了一种新型的混合和异步向后相，该相具有最小的CPU-GPU同步。使用大量具有不同特征的图表的评估表明，与现有的基于流行的散装同步范式（BSP）方法相比，与现有的混合算法相比，我们的混合方法的性能提高了80％，CPU-GPU通信提高了80％，CPU-GPU通信降低了80-90％。
Betweenness centrality (BC) is an important graph analytical application for large-scale graphs. While there are many efforts for parallelizing betweenness centrality algorithms on multi-core CPUs and many-core GPUs, in this work, we propose a novel fine-grained CPU-GPU hybrid algorithm that partitions a graph into CPU and GPU partitions, and performs BC computations for the graph on both the CPU and GPU resources simultaneously with very small number of CPU-GPU communications. The forward phase in our hybrid BC algorithm leverages the multi-source property inherent in the BC problem. We also perform a novel hybrid and asynchronous backward phase that performs minimal CPU-GPU synchronizations. Evaluations using a large number of graphs with different characteristics show that our hybrid approach gives 80% improvement in performance, and 80-90% less CPU-GPU communications than an existing hybrid algorithm based on the popular Bulk Synchronous Paradigm (BSP) approach.
