Improving Efficiency of Parallel Vertex-Centric Algorithms for Irregular Graphs
Improving Efficiency of Parallel Vertex-Centric Algorithms for Irregular Graphs
复制标题
DOI：
10.1109/tpds.2019.2906166
复制
发表时间：
2019-10
影响因子：
5.3
通讯作者：
Muhammet Mustafa Ozdal
中科院分区：
文献类型：
--
作者：
Muhammet Mustafa Ozdal
内存访问是共享内存并行图应用程序的主要瓶颈，特别是对于大型和不规则的图形。传播阻塞（PB）思想是近年来提出的一种提高PageRank、稀疏矩阵和向量乘运算并行性能的方法。这个想法是基于将并行计算分为两个阶段，合并和积累，这样随机存储器访问被连续访问取代。在本文中，我们提出了一个算法，允许这两个阶段同时执行。我们提出了几个改进，以增加并行吞吐量，减少内存开销，提高工作效率。我们的实验结果表明，我们提出的算法提高了共享内存并行吞吐量的一个因素高达2倍相比，原来的PB算法。我们还表明，内存开销可以显着降低（从170%下降到不到5%），而不会显着降低性能。最后，我们证明了我们的并发执行模型允许异步并行执行，导致显着的工作效率，除了吞吐量的提高。
Memory access is known to be the main bottleneck for shared-memory parallel graph applications especially for large and irregular graphs. Propagation blocking (PB) idea was proposed recently to improve the parallel performance of PageRank and sparse matrix and vector multiplication operations. The idea is based on separating parallel computation into two phases, binning and accumulation, such that random memory accesses are replaced with contiguous accesses. In this paper, we propose an algorithm that allows execution of these two phases concurrently. We propose several improvements to increase parallel throughput, reduce memory overhead, and improve work efficiency. Our experimental results show that our proposed algorithms improve shared-memory parallel throughput by a factor of up to 2x compared to the original PB algorithms. We also show that the memory overhead can be reduced significantly (from 170 percent down to less than 5 percent) without significant degradation of performance. Finally, we demonstrate that our concurrent execution model allows asynchronous parallel execution, leading to significant work efficiency in addition to throughput improvements.