论文部分内容阅读
图(Graph)是一种以顶点和边构成的包含多种信息的复杂数据结构,图计算(Graph Computing)则是在图数据中寻找一定关系的一类计算的总称。图计算将现实条件中的关系属性抽象为图数据结构并进行复杂计算,而如何在极大规模的图数据集上完成高性能的计算是图计算需要解决的关键问题。可编程逻辑门阵列(Field-Programmable Gate Array,FPGA)作为并行化的计算密集型加速硬件,拥有卓越的性能功耗比,对比基于GPU和GPU的图计算架构具有独特的优势,因此将FPGA应用于图计算、实现图计算的加速,具有巨大的潜力。基于FPGA的图计算研究已经开展多年,期间出现了不少优秀的算法,ForeGraph就是最近提出的优秀算法之一。ForeGraph算法的核心架构基于GridGraph图划分方法和FPGA硬件加速,它充分利用FPGA片内存储系统(Block Random Access Momery,BRAM)的高效随机访存能力,在多块FPGA开发板上实现了基于简单环结构的图计算架构。但是,当将ForeGraph在单一FPGA开发板上实现时,则在数据预处理、数据调度策略、BRAM和数据存储结构等方面均存在不足。针对ForeGraph在单一FPGA开发板上实现存在的上述问题,设计了高性能单FPGA开发板图计算架构FabGraph,FabGraph虽然仍是基于传统外存储设备、流水线和边流方式进行图计算,但是通过2级缓存(Cache)结构和基于窗口滑动的希尔伯特(Hilbert)调度算法,运算核心(Processor Kernel,PK)聚集及其交错运行,解决了ForeGraph数据膨胀和数据本地性无法利用等核心问题。在单一FPGA开发板上实现了FabGraph,并通过性能分析,在实现过程中有针对性的对其性能进行了改进和优化,如除BRAM外还利用了新型FPGA的URAM(Ultra Random Access Momery)、Hilbert调度算法、2级Cache架构、PK聚集及其交错运行、BRAM间高带宽传输、虚拟流水线等。利用现有的图数据集对FabGraph进行了性能仿真和测试,仿真测试过程中,内存(DRAM)带宽采用DRAMSim2来模拟,计算效率则通过Vivado仿真实现。对比测试发现,相同情况下,FabGraph的性能在大多数测试集上比ForeGraph高出1~3倍,证明FabGraph达到了研究目的。