A Caltech Library Service

GraphStep: A System Architecture for Sparse-Graph Algorithms

deLorimier, Michael and Kapre, Nachiket and Mehta, Nikil and Rizzo, Dominic and Eslick, Ian and Rubin, Raphael and Uribe, Tomás E. and Knight, Thomas F., Jr. and DeHon, André (2006) GraphStep: A System Architecture for Sparse-Graph Algorithms. In: FCCM 2006: 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines. Annual IEEE Symposium on Field-Programmable Custom Computing Machines . IEEE , Los Alamitos, CA, pp. 143-151. ISBN 0-7695-2661-6.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Many important applications are organized around long-lived, irregular sparse graphs (e.g., data and knowledge bases, CAD optimization, numerical problems, simulations). The graph structures are large, and the applications need regular access to a large, data-dependent portion of the graph for each operation (e.g., the algorithm may need to walk the graph, visiting all nodes, or propagate changes through many nodes in the graph). On conventional microprocessors, the graph structures exceed on-chip cache capacities, making main-memory bandwidth and latency the key performance limiters. To avoid this “memory wall,” we introduce a concurrent system architecture for sparse graph algorithms that places graph nodes in small distributed memories paired with specialized graph processing nodes interconnected by a lightweight network. This gives us a scalable way to map these applications so that they can exploit the high-bandwidth and low-latency capabilities of embedded memories (e.g., FPGA Block RAMs). On typical spreading activation queries on the ConceptNet Knowledge Base, a sample application, this translates into an order of magnitude speedup per FPGA compared to a state-of-the-art Pentium processor.

Item Type:Book Section
Related URLs:
URLURL TypeDescription DOIArticle
Additional Information:© 2006 IEEE. Issue Date: 24-26 April 2006, Date of Current Version: 11 December 2006. This work was supported in part by DARPA under grant FA8750-05-C-0011, the NSF CAREER program under grant CCR-0133102, and the Microelectronics Advanced Research Consortium (MARCO) as part of the efforts of the Gigascale Systems Research Center (GSRC). Xilinx Corporation donated hardware, including the XC2V6000s used for the FPGA implementation.
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)FA8750-05-C-0011
Microelectronics Advanced Research Consortium (MARCO)UNSPECIFIED
Gigascale Systems Research CenterUNSPECIFIED
Series Name:Annual IEEE Symposium on Field-Programmable Custom Computing Machines
Record Number:CaltechAUTHORS:20110223-132654232
Persistent URL:
Official Citation:deLorimier, M.; Kapre, N.; Mehta, N.; Rizzo, D.; Eslick, I.; Rubin, R.; Uribe, T.E.; Knight, T.F.; DeHon, A.; , "GraphStep: A System Architecture for Sparse-Graph Algorithms," Field-Programmable Custom Computing Machines, 2006. FCCM '06. 14th Annual IEEE Symposium on , vol., no., pp.143-151, 24-26 April 2006 doi: 10.1109/FCCM.2006.45 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:22460
Deposited By: Benjamin Perez
Deposited On:23 Feb 2011 22:47
Last Modified:09 Nov 2021 16:05

Repository Staff Only: item control page