苏勋斌关于用FPGA硬件加速子图同构问题的论文《FASI: FPGA-friendly Subgraph Isomorphism on Massive Graphs》被ICDE 2023接收。

子图同构（又可称为子图匹配）算法是图算法领域的一个重要的课题。由于其问题本身的计算复杂性，随着数据图规模的扩大，如何快速有效地在真实世界的大图上找出所有匹配变得越来越具有挑战性。因此，利用硬件来加速子图匹配算法便越来越受到人们的关注。近些年来，子图匹配算法在GPU上的实现已有了许多的研究工作，但是它们当中的许多能处理的数据图规模都受限于片上空间的大小。FPGA通过其流水线并行也表现出了潜在的竞争力，然而在FPGA上的子图匹配工作很少。在本文中，我们提出了FASI，一个基于FPGA实现的子图匹配算法。不同于现存的基于边验证（edge-verification）的FPGA上的FAST算法，我们采用基于最坏情况下最优连接的流水线设计方法，它充分利用了FPGA的数据级流水特性和突发读写（burst I/O）优化。具体来说，我们设计了一套对FPGA访问友好的数据结构LPCSR，用于对邻接表的高效访存。其次，我们提出了联合并行流水的策略来加速在FPGA上的匹配过程。最后，我们利用合并访存机制和预分配写回策略两项优化技术进一步提高算法的性能。实验结果表明，在多个大规模的真实图数据集上，FASI都比多个现存的CPU，GPU和FPGA上的子图匹配算法有更好的性能。