Heterogeneous Graph Processing Platform Based On Proportion Of Frontiers

Graph computing is becoming more and more widely used in the modern society,such as social networks,bioinformatics and information networks.However due to the powerlaw characteristics and the complex dependencies of the graph,CPU with traditional Von Neumann architecture cannot perform well.In many previous studies,it is observed that the performance of graph processing is typically limited by the underlying general-purpose processors.Due to the irregularity of the graph and the long latency in memory access,the pipeline slots under the traditional architectures cannot retire normally,resulting in inefficient instruction-level parallelism.At the same time,due to the irregularity of the graph,when dealing with a large number of branches in the graph processing,it is difficult to predict which neighbor to be executed next.The prediction failure will cause the instructions to be rolled back and re-executed,causing a lot of overheads.However,the dataflow architecture can effectively resolve the challenges of low instruction-level parallelism and branch mispredictions in the existing general-purpose architecture for graph applications.By implementing a heterogeneous dataflow architecture in a field programmable logic gate array(Field Programmable Gate Array,FPGA)and a general-purpose processor CPU,a suitable execution model is researched to take advantage of both and get efficiency improved in graph applications.A heterogeneous CPU-FPGA graph computing platform based on the proportion of frontiers.For the problem of inefficient instruction level parallelism and inefficient branch prediction in the graph computing process,we choose different execution models according to the different stages of graph processing judged by change of proportion of frontiers.Specifically,in the early or late stages of the graph computing iteration,because the proportion of frontiers is relatively low,the status of neighbors is better to be predict,and the CPU can play a better role at this time.In the middle stage of graph computing,the proportion of frontiers is high,graph process faces a large number of irregular memory accesses,and the status of neighbors is difficult to predict.Traditional CPU execution models face inefficient instruction-level parallelism and inefficient branch prediction.At this time,using the FPGA-based specific dataflow execution model can avoid the overhead mentioned above.Overall,the heterogeneous CPU-FPGA graph computing scheduling mechanism based on proportion of frontiers includes: 1)a proportion of frontiers detection mechanism based on the source-divided graph,using a heuristic algorithm to determine which stage the subgraph is currently in;2)The scheduling mechanism which applies the Gather-Apply-Scatter(GAS)execution model to solve the difference between the two execution models and improve the synchronization efficiency;3)A data structure which adopts the coordinate storage(Coordinate,COO)storage format of the sparse matrix,and uses the interval-shard graph partition method to store the vertex and edge arrays at the same time,making it compatible with the two execution modes and improving the operating efficiency.The heterogeneous execution model is implemented on a CPU-FPGA platform.Experimental results show that compared with the state-of-the-art CPU-FPGA graph processing accelerator,our method can increase the throughput by 2.2 times.Compared with the state-of-the-art FPGA design,it can increase the throughput by 2.4 times.