基于FPGA的图计算并行算法和体系结构研究

摘要

近年来，随着现场可编程门阵列（FPGA）在计算、存储和逻辑等资源方面的急剧增长，基于FPGA的可重构计算成为高性能计算领域的一个重要分支，越来越凸显其重要的研究和应用价值。图计算是大数据分析领域的一种关键应用，在大数据分析方面具有重要作用，FPGA定制计算在加速图计算方面具有巨大的潜力。然而，现有FPGA图计算存在并行算法设计、并行度开发和支持图计算规模有限等挑战。为应对这些挑战，本文对大规模图计算的FPGA实现技术进行了深入研究，本文的主要工作和创新点如下：
　　（1）提出了面向大规模图最短路径计算的FPGA并行算法和硬件实现结构。针对现有单源路径问题的FPGA实现采用片内存储资源来保存图数据和计算结果，难以高效处理大规模图数据处理的问题，提出了基于Eager Dijkstra算法变种的FPGA并行单源最短路径算法，每次迭代从优先队列移除多个元素进行并行处理，开发了并行性。为了实现大规模优先队列的处理，提出了基于片外存储的大规模优先队列实现方法，利用片外DRAM存储器保存溢出队列元素，并设计合理策略将片外元素重新放回片内，从而保证了大规模优先队列处理的正确性。选取真实的公路网络数据进行测试，实验结果表明基于FPGA的并行单源最短路径算法和通用微处理器上的软件实现相比可以获得5倍的加速效果，并且功耗仅为通用微处理器的1/4。
　　（2）提出了面向大规模图最小生成树计算的FPGA并行算法和硬件实现结构。针对现有最小生成树计算的FPGA实现并行度开发不够和不能处理大规模图的问题，提出了一种基于Prim算法的FPGA最小生成树并行算法。该算法选取多个起始结点并行执行Prim算法生成多个子树，当检测到子树间冲突时，停止当前子树生成，选择其它的未访问结点继续生成新的子树，当所有结点都被访问时，对所有的子树进行合并。对于单个子树的Prim计算，提出了基于线性阵列优先队列的实现方法，当优先队列溢出时，采用DRAM存储溢出队列元素，实现了大规模子树生成。选取随机生成图进行测试，实验结果表明基于FPGA的并行最小生成树算法和通用微处理器上的软件实现相比可以获得2.58倍到6.88倍的加速比。
　　（3）提出了面向大规模图宽度优先搜索（BFS）的FPGA消息传递并行算法和硬件实现结构。针对大规模并行宽度优先搜索通信延迟大的问题，首次提出了一种新颖的基于二维消息传递阵列结构的并行宽度优先搜索算法，利用片上存储减少了处理单元之间的通信延迟。与相关工作相比，该结构显著减少了片上存储资源的消耗，并且具备良好的可扩展性，能够映射到多FPGA系统。此外，提出了一种基于片上位图存储的分布式队列实现方法，该方法避免了为判断顶点是否为当前层待搜索顶点而引入的片外访存开销。使用不同类型的图进行了测试，并与相关工作进行了比较。由于随机访存的延迟较大，单片FPGA上的BFS算法实测性能低于相关工作的性能。尽管如此，本文提出的FPGA并行BFS算法和硬件结构在理论上能够扩展到任意数量FPGA构成的计算系统。
　　（4）提出了面向大规模图匹配的FPGA并行算法和硬件实现结构。针对现有二部图图匹配计算的FPGA实现基于片上存储保存图数据，无法高效处理大规模图匹配的问题，提出了一种二部图图匹配的并行算法，该算法每次对未指派的多个结点进行并行处理，提高了并行性，在此基础上提出了一种基于片外存储的二部图匹配并行计算体系结构，与相关FPGA实现相比，该结构可以处理更大规模的图匹配。选取随机生成图进行了测试，实验结果表明，FPGA实现优于通用处理器的实现。

目录

声明

第一章 绪论

1.1 研究背景

1.2 研究现状

1.3 论文主要工作和创新点

1.4 论文组织结构

第二章 基于FPGA的并行单源最短路径算法

2.1 研究背景

2.2 相关工作

2.3 基于FPGA的并行单源最短路径

2.4 性能分析

2.5 实验测评

2.6 本章小结

第三章 基于FPGA的并行最小生成树算法

3.1 研究背景

3.2 相关工作

3.3 并行最小生成树计算

3.4 实验测评

3.5 本章小结

第四章 基于FPGA的并行宽度优先搜索算法

4.1 研究背景

4.2 相关工作

4.3 消息传递并行BFS算法

4.4 实验测评

4.5 本章小结

第五章 基于FPGA的并行图匹配算法

5.1 研究背景

5.2 相关工作

5.3 图匹配并行算法与结构

5.4 实验测评

5.5 本章小结

第六章 结论与展望

6.1 工作总结

6.2 研究展望

致谢

参考文献

作者在学期间取得的学术成果