An Efficient ReRAM-based Accelerator for Asynchronous Iterative Graph Processing
Open Access
- 20 March 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 22 (1) , 1-26
Abstract
Graph processing has become a central concern for many real-world applications and is well-known for its low compute-to-communication ratios and poor data locality. By integrating computing logic into memory, resistive random access memory (ReRAM) tackles the demand for high memory bandwidth in graph processing. Despite the years’ research efforts, existing ReRAM-based graph processing approaches still face the challenges of redundant computation overhead . It is because the vertices of many subgraphs are ineffectively and repeatedly processed over the ReRAM crossbars for lots of iterations so as to update their states according to the vertices of other subgraphs regardless of the dependencies among the subgraphs. In this article, we propose ASGraph , a dependency-aware ReRAM-based graph processing accelerator that overcomes the aforementioned performance bottlenecks. Specifically, ASGraph dynamically constructs the subgraph based on the dependencies between vertices’ states and then detects constructed subgraph that owns high value (it is likely that it has accumulated many state propagations from its neighbors and is able to affect more other neighbors) to be preferentially processed. In this way, it makes the vertex states propagate along the dependencies between vertices as much as possible to reduce the redundant computation. Besides, ASGraph employs a hybrid processing scheme to accelerate the state propagations of the tightly connected subgraph, thereby minimizing the redundant computations. Experimental results show that ASGraph achieves 25.5× and 4.8× speedup and 70.8× and 2.2× energy saving on average compared with the state-of-the-art ReRAM-based graph processing accelerators, that is, GraphR and GaaS-X, respectively.Keywords
Funding Information
- National Key Research and Development Program of China (2023YFB4502300)
- Key Research and Development Program of Hubei Province (2023BAB078)
- Knowledge Innovation Program of Wuhan-Basi Research (2022013301015177)
- HUAWEI Technologies Co., LTD (YBN2021035018A6)
This publication has 33 references indexed in Scilit:
- Accelerating Graph Convolutional Networks Through a PIM-Accelerated ApproachIEEE Transactions on Computers, 2023
- A Structure-Aware Storage Optimization for Out-of-Core Concurrent Graph ProcessingIEEE Transactions on Computers, 2021
- Exploiting Locality in Graph Analytics through Hardware-Accelerated Traversal Scheduling2018
- Efficient Disk-Based Directed Graph Processing: A Strongly Connected Component ApproachIEEE Transactions on Parallel and Distributed Systems, 2017
- HotGraph: Efficient Asynchronous Processing for Real-World GraphsIEEE Transactions on Computers, 2016
- Maiter: An Asynchronous Graph Processing Framework for Delta-Based Accumulative Iterative ComputationIEEE Transactions on Parallel and Distributed Systems, 2013
- NVSim: A Circuit-Level Performance, Energy, and Area Model for Emerging Nonvolatile MemoryIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2012
- Metal–Oxide RRAMProceedings of the IEEE, 2012
- Graph-based Natural Language Processing and Information Retrieval2011
- A model of a trust-based recommendation system on a social networkAutonomous Agents and Multi-Agent Systems, 2007