FPGA-based acceleration for graph data mining

Abstract

The quick development of Graph-based Data Mining (GDM) techniques has incubated an increasing demand of highly efficient hardware blocks served for this purpose. Among this field, the computation-costing Graph-Similarity (GS) algorithm possess a crucial position, as it could find similarity scores for nodes of two graphs and indicate implicit patterns. In this project, a FPGA-based acceleration engine for GS algorithm is designed and implemented, taking advantage of the hardware resources provided. Available parallelism is explored and implemented, and performance evaluation is conducted. This GS algorithm designed is first implemented in C language and then in Verilog HDL. (1) In the C program, single-threaded programming technique is adopted, involving advanced graph-based searching and manipulation algorithms. (2) On the contrary, multi-threaded parallel programming technique is adopted in the Verilog HDL program, involving fixed-point arithmetic and finite-state-machine (FSM) implementation. (3) The performance is evaluated by applying GS testing datasets, the operation time required as well as the throughputs are measured. Further improvements are also explored and suggested. Finally, the testing results indicate that the hardware implementation on FPGA possess a performance much better than software implementation, which is around hundred times faster, and this observation matches with my estimations greatly. In summary, hardware implementation of GDM has its advantage of multi-threading and thus better performance than normal programming techniques.