CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search
| Authors | Osama Attia, Tyler Johnson, Kevin Townsend, Phillip Jones, and Joseph Zambreno |
|---|---|
| Type | Conference Paper |
| Published in | Proceedings of the Reconfigurable Architectures Workshop (RAW) |
| Date | May 2014 |
Abstract
Large-scale graph structures are considered 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 utilizes 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 5x speedup over previously published FPGA-based implementations.
BibTeX
@conference{AttJoh14A,
title = {CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search},
booktitle = {Proceedings of the Reconfigurable Architectures Workshop (RAW)},
year = {2014},
month = may,
author = {Attia, Osama and Johnson, Tyler and Townsend, Kevin and Jones, Phillip and Zambreno, Joseph}
}