Scalable BFS Algorithm Accelerator Based On FPGA-HBM Platform

In recent years,graph computing has received widespread attention due to its wide applicability in solving practical problems.The breadth-first search algorithm(BFS)is the cornerstone of many graph analysis algorithms,such as the single-start shortest path problem(SSSP)and centrality(BC)algorithm,so it is of great significance to accelerate the BFS algorithm on FPGA.The current BFS computing hardware architecture on FPGA is mainly based on 1?2 channels of DRAM memory,and the computing power is limited by the memory bandwidth,so the hardware characteristics of FPGA's high parallelism cannot be fully used.This scheme,ScalaBFS,is a new type of accelerator,which can expand the BFS performance on FPGA-HBM platform with the increase of memory channels and even the increase of the number of FPGA cards.By taking advantage of the high bandwidth memory(HBM),ScalaBFS can achieve high parallelism,high performance single-card system as well as multi-card system on the U280 accelerated card.The design of high parallelism of ScalaBFS is mainly accomplished by decoupling access logic and computing logic,which are connected by a cross network of vertex scheduler.ScalaBFS can extend to multi-card systems by porting the vertex scheduler's crossover network to the Ethernet.In the single-card experiment,ScalaBFS can scale BFS performance almost linearly with the increase of memory channels.With 32 PE and 64 HBM channels configured,singlecard SCALABFS can achieve the highest BFS performance of 19.7GTEPS on the real graph.Compared with Gunrock,the BFS algorithm on NVIDIA V100 GPU,the performance of Scalab FS in sparse graph is close to that of GPU,but the performance and power consumption ratio is 3-6 times that of GPU.Simulated two-card experiments show that twocard SCALABFS can achieve better scalability and larger graph size with smaller(17%)performance loss and similar resource footprint.