HAGAR: Multi-context Hardware Graph Accelerators
[International Conference on Field Programmable Logic (FPL), 2002]

Oskar Mencer, Zhining Huang, Lorenz Huelsbergen

abstract.

Graph algorithms, such as vertex reachability, transitive closure, and
shortest path, are fundamental in many computing applications. We address
the question of how to utilize the bit-level parallelism available in hardware
and specifically in FPGAs to implement such graph algorithms for speedup.

This paper generalizes the idea of a data-structure residing in reconfigurable
hardware that, along with support logic and software in a microprocessor,
accelerates a core algorithm. We give two examples. First, we draw parallels
to content addressable memories, which are an existing instantiation of this
idea. Secondly, we show how to extend the idea of mapping the adjacency
matrix representation of a graph to a HArdware Graph ARray (HAGAR).

We describe HAGAR implementations for graph reachability and shortest path.
Reachability is a building block that can further be used to implement
transitive closure,
connected components, and other high-level graph algorithms. To handle large graphs where such an approach can excel relative to software, we developa methodology, using an FPGA's small RAM blocks, to store and switch betweenmultiple contexts of a regular architecture. The proposed circuits areimplemented within the PAM-Blox module generation environment using Compaq's PamDC, and run on an FPGA accelerator card.