Research On FPGA-based Graph Processing With Hybrid Push-Pull Computational Model

With the advent arrival of the Big Data era and the rapid development of artificial intelligence,efficient graph processing is very necessary and it is applied to various fields such as social networks and machine learning.Field-programmable gate arrays(FPGA)are advantageous in low power and feature customization,which can realize high parallel processing with perfect energy efficiency.Therefore,generating a FPGA-based graph processing system is very significant.The systems for specific graph algorithms largely depend on the characteristics of the algorithms.The existing general graph processing systems adopt unified framework for the whole procedure of graph processing without fully considering the huge differences of the computational complexity in graph iterations.Besides,they regard FPGA as general processors such as CPU or GPU to design graph engines.Therefore,it is difficult to efficiently complete graph processing and take full advantage of the parallel performance of FPGA.In this paper,we present a FPGA-based graph processing system with efficient hybrid push-pull computational model(FGPH).FGPH applies two computational models to implement push and pull styles for graph iterations with different computational complexity,achieves the full parallel processing for on-chip computational units,and eliminates the workload among different stages of graph iterations.FGPH predicts the computational model of subsequent iterations through the run-time characteristic of the state of data cells in graph processing,and switch models into appropriate one without interrupting execution.FGPH adopts two class of data cells for different models to realize efficient memory access,which achieves much better performance in two models.Furthermore,when a large amount of data is in processing,FGPH balances workload through that multiple computational pipelines generated by custom design on FPGA process different scale of data cells parallel to enhance performance.The experimental results show that compared to state-of-the-art FPGA-based graph systems such as GraphOps and ForeGraph,FGPH gains 2.05 ~ 3.69 times speedups.