Study On Acceleration Of Graph Computation For Heterogeneous Systems

In the era of big data,the scale of graph data has rapidly expanded,and the complexity of graph computation has increased accordingly.With the gradual failure of Moore’s law,generalpurpose computing platforms have become inadequate to meet the real-time demands of graph computation in daily life.Due to the high performance and energy efficiency of heterogeneous platforms,graph computation acceleration on heterogeneous platforms has gradually become a development trend.Hop-constrained Single-Source Simple Path Enumeration(HcPE)problem is one of the important graph computing research problems at present,and PEFP is the only algorithm based on heterogeneous platforms for this problem.As a single-core FPGA-based acceleration algorithm for HcPE,PEFP still has room for optimization in preprocessing and multi-core concurrency.Based on the above background,to study the acceleration problem of graph computation for heterogeneous architecture,this thesis aims to investigate the more advanced FPGA-based accelerator for HcPE.In terms of preprocessing,this thesis proposes the ReBFS algorithm,which reduces the time complexity and the induced subgraph size compared with PEFP.Specifically,this thesis designs a graph-based sorting strategy and a distance-based pruning strategy to optimize the memory access cost and reduce the search space during the query,respectively.Then,this thesis also proposes a CPU-based baseline query algorithm called ReDFS.In terms of the query,this thesis proposes the FPGA-based query algorithm called FSHA based on the framework of PEFP and the ReDFS algorithm.This algorithm designs a pruning-based pipeline optimization strategy to increase the throughput of the pipeline and utilizes additional memory such as UltraRAM to expand the on-chip memory space,thereby reducing the high access overhead of DRAM.In addition,based on multi-core optimization,this thesis proposes the FMHA algorithm to achieve the parallel accelerated query on both CPU and multi-core FPGA.Extensive experiments are conducted on 11 real-world datasets.The experimental results show that FMHA and FSHA have better performance and stability than the state-of-the-art algorithms called PEFP.On a single FPGA,the average speedup of preprocessing time,query time,and total time for the FMHA based on six computing cores compared to PEFP are 2.02,59.94,and 32.01,respectively.