The Research On Acceleration System Of Graph Processing Based On FPGAs

In recent years,the scale of data generated by human life has increased dramati-cally,so it also urges the development and maturity of big data and cloud computing technology.Generally,data can be divided into structured data,semi-structured data and unstructured data.Graph is a typical representative of semi structured data.How to effectively process large-scale graphs has become a hot and difficult research field in the area of academic and industrial.Because of the natural irregularity of graph,the graph processing system based on general processor shows poor computation efficiency and memory efficiency when processing large-scale graphs.Fortunately,customizing hardware accelerator for graph processing is one of the ways to improve the compu-tation efficiency and memory efficiency.At first,our thesis analyzes and evaluates the graph processing systems on single machine,which is based on general purpose processors,analyzes the computation efficiency and memory efficiency,compares the convergence speed of synchronous computation model and asynchronous computation model,and describes the performance model of graph processing accelerator on het-erogeneous platform.Further more,we design an asynchronous and energy-efficient hardware accelerator for graph processing,named Domino,and a scalable hardware accelerator for graph processing,named OmniGraph.Besides,we construct a hetero-geneous system for graph processing,named Jakiro,based on the hardware accelerator.The main contributions and innovations in this work are as follows:(1)This thesis has analyzed and evaluated graph processing systems on a single machine,which is based on general purpose processor.We design the evaluation frame-work in this part and the evaluation refers to performance,data locality,CPU utilization and so on.The conclusion of analysis and evaluation can be a guideline for users when they choose the best system according to the feature of graph applications and the fea-ture of datasets;(2)This thesis analyzes the computation efficiency and memory efficiency of graph processing system based on general processors,and further describes the performance model for graph processing accelerator.Whereafter,we design an asynchronous and energy-efficient hardware accelerator for graph processing,named Domino.Domino adopts naive update mechanism and bisect update mechanism to perform asynchronous control.Experimental results show that Domino achieves 1.47x?7.84x and 0.47x?2.52x average speedup over GraphChi on the Intel Core2 and Core i7 processors,re-spectively.Besides,compared to Intel Core i7 processors,Domino also performs 2.03x?10.08x energy-efficiency;(3)This thesis proposes a scalable hardware accelerator for graph processing,named OmniGraph.OmniGraph is able to adaptively choose the corresponding computation engine to perform graph processing and optimize the data layout on the memory off-chip.Experimental results demonstrate that the MGPE(Medium-scale Graph Process-ing Engine)achieves 1.03x?8.13x average speedup over Intel Core2 Processors;(4)This thesis further constructs heterogeneous graph processing system on CPU-FPGA platform,named Jakiro,and describes the hierarchical architecture of Jakiro.Jakiro achieves a series of application programming interface functions on API layer and shows the StreamEdges-Reduce-Update programming model of this system.The accelerator proposed in this thesis improves the performance and economizes the power consumption of graph processing when compares to the graph processing system on a single machine,GraphChi.Besides,users are able to use the underlying accelerator by invoking the interface functions in Jakiro.