21 October 1996 Solving graph problems with dynamic computation structures
Author Affiliations +
Abstract
We introduce dynamic computation structures (DCS), a compilation technique to produce dynamic code for reconfigurable computing. DCS specializes directed graph instances into user-level hardware for reconfigurable architectures. Several problems such as shortest path and transitive closure exhibit the general properties of closed semirings, an algebraic structure for solving directed paths. Motivating our application domain choice of closed semiring problems is the fact that logic emulation software already maps a special case of directed graphs, namely logic netlists, onto arrays of field programmable gate arrays (FPGA). A certain type of logic emulation software called virtual wires further allows an FPGA array to be viewed as a machine-independent computing fabric. Thus, a virtual wires compiler, coupled with front-end commercial behavioral logic synthesis software, enables automatic behavioral compilation into a multi-FPGA computing fabric. We have implemented a DCS front-end compiler to parallelize the entire inner loop of the classic Bellman-Ford algorithm into synthesizable behavioral verilog. Leveraging virtual wire compilation and behavioral synthesis, we have automatically generated designs of 14 to 261 FPGAs from a single graph instance. We achieve speedups proportional to the number of graph edges - - from 10X to almost 400X versus a 125 SPECint SparcStation 10.
© (1996) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Jonathan W. Babb, Matthew Frank, Anant Agarwal, "Solving graph problems with dynamic computation structures", Proc. SPIE 2914, High-Speed Computing, Digital Signal Processing, and Filtering Using Reconfigurable Logic, (21 October 1996); doi: 10.1117/12.255820; https://doi.org/10.1117/12.255820
PROCEEDINGS
12 PAGES


SHARE
RELATED CONTENT

Design advantages of run-time reconfiguration
Proceedings of SPIE (August 26 1999)
Using the KressArray for reconfigurable computing
Proceedings of SPIE (October 08 1998)
WILDFIRE custom configurable computer
Proceedings of SPIE (September 19 1995)
Field programmable gate arrays and reconfigurable computing
Proceedings of SPIE (September 19 1995)

Back to Top