Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics
Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics
复制标题
重新审视动态 GPU 图形分析的边缘和节点并行性
DOI：
10.1109/ipdpsw.2014.157
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
David A. Bader
中科院分区：
文献类型：
--
作者：
Adam McLaughlin;David A. Bader
介数中心性（Betweenness Centrality）是一种广泛使用的图分析，其应用包括在社交网络中寻找有影响力的人，分析电网和研究蛋白质相互作用。然而，它的复杂性使得它的精确计算对于感兴趣的大型图是不可行的。此外，网络往往会随着时间的推移而变化，使先前计算的结果无效，并鼓励对中心性指标如何随时间变化进行新的分析。虽然GPU在常规的结构化应用领域占据主导地位，但其高内存吞吐量和大规模并行性也使其成为不规则的非结构化应用的合适目标架构。在本文中，我们比较和对比两个GPU实现的动态介数中心的算法。我们发现，典型的网络更新影响的中心分数的一个令人惊讶的小子集的顶点总数在图中。通过有效地将线程映射到工作单元，我们在CPU实现算法的基础上实现了高达110倍的加速，并且可以比GPU上的静态重新计算平均快45倍地更新分析。
Betweenness Centrality is a widely used graph analytic that has applications such as finding influential people in social networks, analyzing power grids, and studying protein interactions. However, its complexity makes its exact computation infeasible for large graphs of interest. Furthermore, networks tend to change over time, invalidating previously calculated results and encouraging new analyses regarding how centrality metrics vary with time. While GPUs have dominated regular, structured application domains, their high memory throughput and massive parallelism has made them a suitable target architecture for irregular, unstructured applications as well. In this paper we compare and contrast two GPU implementations of an algorithm for dynamic betweenness centrality. We show that typical network updates affect the centrality scores of a surprisingly small subset of the total number of vertices in the graph. By efficiently mapping threads to units of work we achieve up to a 110x speedup over a CPU implementation of the algorithm and can update the analytic 45x faster on average than a static recomputation on the GPU.