Solving graph problems with dynamic computation structures

Jonathan W. Babb; Matthew Frank; Anant Agarwal

doi:10.1117/12.255820

21 October 1996 Solving graph problems with dynamic computation structures

Jonathan W. Babb, Matthew Frank, Anant Agarwal

Proceedings Volume 2914, High-Speed Computing, Digital Signal Processing, and Filtering Using Reconfigurable Logic; (1996) https://doi.org/10.1117/12.255820
Event: Photonics East '96, 1996, Boston, MA, United States

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.

Citation Download Citation

Jonathan W. Babb, Matthew Frank, and 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); https://doi.org/10.1117/12.255820

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available