【作者】 金鑫；

【导师】 林学民；

【作者基本信息】 华东师范大学 ， 软件工程， 2021， 硕士

【摘要】 图可以用来描绘事物之间的复杂关系,被广泛应用于生物、化学、电商和社交网络等领域。随着领域发展与图的大量积累,人们在图的管理与分析,尤其是子图匹配问题上,进行了越来越多的研究,子图匹配有非常广泛的应用,例如OLAP场景中生物学蛋白质交互网络的分析与比较;OLTP场景中风控管理对风险交易的实时预警等。子图匹配问题是指给定一个查询图与数据图,找出数据图中所有查询图的同构子图。近年来,随着图数据的规模日益增大,单核串行算法已经无法高效地处理大规模图数据,并且现有的子图匹配算法多是在单核环境下开发和设计的,无法充分利用日益提高的硬件性能(多核CPU;新硬件如FPGA等)来提高可扩展性。同时,近年来学术界与工业界对现场可编程门阵列(FPGA)的兴趣愈来愈浓。各大云计算厂商例如AWS、Azure和阿里云等,都纷纷在其云计算平台推出FPGA服务。学术界内,对利用FPGA加速图算法的研究也逐年增多。基于此,本文研究并实现了基于FPGA的多核并发子图匹配算法。算法能够充分利用单机上的硬件资源,例如多核CPU、多块FPGA加速卡等。这也是目前世界上第一个利用FPGA对子图匹配问题进行加速的算法。算法首先设计了全新的辅助数据结构CST作为子图匹配的完备搜索空间。CST能够极大的对原图进行剪枝过滤,大大减小了子图匹配的搜索空间。其次本文设计了CST的划分方法,来实现搜索空间的并发分配,同时拆分后的CST能够完全存储到FPGA的片上存储BRAM中,避免了FPGA在加速子图匹配的过程中,数据在片上存储BRAM与片外存储DRAM之间的频繁传输。本文还设计了基于CST的工作量估算算法,用以解决负载不均衡的问题。在FPGA上,本文将传统的子图匹配算法串行过程,转换为多模块并行的模式,充分利用FPGA数据加速与流水线加速的特性,对子图匹配进行加速。基于工业界基准LDBC的大规模图上实验证实了本文实现的单机环境下基于FPGA的多核并发子图匹配算法,在性能上比当前最快的CPU算法CFL,DAF和CECI以及GPU算法GSI和Gp SM有极大的提升。同时本文提出的算法也是实验中唯一一个能够在10亿条边的大图上,成功进行子图匹配计算的算法。更多还原

【Abstract】 Graphs can be used to describe complex relationships between things and are widely used in biology,chemistry,social networks and so on.With the development of the fields and the accumulation of data,people have conducted more and more re-searches on the management and analysis of graphs,especially the subgraph matching problem.Subgraph matching has a very wide range of applications,such as analysis and comparison of protein interaction networks in OLAP scenarios? real-time fraud detec-tion in OLTP scenarios,etc.Given a query graph q and a data graph G,subgraph match-ing is to find out all the isomorphic subgraphs of q in G.In recent years,as the scale of graph data increase rapidly,serial algorithms can hardly process large-scale graph data efficiently.And the existing works are mostly developed and designed in a stand-alone environment,which cannot utilize the ever-developing hardware(e.g.multi-CPUs,FP-GAs,etc.)to improve their scalability.At the same time,people in the academia and industry have gain their interest in field programmable gate arrays(FPGAs).Major cloud computing vendors such as AWS,Azure,and Alibaba Cloud have all launched FPGA services on their cloud computing platforms.In academia,research on the use of FPGA to accelerate graph algorithms has also increased year by year.So we study and implement an FPGA-based multi-core subgraph matching algo-rithm,called FAST.FAST makes full use of hardware resources on a single machine,such as multi-CPUs,multiple FPGA accelerator cards,etc.This is also the world’s first algorithm that uses FPGAs to accelerate the subgraph matching problem.In FAST,we first design a new auxiliary data structure called candidate search tree(CST)as a com-plete search space for subgraph matching.CST can greatly prune and filter the search space for the subgraph matching.Secondly,we designed the partition mechanism of CST to realize the concurrent allocation of the search space.At the same time,the par-titioned CST can be completely stored in the FPGA’s on-chip memory BRAM,avoiding the costly data transformation between on-chip memory BRAM and off-chip memory DRAM.We also design a workload estimation method of CST to solve the problem of load imbalance.On the kernel side(i.e.FPGA),we split the traditional serial process of subgraph matching into a multi-module parallel mode.We make full use of the data acceleration and pipeline acceleration property of FPGAs to accelerate the subgraph matching.Through large-scale graph experiments based on the industry benchmark LDBC,we confirm that FAST significantly outperforms the state-of-the-art CPU-based algo-rithms(e.g.CFL,DAF and CECI)and GPU-based algorithms(e.g.GSI and Gp SM).FAST is also the only algorithm that can successfully perform subgraph matching on a billion-scale graph.更多还原