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 are proposed and achieve good results. To provide readers with a comprehensive understanding of graph processing optimizations on multi-core CPU and GPU platforms, we first present the basic concepts, including the graph data structures, the typical graph algorithms, and the characteristics of graph application. Then the challenges of graph processing are clarified. After that, we present the existing graph processing systems based on multi-core CPU and GPU platforms. From the perspective of accelerated graph processing design, we summarize the key technology optimizations in detail and systematically, including pre-processing, memory access optimization, computing acceleration, and overhead reduction of data communication. Finally, we analyze the performance and scalability of state-of-art graph processing and conclude 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.