Fast load balance parallel graph analytics with an automatic graph data structure selection algorithm
Fast load balance parallel graph analytics with an automatic graph data structure selection algorithm
复制标题
DOI：
10.1016/j.future.2020.06.005
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Jiawen Sun;Hans Vandierendonck;Dimitrios S. Nikolopoulos
中科院分区：
文献类型：
--
作者：
Jiawen Sun;Hans Vandierendonck;Dimitrios S. Nikolopoulos
本文研究了图结构分析在大规模共享内存系统上的性能。由于大数据集大小和不规则的数据访问模式，图分析对高效的图遍历有很高的要求。为了实现高效的图形分析，我们考虑并讨论了三种常见类型的图形数据结构的性能。此外，我们证明了负载平衡在很大程度上是由每个线程处理的边的数量和唯一的顶点数。最后，我们提出了一个自动的图数据结构选择算法和一个有效的重新排序作为预处理步骤，以平衡顶点和边的数量在一起。重排序算法还优化平衡了具有幂律度分布的图的边和顶点，并确保了线程之间的均匀度分布。所开发的技术在GraphGrind中实现，这是一个新的共享内存图分析框架。GraphGrind中的评估表明，这优于用于共享内存的最先进的图形分析框架，包括高达10.4倍的Ligra（Shun和Blelloch，2013）和Polymer（Zhang等人，2015）在8种算法和6种图形上高达8.3倍。
This paper investigates the performance of graph-structured analytics on large-scale shared memory systems. Graph analytics are highly demanding for efficient graph traversal due to large data set size and irregular data access patterns. In order to achieve efficient graph analytics, we consider and discuss the performance of three common types of graph data structures. Also, we demonstrate that load balance is to a large extent determined by the number of edges and number of unique vertices processed by each thread. Finally, we propose an automatic graph data structure selection algorithm and an efficient reordering as a pre-processing step to balance the number of vertices and edges together. Reordering algorithm also optimally balances edges and vertices for graphs with a power-law degree distribution and ensures an equal degree distribution across threads. The developed techniques are implemented in GraphGrind, a new shared memory graph analytics framework. Evaluation in GraphGrind, shows that this outperforms state-of-the-art graph analytics frameworks for shared memory including Ligra (Shun and Blelloch, 2013) up to 10.4×, and Polymer (Zhang et al., 2015) up to 8.3× across 8 algorithms and 6 graphs.