TitleCyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search
Publication TypeConference Papers
2014
AuthorsO. Attia, T. Johnson, K. Townsend, P. Jones and J. Zambreno
Conference NameProceedings of the Reconfigurable Architectures Workshop (RAW)
Date PublishedMay

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.

Paper attachments: