Implementing Push-Pull Efficiently in GraphBLAS
Implementing Push-Pull Efficiently in GraphBLAS
复制标题
DOI：
10.1145/3225058.3225122
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Carl Yang;A. Buluç;John Douglas Owens
中科院分区：
文献类型：
--
作者：
Carl Yang;A. Buluç;John Douglas Owens
我们将波束算法的推拉算法，也称为方向优化的广度优先搜索算法(DOBFS)分解为3种可分离的优化算法，并分析了它们的泛化能力、渐近加速比和对整体加速比的贡献。我们证明了掩蔽对于高性能是至关重要的，并且可以推广到输出的稀疏模式是先验已知的所有图算法。我们证明了这些图算法优化，它们共同构成了DOBF，可以用线性代数来简洁地、可分离地描述，并且可以用基于图的线性代数的框架来表示。我们提供的实验证据表明，通过这些优化，用基于线性代数的图框架表示的DOBFS在GPU和多线程CPU上获得了与最先进的图框架相当的性能，在22rmat的比例图上获得了101 GTEPS。
We factor Beamer's push-pull, also known as direction-optimized breadth-first-search (DOBFS) into 3 separable optimizations, and analyze them for generalizability, asymptotic speedup, and contribution to overall speedup. We demonstrate that masking is critical for high performance and can be generalized to all graph algorithms where the sparsity pattern of the output is known a priori. We show that these graph algorithm optimizations, which together constitute DOBFS, can be neatly and separably described using linear algebra and can be expressed in the GraphBLAS linear-algebra-based framework. We provide experimental evidence that with these optimizations, a DOBFS expressed in a linear-algebra-based graph framework attains competitive performance with state-of-the-art graph frameworks on the GPU and on a multi-threaded CPU, achieving 101 GTEPS on a Scale 22 RMAT graph.