Share Email Print
cover

Proceedings Paper

Solving graph problems with dynamic computation structures
Author(s): Jonathan W. Babb; Matthew Frank; Anant Agarwal
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper 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.

Paper Details

Date Published: 21 October 1996
PDF: 12 pages
Proc. SPIE 2914, High-Speed Computing, Digital Signal Processing, and Filtering Using Reconfigurable Logic, (21 October 1996); doi: 10.1117/12.255820
Show Author Affiliations
Jonathan W. Babb, MIT Lab. for Computer Science (United States)
Matthew Frank, MIT Lab. for Computer Science (United States)
Anant Agarwal, MIT Lab. for Computer Science (United States)


Published in SPIE Proceedings Vol. 2914:
High-Speed Computing, Digital Signal Processing, and Filtering Using Reconfigurable Logic
John Schewel; Peter M. Athanas; V. Michael Bove; John Watson, Editor(s)

© SPIE. Terms of Use
Back to Top