.png){kind=icon}
返回
Parallel algorithms for finding connected components using linear algebra
.png){kind=icon}
OA
AI
DOI：10.1016/j.jpdc.2020.04.009.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Finding connected components is one of the most widely used operations on a graph. Optimal serial algorithms for the problem have been known for half a century, and many competing parallel algorithms have been proposed over the last several decades under various different models of parallel computation. This paper presents a class of parallel connected-component algorithms designed using linear-algebraic primitives. These algorithms are based on a PRAM algorithm by Shiloach and Vishkin and can be designed using standard GraphBLAS operations. We demonstrate two algorithms of this class, one named LACC for Linear Algebraic Connected Components, and the other named FastSV which can be regarded as LACC's simplification. With the support of the highly-scalable Combinatorial BLAS library, LACC and FastSV outperform the previous state-of-the-art algorithm by a factor of up to 12x for small to medium scale graphs. For large graphs with more than 50B edges, LACC and FastSV scale to 4K nodes (262K cores) of a Cray XC40 supercomputer and outperform previous algorithms by a significant margin. This remarkable performance is accomplished by (1) exploiting sparsity that was not present in the original PRAM algorithm formulation, (2) using high-performance primitives of Combinatorial BLAS, and (3) identifying hot spots and optimizing them away by exploiting algorithmic insights. (C) 2020 Elsevier Inc. All rights reserved.
Keyword:
Connected Component
Distributed memory
GraphBLAS
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4
论文数:
3.8K
被引数:
4.8K
机构
引用论文
Role of GABRA2 on risk for alcohol, nicotine, and cannabis dependence in the Iowa Adoption StudiesOAAI
.png){kind=icon}
OAAI分享收藏分享收藏Optimization of (Bi,Pb) 2 Sr 2 Ca 2 Cu 3 O 10 /Ag conductors for practical applications(Bi,Pb)₂Sr₂Ca₂Cu₃O₁₀/Ag导体的优化以用于实际应用
PREAI
分享收藏
查看更多内容