Research Of High Performance Generalized Graph Analytics Framework On The GPU

Graphs are ubiquitous data structures which can represent relationships between human beings,computers,biological and genetic interactions,and elements in unstructured meshes.Many practical problems and applications,such as bioinformatics,social network analysis,traffic engineering,can be modeled in their essential form by graphs and solved with appropriate graph primitives.In recent years,the rapidly growing use of graphs has sparked parallel graph analytics frameworks for leveraging the massive hardware resources,specifically graphics processing units(GPUs).However,the issues of the unpredictable control flows,memory access,and the complexity of programming have restricted high-level GPU graph libraries.In this work,we present HPGraph,a high performance generalized graph analytics framework targeting the GPU.HPGraph designed and implemented a model that maps vertex-centric programming to the backend of the sparse matrix operations on the GPU.HPGraph incorporates a BSP model and uses a generalized sparse matrix vector multiplication to implement graph traversal in each iteration until the algorithm converges.We present the specific implementation flow of HPGraph in the article.Meanwhile,HPGraph integrates a range of performance optimization strategies in matrix storage format,memory access and algorithm-specific.These optimization methods have greatly improved the performance of the framework.HPGraph strikes a balance between performance and productivity by using a high-level programming model and providing users with simple APIs,which enables users to implement a variety of graph algorithms with relatively little effort.In this paper,we implemented four graph algorithms: BFS,SSSP,PageRank,and TC,and evaluated the performance of HPGraph on large-scale datasets.The experimental results show that HPGraph matches or even exceeds the performance of MapGraph,Gunrock and nvGRAPH,three state-of-the-art GPU graph libraries.HPGraph also runs significantly faster than advanced CPU graph libraries.