The Research And Implementation Of A High Performance Graph Computing Architecture Fabgraph Based On FPGA

Graph is a complex data structure composed of vertices and edges and containing a variety of information.Graph Computing is a general term for a class of calculations that find a certain relationship in graph data.Graph computing abstracts the relationship attributes in real conditions into graph data structures and performs complex calculations.How to perform high-performance calculations on extremely large graph data sets is a key problem that graph computing needs to solve.As a parallelized computationally intensive acceleration hardware,the Field-Programmable Gate Array(FPGA),compared with the GPU and GPU-based graph computing architecture,has excellent performance-to-power ratio and unique advantages,so FPGA applications which are applied in the calculation of graphs and the acceleration of graph calculations have great potential.Research on graph computing based on FPGA has been carried out for many years,and many excellent algorithms have appeared during the period.ForeGraph is one of the outstanding algorithms recently proposed.The core architecture of the ForeGraph algorithm is based on the GridGraph graph partitioning method and FPGA hardware acceleration.It makes full use of the ability of the Random Random Access Momery(BRAM)to efficiently access random memory,and implements a simple graph computing architecture based on multiple FPGA development boards and the ring structure.However,when implementing ForeGraph on a single FPGA development board,there are deficiencies in data preprocessing,data scheduling strategies,BRAM,and data storage structures.Aiming at the above problems in ForeGraph implementation on a single FPGA development board,FabGraph is designed for high performance single FPGA development board diagram calculation.Although FabGraph is still based on traditional external storage devices,pipeline and edge flow to implement graph computing,through cache structure and Hilbert scheduling algorithm based on Window sliding,PK(Processor Kernel)aggregation and interleaving,solve the core problems of ForeGraph data expansion and data locality that cannot? be utilized.FabGraph is implemented on a single FPGA development board,and its performance is improved and optimized in the implementation process through performance analysis.For example,URAM(Ultra Random Access Momery),which uses a new FPGA in addition to BRAM,Hilbert scheduling algorithm,secondary Cache architecture,PK aggregation and its interleaving operation,high bandwidth transmission between BRAM,virtual pipeline,etc.FabGraph was simulated and tested using the existing graph dataset.During the simulation test,the memory(DRAM)bandwidth was simulated by DRAMSim2,and the computational efficiency was realized by Vivado simulation.The comparison test found that the performance of FabGraph was 1-3 times higher than that of ForeGraph in most of the test sets under the same conditions,which proved that FabGraph achieved the research goal.