Тема: Generalized sparse linear algebra library with vendor-agnostic GPUs acceleration

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.
Купить

The following results were achieved in this work.
• The survey of the field was conducted. Model for a graph analy­sis were shown. Also, the concept of the linear algebra based approach was described in a great detail with a respect to a graph traversal and existing solutions. Introduction into a GraphBLAS standard was pro­vided. Existing implementations, frameworks and most significant contributions for a graph analytic were studied. Their limitations were highlighted. General-purpose GPU computations concept was covered. Different APIs for GPU programming were presented. Their advantages and disadvantages were covered. General GPU program­ming challenges and pitfalls were highlighted.
• The architecture of the library for a generalized sparse linear algebra for GPU computations was developed. The architec­ture and library design was based on a project requirements, as well as on a limitation and experience of the existing solutions. The dif­ferences with GraphBLAS standard were stated.
• The library was implemented accordingly to the developed architecture. The core of the library, interface, data containers, built-in scalar data types, built-in element-wise functions, expressions processing, OpenCL backend functionality, common linear algebra operations implementations were covered. Several graph algorithms for a graph analysis were implemented using developed library API.
• The preliminary experimental study of the proposed arti­facts was conducted. Obtained results allowed to conclude, that the chosen method of the library development is a promising way to a high-performance graph analysis in terms of the linear algebra on a wide family of GPU devices. The proposed solution showed compara­ble performance to the GraphBLAST, reaching up to x36 speedup in some cases, and showed constantly better performance, than SuiteS- parse, reaching up to x20 speedup in some cases. The developed library showed a scalability on different device vendors GPUs. Also, the proposed solutions got an acceptable performance on integrated GPUs in some cases even if compared with highly-optimized multi­core CPU frameworks.
All in all, there are still a plenty of research questions and directions for improvement. Some of them are listed bellow.
• Performance tuning. There is a still space for optimizations. Bet­ter workload balancing must be done. Performance must be improved on AMD and Intel devices. More optimized algorithms must be imple­mented, such as SpGEMM algorithm proposed by Nagasaka et al. [21] for general mxm operation.
• Operations. Additional linear algebra operations must be imple­mented as well as useful subroutines for filtering, joining, loading, saving data, and other manipulations involved in typical graphs anal­ysis.
• Graph streaming. The next important direction of the study is streaming of data from CPU to GPU for out-of-memory graphs anal­ysis. CuSha adopt data partitioning techniques for graphs processing which do not fit single GPU. Modern GPUs have a limited VRAM. Even high-end devices allow only a moderate portion of the memory to be addressed by the kernel at the same time. Thus, manual streaming of the data from CPU to GPU is required in order to support analysis of extremely large graphs, which count billions of edges to process.
• Multi-GPU. Finally, scaling of the library to multiple GPUs must be implemented. Gunrock shows, that such approach can increase overall throughput and speedup processing of really dense graph. In connection with a streaming, it can be an ultimate solution for a large real-world graphs analysis.
Купить