Parallel Minimum Spanning Forest Computation using Sparse Matrix Kernels
Parallel Minimum Spanning Forest Computation using Sparse Matrix Kernels
复制标题
DOI：
10.1137/1.9781611977141.7
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
Tim Baer;Raghavendra Kanakagiri;Edgar Solomonik
中科院分区：
文献类型：
--
作者：
Tim Baer;Raghavendra Kanakagiri;Edgar Solomonik
使用稀疏线性代数的图算法公式已经产生了针对连通性和最短路径计算等问题的高度可扩展的分布式算法。我们使用线性代数原语开发了 Awerbuch-Shiloach 并行最小生成森林 (MSF) 算法的第一个公式。我们引入了一个对邻接矩阵和两个向量进行操作的多线性内核。该内核通过同时使用相邻边和顶点的信息来更新图顶点。此外，我们还探索了加速 Awerbuch-Shiloach 算法中快捷步骤的优化。我们使用 Cyclops 来实现这个 MSF 算法，Cyclops 是一个用于广义稀疏张量代数的分布式内存库。我们分析了 Stampede2 超级计算机上实施的并行可扩展性。
Formulations of graph algorithms using sparse linear algebra have yielded highly scalable distributed algorithms for problems such as connectivity and shortest path computation. We develop the first formulation of the Awerbuch-Shiloach parallel minimum spanning forest (MSF) algorithm using linear algebra primitives. We introduce a multilinear kernel that operates on an adjacency matrix and two vectors. This kernel updates graph vertices by simultaneously using information from both adjacent edges and vertices. In addition, we explore optimizations to accelerate the shortcutting step in the Awerbuch-Shiloach algorithm. We implement this MSF algorithm with Cyclops, a distributed-memory library for generalized sparse tensor algebra. We analyze the parallel scalability of our implementation on the Stampede2 supercomputer.