PaperlayerView exact revision on arXiv

Source-linked AI summary

GraphR: Accelerating Graph Processing Using ReRAM

Linghao Song, Youwei Zhuo, Xuehai Qian, Hai Li, Yiran Chen

arXiv:1708.06248v4cs.DCcs.AR

TL;DR

Graph processing suffers from costly data movement and irregular access, raising the question of whether ReRAM can efficiently exploit graph algorithms’ matrix structure. GRAPHR maps suitable vertex programs to sparse matrix-vector multiplication on ReRAM crossbars, and reports strong speedup and energy results against CPU, GPU, and PIM baselines. Its evaluated configuration assumes an out-of-core single-node setting, while multi-node communication remains future work.

  • Problem

    Graph processing has poor locality, high bandwidth requirements, and costly data movement, while sparse representations complicate efficient matrix-vector computation.

  • Method

    GRAPHR combines compressed graph storage in memory ReRAM with ReRAM-crossbar graph engines that process sparse subgraphs through matrix-vector multiplication.

  • Results

    16.01× geometric-mean speedup and 33.82× energy saving are reported versus a CPU baseline, with additional speedup and energy advantages over GPU and PIM.

  • Takeaways & Limitations

    ReRAM crossbars can efficiently perform graph computations expressible as SpMV, with parallel-operation benefits outweighing sparsity waste on small subgraphs.

  • Takeaways & Limitations

    The evaluation assumes one GRAPHR node in an out-of-core setting and leaves inter-node communication support for future work.

Abstract

from arXiv · show

This paper presents GRAPHR, the first ReRAM-based graph processing accelerator. GRAPHR follows the principle of near-data processing and explores the opportunity of performing massive parallel analog operations with low hardware and energy cost. The analog computation is suit- able for graph processing because: 1) The algorithms are iterative and could inherently tolerate the imprecision; 2) Both probability calculation (e.g., PageRank and Collaborative Filtering) and typical graph algorithms involving integers (e.g., BFS/SSSP) are resilient to errors. The key insight of GRAPHR is that if a vertex program of a graph algorithm can be expressed in sparse matrix vector multiplication (SpMV), it can be efficiently performed by ReRAM crossbar. We show that this assumption is generally true for a large set of graph algorithms. GRAPHR is a novel accelerator architecture consisting of two components: memory ReRAM and graph engine (GE). The core graph computations are performed in sparse matrix format in GEs (ReRAM crossbars). The vector/matrix-based graph computation is not new, but ReRAM offers the unique opportunity to realize the massive parallelism with unprecedented energy efficiency and low hardware cost. With small subgraphs processed by GEs, the gain of performing parallel operations overshadows the wastes due to sparsity. The experiment results show that GRAPHR achieves a 16.01x (up to 132.67x) speedup and a 33.82x energy saving on geometric mean compared to a CPU baseline system. Com- pared to GPU, GRAPHR achieves 1.69x to 2.19x speedup and consumes 4.77x to 8.91x less energy. GRAPHR gains a speedup of 1.16x to 4.12x, and is 3.67x to 10.96x more energy efficiency compared to PIM-based architecture.

1. INTRODUCTION

Graph processing suffers from irregular memory access, bandwidth demands, and data movement, motivating GRAPHR, a ReRAM-based accelerator that maps graph computation to sparse matrix-vector multiplication. The design combines ReRAM storage and graph engines, with experiments showing substantial speedup and energy savings against CPU, GPU, and PIM baselines.

  • Graph processing has poor locality and high memory-bandwidth requirements, causing substantial data movement and energy consumption on conventional architectures.
  • ReRAM analog computation suits graph algorithms because iterative methods tolerate imprecision and probability- or integer-based algorithms are resilient to errors.
  • GRAPHR addresses compressed data representation, graph size, execution ordering, and algorithm mapping through its architecture and processing models.
  • GRAPHR combines memory ReRAM for compressed graph storage with ReRAM-crossbar graph engines for matrix-vector multiplication, streaming-apply execution, and algorithm-specific mapping patterns.
  • 16.01× geometric-mean speedup and 33.82× energy saving are achieved versus the CPU baseline, while GPU and PIM comparisons also favor GRAPHR.Against GPU, speedup is 1.69× to 2.19× with 4.77× to 8.91× lower energy; against PIM, speedup is 1.16× to 4.12× with 3.67× to 10.96× greater energy efficiency.

2. BACKGROUND AND MOTIVATION

Graph processing is constrained by sparse, irregular accesses and costly disk or memory movement, while ReRAM offers dense in-situ matrix-vector multiplication. The background motivates processing sparse graph submatrices in ReRAM while retaining compressed graph storage and supporting out-of-core systems.

  • 2.1 Graph Processing: Sparse graph traversal produces random vertex accesses, bandwidth waste, and significant data movement, making sequential disk access especially important for out-of-core systems.
  • 2.1 Graph Processing: X-Stream accesses partitioned edges sequentially but may generate updates as large as the edge set; GridGraph reduces this overhead with dual sliding windows.
  • 2.2 ReRAM Basics: ReRAM is a dense, fast-read, low-leakage non-volatile memory whose crossbars perform in-situ matrix-vector multiplication through bitline-current summation.
  • 2.3 Graph Processing Accelerators: Existing graph accelerators mainly optimize memory access or place computation near memory, whereas GRAPHR targets low-cost parallel computation with ReRAM.
  • 2.4 Graph Representation: GRAPHR stores most graph data in compressed sparse form but processes small subgraphs in uncompressed sparse matrix form to exploit ReRAM parallelism.
  • 2.4 Graph Representation: CSC, CSR, and COO are the three major compressed sparse representations, differing in whether nonzeros are organized by columns, rows, or coordinate tuples.
  • 2.4 Graph Representation: GRAPHR assumes COO graph storage; in the example, COO saves 61% of storage, while WikiVote requires 0.2% of adjacency-matrix space.

3. GRAPHR ARCHITECTURE

GRAPHR combines ReRAM memory with graph engines built from ReRAM crossbars to execute graph vertex programs as sparse matrix-vector multiplications. Its architecture uses compressed graph storage, preprocessing, streaming-apply execution, and buffered reductions to process large graphs while managing crossbar size and processing-order constraints.

  • 3.1 Sparse Matrix Vector Multiplication (SpMV) and Graph Processing: A vertex program maps to SpMV: edge processing performs multiplication, and destination updates require multiply-accumulate operations followed by reduction.The mapping enables parallel execution of vertex programs using ReRAM crossbars.
  • 3.1 Sparse Matrix Vector Multiplication (SpMV) and Graph Processing: Because crossbars are small and large graphs may exceed memory, GRAPHR partitions graphs into subgraphs and streams them through multiple graph engines.A controller converts compressed edge data into matrix form, while intermediate subgraph results are buffered for reduction.
  • 3.2 GraphR Architecture: GRAPHR supports multi-node and out-of-core operation, allowing blocks to be processed across nodes or consecutively by one accelerator.The out-of-core setting integrates with a graph-processing framework that loads blocks from disk.
  • 3.2 GraphR Architecture: GRAPHR stores graph data in compressed sparse representation and uses graph engines to execute matrix-vector multiplications on ReRAM crossbars.Memory ReRAM stores the graph, while GEs perform computation on sparse matrix representations.
  • 3.3 Streaming-Apply Execution Model: The streaming-apply model processes subgraphs in column-major or row-major order, trading register usage against repeated source-vertex reads.GRAPHR selects column-major order because it requires fewer registers and ReRAM writes cost more than reads.
  • 3.5 Discussion: GRAPHR’s analog parallelism improves energy efficiency, while preprocessing and streaming make disk and memory accesses sequential but reduce scheduling flexibility.The architecture is intended as a drop-in accelerator for out-of-core graph processing and targets vertex programs expressible in SpMV form.

4. MAPPING ALGORITHMS IN GE

GRAPHR maps graph algorithms to two graph-engine patterns: parallel MAC and parallel add-op. These patterns use ReRAM crossbars to execute sparse graph computations on small matrix blocks.

  • Parallel MAC: Parallel MAC applies when processEdge performs multiplication in each crossbar cell, with parallelization roughly C × C × N × G.
  • Parallel MAC: PageRank exemplifies parallel MAC through iterative probability updates computed as a matrix-vector multiplication plus a probability vector.
  • Parallel Add-Op: Parallel add-op applies when processEdge performs addition across each crossbar row, while the sALU executes the reduce operation.
  • Parallel Add-Op: SSSP maps to parallel add-op because edge relaxation adds source distance and edge weight, then reduction selects the minimum distance.
  • Parallel Add-Op: For SSSP, an one-hot vector selects an adjacency-matrix row, allowing edge weights to be added to a source distance in parallel.
  • Parallel Add-Op: The SSSP crossbar uses a fixed final row to add dist(u), processes source vertices across time slots, and activates updated destinations for the next iteration.

5. EVALUATION

GRAPHR is evaluated against CPU, GPU, and PIM-based systems across graph-processing applications and datasets. It shows broad performance and energy advantages, while increasing sparsity modestly reduces both benefits.

  • Evaluation Setup: The evaluation uses seven real-world graphs and runs PageRank, BFS, SSSP, SpMV, or collaborative filtering across CPU, GPU, and PIM comparisons.
  • Performance Results: GRAPHR achieves a 16.01× geometric-mean speedup over CPU, with a maximum speedup of 132.67× on SpMV for WikiVote.
  • Energy Results: GRAPHR achieves 33.82× geometric-mean energy savings over CPU, reaching 217.88× on SpMV for the Slashdot dataset.
  • Comparison to GPU Platform: GRAPHR provides 1.69× to 2.19× speedup and consumes 4.77× to 8.91× less energy than GPU.
  • Comparison to PIM Platform: Compared with PIM-based architecture, GRAPHR achieves 1.16× to 4.12× speedup and 3.67× to 10.96× greater energy efficiency.
  • Sensitivity to Sparsity: As dataset sparsity increases, GRAPHR's performance and energy savings slightly decrease because more edge blocks must be traversed.

6. CONCLUSION

GRAPHR is a ReRAM-based graph accelerator that performs sparse matrix-vector computations in ReRAM crossbars. It delivers substantial speedup and energy savings against CPU, GPU, and PIM baselines.

  • GRAPHR uses memory ReRAM for compressed sparse graph storage and ReRAM-crossbar graph engines for core sparse matrix-vector computations.
  • The accelerator targets vertex programs expressible as sparse matrix-vector multiplication, using small subgraphs to exploit parallel operations despite sparsity.
  • GRAPHR achieves 16.01× geometric-mean speedup and 33.82× energy savings over CPU, with additional gains over GPU and PIM-based architectures.
Loading 1708.06248v4…