Exploring FPGA Optimizations in OpenCL for Breadth-First Search on Sparse Graph Datasets
Exploring FPGA Optimizations in OpenCL for Breadth-First Search on Sparse Graph Datasets
复制标题
DOI：
10.1109/fpl50879.2020.00032
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Atharva Gondhalekar;W. Feng
中科院分区：
文献类型：
--
作者：
Atharva Gondhalekar;W. Feng
呼吸优先搜索（Breath-First Search，BFS）是许多基于图的应用程序中的基本构建块。由于其不规则的内存访问模式，优化具有挑战性。以前的工作，基于硬件描述语言（HDL）和高级综合（HLS），解决内存访问瓶颈，使用技术，如边缘为中心的遍历，数据对齐，和计算单元（CU）复制。虽然这些优化对于密集图数据集效果很好，但由于内核启动开销和处理元素之间的工作负载分布不佳，在稀疏图上优化BFS仍然是一个重大挑战。作为对先前工作的补充，我们在OpenCL中提出并评估了稀疏图上的BFS优化。具体来说，我们探索特定于应用程序和架构感知的优化，旨在减轻不规则的全局内存访问瓶颈稀疏图。在我们的内核设计中，我们考虑的因素，如队列和数组之间的数据结构的选择，存储体的数量，和内核启动配置。我们评估了不同的稀疏图集上提出的优化的影响。与最先进的OpenCL实现FPGA相比，我们实现了5.7倍-22.3倍的加速Stratix 10 SX 2800 FPGA的图形是最敏感的，我们的优化方案。
Breath-first search (BFS) is a fundamental building block in many graph-based applications. It is challenging to optimize due to its irregular memory-access pattern. Prior work, based on hardware description languages (HDLs) and high-level synthesis (HLS), address the memory-access bottleneck by using techniques such as edge-centric traversal, data alignment, and compute-unit (CU) replication. While these optimizations work well for dense graph datasets, optimizing BFS on sparse graphs remains a significant challenge due to the kernel launch overhead and poor workload distribution across processing elements. As a complement to the prior work, we present and evaluate optimizations in OpenCL for BFS on sparse graphs. Specifically, we explore application-specific and architecture-aware optimizations aimed at mitigating the irregular global-memory access bottleneck in sparse graphs. In our kernel design, we consider factors such as choice of data structure between queue and array, number of memory banks, and kernel launch configuration. We evaluate the impact of proposed optimizations on a diverse set of sparse graphs. In comparison with the state-of-the-art OpenCL implementation for FPGA, we achieve 5.7X-22.3X speedup on Stratix 10 SX 2800 FPGA for the graphs that are most sensitive to our optimization scheme.