A Breadth-First Search Algorithm Accelerator Based on CSCI Graph Data Format

Breadth first search (BFS) algorithm is a building block of many graph applications; The sparsity of graph data and power-law distribution restrict the performance improvement of graph applications. In order to improve the access efficiency of data in graph computing accelerator, a variety of graph data formats have been proposed successively. However, the current scheme is complex, and the compressed data often needs to be decompressed to perform subsequent processing. In order to solve this problem, starting with the graph data organization format, this paper proposes a new data compression format compressed sparse columns independently(CSCI), and designs a BFS accelerator based on CSCI to improve the performance of graph computing accelerator and weaken the influence of sparsity. In this paper, the proposed accelerator circuit is tested on a prototype system based on XCVU9P-L2FLGA2104 using SNAP datasets. The experimental results show that the proposed BFS accelerator can reduce the resource utilization rate of LUT, FF and BRAM by 55%, 98%, 98.2% at most. At the same time, compared with the classical GraphBIG and Gemini graph framework, the running time of BFS accelerator is reduced by 61% and 64%, and the power is reduced by 34% compared with GraphBIG.