Survey on Key Technologies of Graph Processing Systems Based on Multi-core CPU and GPU Platforms

As a key technique for analyzing and mining relationships, graph computing has been widely used in smart healthcare, social network analysis, financial anti-fraud, road navigation, computational sciences, and others. In recent years, with the development of parallel structures, memory access methods, interconnection structures, and synchronization mechanisms of general-purpose CPU and GPU architecture, multi-core CPU and GPU have become common platforms for accelerating graph processing. However, there are significant challenges to graph processing in terms of improving performance and achieving high scalability, such as the large scale and irregular distribution of data, complex data dependence, high communication-to-computation ratio, and dynamic changes of vertices and edges. To address the above challenges, a large number of graph processing systems based on multi-core CPU and GPU platforms have been proposed and achieved good results. To provide readers with a comprehensive understanding of graph processing optimizations on multi-core CPU and GPU platforms, this paper first presents the basic concepts, including the graph data structures, the typical graph algorithms, and the characteristics of graph application. Then this article clarifies the challenges of graph processing. After that, this article presents the existing graph processing systems based on multi-core CPU and GPU platforms. From the perspective of accelerated graph processing design, this article summarizes the key technology optimizations in detail and systematically, including pre-processing, memory access optimization, computing acceleration, and overhead reduction of data communication. Finally, this article analyzes the performance and scalability of state-of-art graph processing and concludes the future development trend of graph processing based on different perspectives, which expects to bring certain inspiration to relevant researchers to explore high-performance graph processing system.