Development Of Random Walk Algorithm Acceleration System Based On FPGA

The Random Walk algorithm based on the Monte Carlo method is one of the very important basic methods in the field of graph computing,and is widely used in tasks such as graph node similarity calculation,web page ranking,image segmentation,and machine learning preprocessing.The independence of random walk path sampling makes it have the advantage of natural high parallelism.At the same time,the random walk process is full of a large number of random accesses,so the memory access overhead is relatively large,which is a memory access-intensive algorithm.However,existing computing platforms such as GPUs,CPUs,etc.,due to their hardware characteristics and memory scheduling mechanisms,are difficult to provide efficient calculations for random walk algorithms.In the field of graph computing,Field Programmable Gate Array(FPGA)is widely used due to its configurability,low power consumption,high parallelism,pipeline and other characteristics,which brings a good acceleration effect in the calculation of irregular graph data.At present,there is no deployment and acceleration of random walk algorithms on FPGA,and there is a lack of corresponding system design.In order to improve the computational efficiency of random walk,this paper proposes a random walk acceleration system based on FPGA.The system is mainly divided into two parts: CPU-side main control system and FPGA random walk accelerator.This article makes full use of the respective advantages of CPU and FPGA,and builds a CPU-FPGA collaborative computing framework with the help of the highbandwidth communication provided by the PCIE interface.In this paper,the random walk calculation and cache unit are deployed on FPGA chips with lower memory access latency,and the data flow optimization methods such as the memory access optimization mechanism based on message fusion,the fine-grained division of storage units,and the pre-sampling random walk strategy are adopted,which improves the efficiency of FPGA on-chip memory access and reduces the amount of off-chip memory access data,thereby improving the computational efficiency of random walks.In order to improve the ease of use of the system,this paper deploys the external interface and control center of the system to the CPU side.The use of the system only needs to input graph data and random walk calculation task information.The experimental results show that,compared to Knight King,a dedicated calculation engine for random walks and the FPGA-based random walk acceleration system designed in this paper can achieve a performance improvement of up to 12 times.Because the system uses FPGA as the computing platform of random walk,it has lower computing power consumption.After evaluation,the power consumption of the FPGA random walk accelerator is only 2.841 W,which is far lower than the computing power consumption of a general-purpose processor.In addition,this article is the first to design a dedicated hardware accelerator for random walks,which can provide a good research idea for the subsequent architecture design of random walks and other graph computing accelerators.