Generalized sparse linear algebra library with vendor-agnostic GPUs acceleration

Introduction 5
1. Problem statement 7
2. Background of study 8
2.1. Related Work 8
2.2. GraphBLAS concepts 11
2.3. GraphBLAS limitations 14
2.4. GPU computations 16
2.5. GPU architecture 18
2.6. OpenCL concepts 20
2.7. Implementation challenges on GPUs 22
3. Proposed solution description 24
3.1. Design Principles 24
3.2. Architecture overview 25
3.3. Data Containers 26
3.4. Algebraic Operations 27
3.5. Differences with GraphBLAS standard 29
4. Implementation details 31
4.1. Project structure 31
4.2. Compile-time dependencies 32
4.3. Development automation 33
4.4. Library interface 35
4.5. Algorithms registry 38
4.6. Storage formats 41
4.7. OpenCL backend 43
4.8. Linear Algebra Operations 44
4.9. Graph Algorithms 45
4.10. Running example 46
5. Evaluation 48
5.1. Research questions 48
5.2. Evaluation setup 48
5.3. Methodology 49
5.4. Graph algorithms 49
5.5. Dataset 50
5.6. Results Summary 51
6. Results 59
References 62
Купить

Graph model is a natural way to structure data in a number of a real practical tasks, such as graph queries, graph databases, social net­works analysis, RDF data analysis, bioinformatics and static code analysis. In the graph model the entity is represented as a graph vertex. Relations between entities are directed labeled edge. This notation allows one to model the domain of the analysis with a little effort, preserv­ing complex relationships between objects. What is not easy and clear to do, for example, in a classic relational model, based on tables.
Practical real-world graph data tends to be sparse and counts dozens of millions of vertices and billions of edges. Thus, scalable high- performance graph analysis is demanding area and an actual challenge for a research. There is a big number of ways to attack this challenge and the first promising idea is to utilize general-purpose graphic processing units. Such existing solutions, as CuSha and Gunrock show that utiliza­tion of GPUs can improve the performance of graph analysis, moreover it is shown that solutions may be scaled to multi-GPU systems. However, low flexibility and high complexity of API are problems of these solutions.
The second promising thing which provides a user-friendly API for high- performance graph analysis algorithms creation is a GraphBLAS API, which provides linear algebra based building blocks to create graph analy­sis algorithms. The idea of GraphBLAS is based on a well-known fact that linear algebra operations can be efficiently implemented on parallel hard­ware. Along with that, a graph can be natively represented using matrices: adjacency matrix, incidence matrix, etc. While reference CPU-based imple­mentation of GraphBLAS, SuiteSparse, demonstrates good performance in real-world tasks, GPU-based implementation is challenging.
One of the challenges in this way is that real data are often sparse, thus underlying matrices and vectors are also sparse, and, as a result, classical data structures and respective algorithms are inefficient. So, it is necessary to use advanced data structures and procedures to implement sparse linear algebra, but the efficient implementation of them on GPUs is hard due to the irregularity of workload and data access patterns. Though such well- known libraries as cuSPARSE, clSPARSE, bhSPARSE, Cusp show that sparse linear algebra operations can be efficiently implemented for GPUs, it is not so trivial to implement GraphBLAS on GPU. First of all, it requires generalized sparse linear algebra, thus it is impossible just to reuse existing libraries which are almost all specified for operations over floats with classical element-wise functions. The second problem is specific optimizations, such as masking fusion, which can not be natively implemented on top of existing kernels. Nevertheless, there is a number of implementations of GraphBLAS on GPU, such as GraphBLAST, GBTL, which show that GPUs utilization can improve the performance of GraphBLAS-based graph analysis solutions. But these solutions are not portable across different device vendors because they are based on Nvidia Cuda stack.
Although GraphBLAS is solid and mature standard with a number of implementation, it has limitations and shortcomings discussed in a talk given by John R. Gilbert. Some of them are lack of interoperability and introspection, what is an obstacle on the way of GraphBLAS integra­tion into real-world data analysis pipelines. Implicit zeroes mechanism and masking, which uses mix of engineering and math, leads to unpredictable memory usage in some cases, keeping API complex for both implementation and usage.
Summarizing, there is still no portable and high-performance library, which provides generalized linear-algebra based building blocks for real- world large sparse graph analysis problems. Such a library can potentially solve a number of problems, such as complex user API for particular graph algorithms implementation, GPUs performance and portability issues. Al­though GraphBLAS standard is a good reference point for implementation, it is still possible to design a bit different API. The solution can solve some of technical GraphBLAS limitations while still being coherent with the standard for further co-operation.
Купить