TitleAccelerating All-Pairs Shortest Path Using A Message-Passing Reconfigurable Architecture
Publication TypeConference Papers
2015
AuthorsO. Attia, A. Grieve, K. Townsend, P. Jones and J. Zambreno
Conference NameProceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig)
Date PublishedDecember

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.

Paper attachments: