CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search
CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search
复制标题
DOI：
10.1109/ipdpsw.2014.30
复制
发表时间：
2014-05
期刊：
影响因子：
--
通讯作者：
Osama G. Attia;Tyler Johnson;Kevin Townsend;Phillip H. Jones;Joseph Zambreno
中科院分区：
文献类型：
--
作者：
Osama G. Attia;Tyler Johnson;Kevin Townsend;Phillip H. Jones;Joseph Zambreno
大规模图结构被认为是许多新兴高性能计算应用的基石，其中广度优先搜索（BFS）是重要的构建块。对于这样的图结构，BFS操作往往是内存绑定的，而不是计算绑定的。在本文中，我们提出了一种高效的可重构并行BFS架构，该架构采用了新的优化方法来利用内存带宽。我们的架构采用基于压缩稀疏原始格式（CSR）的自定义图表示，以及对传统BFS算法的重构。通过最大限度地利用可用的内存带宽，我们的架构可以持续地保持处理元素的活动。使用商用高性能可重构计算系统（Convey HC-2），我们的结果表明，与之前发布的基于fpga的实现相比，我们的速度提高了5倍。
Large-scale graph structures are considered as a keystone for many emerging high-performance computing applications in which Breadth-First Search (BFS) is an important building block. For such graph structures, BFS operations tends to be memory-bound rather than compute-bound. In this paper, we present an efficient reconfigurable architecture for parallel BFS that adopts new optimizations for utilizing memory bandwidth. Our architecture adopts a custom graph representation based on compressed-sparse raw format (CSR), as well as a restructuring of the conventional BFS algorithm. By taking maximum advantage of available memory bandwidth, our architecture continuously keeps our processing elements active. Using a commercial high-performance reconfigurable computing system (the Convey HC-2), our results demonstrate a 5× speedup over previously published FPGA-based implementations.