
@conference {AttJoh14A,
	title = {CyGraph: A Reconfigurable Architecture for Parallel Breadth-First Search},
	booktitle = {Proceedings of the Reconfigurable Architectures Workshop (RAW)},
	year = {2014},
	month = {May},
	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.
},
	author = {Osama Attia and Tyler Johnson and Kevin Townsend and Phillip Jones and Joseph Zambreno}
}
