论文部分内容阅读
图计算在现代社会中的应用越来越广泛，例如在社交网络，生物信息学和信息网络中均有大量应用。由于图结构的不确定性、幂律分布以及复杂依赖关系等特性，图计算在使用冯·诺依曼体系结构的通用处理器(Central Processing Unit，CPU)上的处理效率远未达到理想水平。一方面，由于图的不规则性，导致内存访问的时间过长进而引发流水线插槽无法正常地回退，后续的指令无法正常进入流水线插槽执行。因此，每个周期执行的指令数很少。另一方面，图的不规则性使得图计算应用中大量分支难以较好地预测下一邻居节点的信息，导致指令回滚和重新执行，造成大量性能损耗。而数据流执行模型因其天然的细粒度并行性，可以有效地解决低效指令级并行和分支预测失效的问题。通过在可编程逻辑门阵列(Field Programmable Gate Array， FPGA)实现数据流执行模型与通用处理器CPU进行异构，开展合适的执行模型研究各取两种架构之所长对提升图计算的处理效率有着重要的作用。
基于顶点活跃度的异构CPU-FPGA图计算平台，针对图计算过程中低效的指令级并行和低效的分支预测问题，根据顶点活跃度的变化情况，可判断图计算在不同的迭代阶段，并依据迭代阶段的不同选择不同的执行模型。具体而言，在图计算迭代的初期或后期阶段，因为顶点活跃度相对较低(指活跃顶点的比例较低)，邻居节点信息较好预测，此时CPU可以发挥较好的作用。在图计算中间阶段，顶点活跃度相对较高(指活跃顶点的比例较高)，面临着大量不规则访存，且邻居节点状态难以预测，传统CPU执行模型面临低效的指令级并行和低效的分支预测问题。此时，使用基于FPGA的特定数据流执行模型可规避上述开销。总体来看，基于顶点活跃度的异构CPU-FPGA图计算调度机制包括：1)基于图划分后的源顶点活跃度的检测机制，使用启发式算法判断子图当前处于图计算哪个阶段；2)两种执行模式的调度机制，应用了收集-应用-扩散(Gather-Apply-Scatter，GAS)执行模型来解决两种执行模型的差异问题并提高了同步效率；3)兼容不同执行模式的通用数据结构，采用了稀疏矩阵的坐标存储(Coordinate，COO)存储格式，配合interval-shard的图划分方法同时存储顶点和边数组，使其兼容两种执行模式，提高运行效率。
在典型CPU-FPGA平台上对混合执行模型进行了实现。实验结果表明，与国际上典型的的CPU-FPGA图计算加速器相比，混合执行模型将吞吐量提高了2.2倍；与典型的FPGA设计相比，吞吐量提高2.4倍。
基于顶点活跃度的异构CPU-FPGA图计算平台，针对图计算过程中低效的指令级并行和低效的分支预测问题，根据顶点活跃度的变化情况，可判断图计算在不同的迭代阶段，并依据迭代阶段的不同选择不同的执行模型。具体而言，在图计算迭代的初期或后期阶段，因为顶点活跃度相对较低(指活跃顶点的比例较低)，邻居节点信息较好预测，此时CPU可以发挥较好的作用。在图计算中间阶段，顶点活跃度相对较高(指活跃顶点的比例较高)，面临着大量不规则访存，且邻居节点状态难以预测，传统CPU执行模型面临低效的指令级并行和低效的分支预测问题。此时，使用基于FPGA的特定数据流执行模型可规避上述开销。总体来看，基于顶点活跃度的异构CPU-FPGA图计算调度机制包括：1)基于图划分后的源顶点活跃度的检测机制，使用启发式算法判断子图当前处于图计算哪个阶段；2)两种执行模式的调度机制，应用了收集-应用-扩散(Gather-Apply-Scatter，GAS)执行模型来解决两种执行模型的差异问题并提高了同步效率；3)兼容不同执行模式的通用数据结构，采用了稀疏矩阵的坐标存储(Coordinate，COO)存储格式，配合interval-shard的图划分方法同时存储顶点和边数组，使其兼容两种执行模式，提高运行效率。
在典型CPU-FPGA平台上对混合执行模型进行了实现。实验结果表明，与国际上典型的的CPU-FPGA图计算加速器相比，混合执行模型将吞吐量提高了2.2倍；与典型的FPGA设计相比，吞吐量提高2.4倍。