GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU
GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU
复制标题
DOI：
10.1145/3466795
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
Carl Yang;A. Buluç;John Douglas Owens
中科院分区：
文献类型：
--
作者：
Carl Yang;A. Buluç;John Douglas Owens
图算法的高性能实现在新的并行硬件(如GPU)上实现是具有挑战性的，因为有三个挑战：(1)提出图构建块的难度，(2)并行硬件上的负载不平衡，(3)低运算强度的图问题。为了解决其中的一些挑战，GraphBLAS是图分析社区正在进行的一项创新工作，它提出了基于稀疏线性代数的构建块，允许以高效、简洁、可组合和可移植的方式表示图算法。在本文中，我们研究了基于线性代数的方法来构建图形框架的性能挑战，并描述了克服这些瓶颈的新的设计原则。新的设计原则之一是利用输入稀疏性，允许用户编写图形算法，而无需指定推拉方向。利用输出稀疏性，用户可以告诉后端他们不希望在单个矢量化计算中计算输出的哪些值。负载平衡是在并行工作者之间平衡工作的一个重要特性。我们描述了用于处理具有不同特征的图的重要负载平衡功能。本文描述的设计原则已经在NVIDIA图形处理器上第一个高性能的基于线性代数的开源图形框架“GraphBLAST”中得到了实现。结果表明，在单GPU上，GraphBLAST的平均加速比以前的GraphBLAS实现SuiteSparse和GBTL至少有一个数量级，性能与最快的GPU硬连线基元和共享内存图形框架LIGRA和GunRock相当，性能优于任何其他GPU图形框架，同时提供了更简单、更简洁的编程模型。
High-performance implementations of graph algorithms are challenging to implement on new parallel hardware such as GPUs because of three challenges: (1) the difficulty of coming up with graph building blocks, (2) load imbalance on parallel hardware, and (3) graph problems having low arithmetic intensity. To address some of these challenges, GraphBLAS is an innovative, on-going effort by the graph analytics community to propose building blocks based on sparse linear algebra, which allow graph algorithms to be expressed in a performant, succinct, composable, and portable manner. In this paper, we examine the performance challenges of a linear-algebra-based approach to building graph frameworks and describe new design principles for overcoming these bottlenecks. Among the new design principles is exploiting input sparsity, which allows users to write graph algorithms without specifying push and pull direction. Exploiting output sparsity allows users to tell the backend which values of the output in a single vectorized computation they do not want computed. Load-balancing is an important feature for balancing work amongst parallel workers. We describe the important load-balancing features for handling graphs with different characteristics. The design principles described in this paper have been implemented in “GraphBLAST”, the first high-performance linear algebra-based graph framework on NVIDIA GPUs that is open-source. The results show that on a single GPU, GraphBLAST has on average at least an order of magnitude speedup over previous GraphBLAS implementations SuiteSparse and GBTL, comparable performance to the fastest GPU hardwired primitives and shared-memory graph frameworks Ligra and Gunrock, and better performance than any other GPU graph framework, while offering a simpler and more concise programming model.