Scalable Triangle Counting on Distributed-Memory Systems
Scalable Triangle Counting on Distributed-Memory Systems
复制标题
分布式内存系统上的可扩展三角形计数
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ümit V. Çatalyürek
中科院分区：
文献类型：
--
作者：
Seher Acer;Abdurrahman Yasar;S. Rajamanickam;Michael M. Wolf;Ümit V. Çatalyürek
三角计数是网络科学中一个基本的图分析核心。这也是“静态图形挑战赛”的挑战问题之一。在这项工作中，我们提出了一种基于线性代数公式的新型混合并行三角形计数算法。我们的框架分别使用MPI和Cilk来利用分布式内存和共享内存并行性的优势。该问题在MPI进程之间使用二维（2D）笛卡尔块分区进行分区。使用Cilk编程模型，在笛卡尔块中使用一维（1D）逐行分区来实现共享内存并行性。除了在几乎所有测试图中表现出非常好的强缩放行为外，我们的算法在1.4B边缘真实twitter图上实现了最快的时间，在1,092个内核上达到3.217秒。与过去图表挑战的分布式内存并行获胜者相比，我们在这个twitter图表上展示了2.7倍的速度提升。当twitter图没有被复制时，这也是在twitter图上进行平行三角形计数的最快时间。
Triangle counting is a foundational graph-analysis kernel in network science. It has also been one of the challenge problems for the “Static Graph Challenge”. In this work, we propose a novel, hybrid, parallel triangle counting algorithm based on its linear algebra formulation. Our framework uses MPI and Cilk to exploit the benefits of distributed-memory and shared-memory parallelism, respectively. The problem is partitioned among MPI processes using a two-dimensional (2D) Cartesian block partitioning. One-dimensional (1D) rowwise partitioning is used within the Cartesian blocks for shared-memory parallelism using the Cilk programming model. Besides exhibiting very good strong scaling behavior in almost all tested graphs, our algorithm achieves the fastest time on the 1.4B edge real-world twitter graph, which is 3.217 seconds, on 1,092 cores. In comparison to past distributed-memory parallel winners of the graph challenge, we demonstrate a speed up of 2.7× on this twitter graph. This is also the fastest time reported for parallel triangle counting on the twitter graph when the graph is not replicated.