|Accelerating All-Pairs Shortest Path Using A Message-Passing Reconfigurable Architecture
|Attia, O., A. Grieve, K. Townsend, P. Jones, and J. Zambreno
|Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig)
In this paper, we study the design and implementation of a reconfigurable architecture for graph processing algorithms. The architecture uses a message-passing model targeting shared-memory multi-FPGA platforms. We take advantage of our architecture to showcase a parallel implementation of the all-pairs shortest path algorithm (APSP) for unweighted directed graphs. Our APSP implementation adopts a fine-grain processing methodology while attempting to minimize communication and synchronization overhead. Our design utilizes 64 parallel kernels for vertex-centric processing. We evaluate a prototype of our system on a Convey HC-2 high performance computing platform, in which our performance results demonstrates an average speedup of 7.9x over the sequential APSP algorithm and an average speedup of 2.38x over a multi-core implementation.