Hardware/Software Codesign for All-Pairs Shortest-Paths on a Reconfigurable Supercomputer

Rapid advances in VLSI technology have led to FieldProgrammable Gate Arrays (FPGAs) being employed in High Performance Computing systems. Applications using FPGAs on reconfigurable supercomputers involve software on the system managing computation on the reconfigurable hardware. To extract maximum benefits from a parallel FPGA kernel at the application level, it becomes crucial to minimize data movement costs on the system. We address this challenge in the context of the All-Pairs Shortest-Paths (APSP) problem in a directed graph. Employing a parallel FPGA-based APSP kernel with a blocked algorithm, with appropriate optimizations, the application-level speedup of the FPGA-based implementation over a modern generalpurpose microprocessor is increased from 4x to 15x for all problem sizes