Hardware/Software Integration for FPGA-based All-Pairs Shortest-Paths
Field-Programmable Gate Arrays (FPGAs) are be- ing employed in high performance computing systems owing to their potential to accelerate a wide variety of long-running routines. Parallel FPGA-based de- signs often yield a very high speedup. Applications us- ing these designs on reconfigurable supercomputers in- volve software on the system managing computation on the FPGA. To extract maximum performance from an FPGA design at the application level, it becomes neces- sary to minimize associated data movement costs on the system. We address this hardware/software integration challenge in the context of the All-Pairs Shortest-Paths (APSP) problem in a directed graph. We employ a par- allel FPGA-based design using a blocked algorithm to solve large instances of APSP. With appropriate design choices and optimizations, experimental results on the Cray XD1 show that the FPGA-based implementation sustains an application-level speedup of 15 over an op- timized CPU-based implementation.