FPGA-based graph data processing method and system

Abstract

The invention relates to an FPGA-based graph data processing method and system. The method is used for carrying out graph traversal on a graph with small world network characteristics. The method comprises the following steps: obtaining a sample; carrying out graph traversal by using the first processor and a second processor in communication connection with the first processor, the first processor is a CPU, The second processor is an FPGA, The first processor is used for transmitting graph data needing to be traversed to the second processor. the first processor obtains result data of the graph traversal for result output after the second processor completes the graph traversal of the graph data according to a layer sequence traversal mode; the second processor comprises a low peak processing module and a high peak processing module; wherein the low-peak processing module and the high-peak processing module respectively utilize on-chip logic resources of different areas of the secondprocessor, the high-peak processing module has higher parallelism relative to the low-peak processing module, the low-peak processing module is used for carrying out graph traversal in a starting stage and / or an ending stage, and the high-peak processing module is used for carrying out graph traversal in an intermediate stage.

Description

technical field [0001] The invention relates to the technical field of FPGA graph computing, in particular to an FPGA-based graph data processing method and system. Background technique [0002] Graph is a classic data structure that widely exists in real life, such as social networks, road networks, etc. By processing and analyzing graphs, a lot of practical information can be obtained. Graph traversal algorithm is one of the most classic algorithms in the field of graph computing. Many functions are related to graph traversal. Graph traversal algorithms include BFS, DFS, SSSP, etc. [0003] The world is composed of various networks, and the graph data structure is a mathematical representation of the network. At the end of the 20th century, through the study of natural, social and technical networks, it was found that most of these networks have the following characteristics: high clustering, unbalanced degree distribution and central node structure. The small world netw...

AI Technical Summary

Problems solved by technology

It can be seen that if it is necessary to achieve parallelization with a low degree of parallelism, CPU is better than FPGA, and if it is necessary to achieve parallelization with high degree of parallelism, FPGA is better than CPU. Therefore, in the design of CPU-FPGA heterogeneous graph computing systems, generally The start / end stage is placed on the CPU for execution, and the high-parallel intermediate stage is placed on the FPGA to execute, but this heterogeneous CPU-FPGA graph computing architecture has the following disadvantages: (1) When the CPU and FPGA perform conversion It is necessary to stop the program execution of the current processor, save the current running state and processing data, and then transfer the data to the processor to be converted to through the PCIe channel, and then rebuild the execution state. This process takes a lot of time, accounting for almost all (2) When the CPU transfers the program execution to the FPGA, the work of the CPU needs to be stopped, and when the FPGA transfers the program execution to the CPU, the work of the FPGA needs to be stopped, which is a frequent Compared with executing the entire traversal program on a processor, it is very cumbersome and complicated

[0009] The FPGA-based graph architecture implementation mode is to execute the entire graph computing process on the same FPGA design architecture. Compared with the graph computing architecture based on CPU-FPGA heterogeneous design, it saves the consumption of data transmission and state reconstruction between CPU and FPGA. , but this architecture has the following disadvantages: (1) The architecture design is not combined with the obvious execution characteristics of different stages of graph computing, so that the characteristics of processors and graph algorithms cannot be fully utilized to achieve the purpose of optimizing graph computing; (2) In order to meet the large number of threads required by graph computing, the graph computing functional module has a large number of parallel units. Due to the load balancing problem of the execution part of graph computing with low parallelism in a large number of parallel units, the problem of long tail effect of graph computing occurs, etc.

Images