An FPGA framework for edge-centric graph processing
An FPGA framework for edge-centric graph processing
复制标题
DOI：
10.1145/3203217.3203233
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Shijie Zhou;R. Kannan;Hanqing Zeng;V. Prasanna
中科院分区：
文献类型：
--
作者：
Shijie Zhou;R. Kannan;Hanqing Zeng;V. Prasanna
许多新兴的现实应用程序需要以图表形式代表的大规模数据设计非常灵活，可以加速具有各种顶点属性和更新传播功能的常规图算法，例如稀疏矩阵矢量乘法（SPMV），Pagerank （PR），单源最短路径（SSSP）和弱连接的组件（WCC）。资源约束作为输入，我们的框架可以确定最佳设计参数，并产生优化的寄存器 - 转移级别（RTL）FPGA加速器设计局部性并增加了并行性，我们将输入图划分为非重叠的分区。优化的数据布局以改善外部内存性能并根据我们的设计方法减少数据通信。绩效评估：稀疏的基质载体乘法（SPMV）和PAGERANK（PR）分别为SPMV和PR分别具有高达22.5亿个遍历的速度几种高度优化的多核设计，我们的FPGA框架可用于SPMV的20.5倍速度，PR的加速17.7倍，与两个最先进的FPGA框架相比，我们的设计分别为SPMV和PR提供了5.3×和1.8倍的吞吐量改进。
Many emerging real-world applications require fast processing of large-scale data represented in the form of graphs. In this paper, we design a Field-Programmable Gate Array (FPGA) framework to accelerate graph algorithms based on the edge-centric paradigm. Our design is flexible for accelerating general graph algorithms with various vertex attributes and update propagation functions, such as Sparse Matrix Vector Multiplication (SpMV), PageRank (PR), Single Source Shortest Path (SSSP), and Weakly Connected Component (WCC). The target platform consists of large external memory to store the graph data and FPGA to accelerate the processing. By taking an edge-centric graph algorithm and hardware resource constraints as inputs, our framework can determine the optimal design parameters and produce an optimized Register-Transfer Level (RTL) FPGA accelerator design. To improve data locality and increase parallelism, we partition the input graph into non-overlapping partitions. This enables our framework to efficiently buffer vertex data in the on-chip memory of FPGA and exploit both inter-partition and intra-partition parallelism. Further, we propose an optimized data layout to improve external memory performance and reduce data communication between FPGA and external memory. Based on our design methodology, we accelerate two fundamental graph algorithms for performance evaluation: Sparse Matrix Vector Multiplication (SpMV) and PageRank (PR). Experimental results show that our accelerators sustain a high throughput of up to 2250 Million Traversed Edges Per Second (MTEPS) and 2487 MTEPS for SpMV and PR, respectively. Compared with several highly-optimized multi-core designs, our FPGA framework achieves up to 20.5× speedup for SpMV, and 17.7× speedup for PR, respectively; compared with two state-of-the-art FPGA frameworks, our designs demonstrate up to 5.3× and 1.8× throughput improvement for SpMV and PR, respectively.