Accelerating All-Pairs Shortest Path Using A Message-Passing Reconfigurable Architecture
| Authors | Osama Attia, Alex Grieve, Kevin Townsend, Phillip Jones, and Joseph Zambreno |
|---|---|
| Type | Conference Paper |
| Published in | Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig) |
| Date | December 2015 |
Abstract
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.
BibTeX
@conference{AttGri15A,
title = {Accelerating All-Pairs Shortest Path Using A Message-Passing Reconfigurable Architecture},
booktitle = {Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig)},
year = {2015},
month = dec,
author = {Attia, Osama and Grieve, Alex and Townsend, Kevin and Jones, Phillip and Zambreno, Joseph}
}