Research On Graph Partitioning And Scheduling Method For The Multi-FPGA Computing Platform

It is of great significance to improve the efficiency of large-scale graph processing to solve many practical problems.Field Programmable Gate Array(FPGA)is widely used in accelerating graph processing system because of its programmable features.The real-world data size is too big to be effectively stored and processed on a single FPGA board.Therefore,the adoption of multi-FPGA architecture is an important technical approach to solve the above problems.The raw graph data is divided into several subgraphs and placed into different FPGAs to be processed respectively.Due to the limitation of the communication bandwidth between FPGA boards,the frequent synchronization interaction among different subgraphs can be restricted.It leads to decing performance in the current multi-FPGA graph processing systems.In order to improve the overall processing performance of graph processing system,multi-FPGA graph processing system Efiraph is proposed.By measuring the relationship between communication and local computation,the communication overhead between FPGA is effectively reduced.Specifically,Efiraph proposes an effective graph partitioning algorithm based on communication bandwidth and local computing speed at preprocessing stage.Meanwhile,Efiraph adopts the work stealing method to improve the local computing efficiency,that can improve the performance of the overall graph processing system.Efiraph also optimizes the memory access of the graph processing system,which can connect the relationship between the graph partitioning and the subgraph processing,achieving the overall performance improvement of the graph processing system.The experimental results show that compared with typical FPGA graph processing systems in the world,Efiraph can improve the overall performance by 2.56 times,and the system cost is lower.Meanwhile,under the condition of limited communication bandwidth,Efiraph has better system scalability.