More Web Proxy on the site http://driver.im/

research-article

GraphSAR: a sparsity-aware processing-in-memory architecture for large-scale graph processing on ReRAMs

Authors:

John WawrzynekAuthors Info & Claims

ASPDAC '19: Proceedings of the 24th Asia and South Pacific Design Automation Conference

Pages 120 - 126

https://doi.org/10.1145/3287624.3287637

Published: 21 January 2019 Publication History

Abstract

Large-scale graph processing has drawn great attention in recent years. The emerging metal-oxide resistive random access memory (ReRAM) and ReRAM crossbars have shown huge potential in accelerating graph processing. However, the sparse feature of natural graphs hinders the performance of graph processing on ReRAMs. Previous work of graph processing on ReRAMs stored and computed edges separately, leading to high energy consumption and long latency of transferring data. In this paper, we present GraphSAR, a sparsity-aware processing-in-memory large-scale graph processing accelerator on ReRAMs. Computations over edges are performed in the memory, eliminating overheads of transferring edges. Moreover, graphs are divided considering the sparsity. Subgraphs with low densities are further divided into smaller ones to minimize the waste of memory space. According to our extensive experimental results, GraphSAR achieves 4.43x energy reduction and 1.85x speedup (8.19x lower energy-delay product, EDP) against previous graph processing architecture on ReRAMs (GraphR [1]).

References

[1]

Linghao Song et al. Graphr: Accelerating graph processing using reram. In HPCA, pages 531--543. IEEE, 2018.

[2]

Aapo Kyrola et al. Graphchi: Large-scale graph computation on just a pc. In OSDI, pages 31--46. USENIX, 2012.

Digital Library

[3]

Amitabha Roy et al. X-stream: Edge-centric graph processing using streaming partitions. In SOSP, pages 472--488. ACM, 2013.

Digital Library

[4]

Xiaowei Zhu et al. Gridgraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In ATC, pages 375--386. USENIX, 2015.

Digital Library

[5]

Yuze Chi et al. Nxgraph: An efficient graph processing system on a single machine. In ICDE, pages 409--420. IEEE, 2016.

[6]

Grzegorz Malewicz et al. Pregel: a system for large-scale graph processing. In SIGMOD, pages 135--146. ACM, 2010.

Digital Library

[7]

Yucheng Low et al. Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 5(8):716--727, 2012.

Digital Library

[8]

Tae Jun Ham et al. Graphicionado: A high-performance and energy-efficient accelerator for graph analytics. In MICRO, pages 1--13. IEEE, 2016.

Digital Library

[9]

Guohao Dai et al. Fpgp: Graph processing framework on fpga a case study of breadth-first search. In FPGA, pages 105--110. ACM, 2016.

Digital Library

[10]

Tayo Oguntebi et al. Graphops: A dataflow library for graph analytics acceleration. In FPGA, pages 111--117. ACM, 2016.

Digital Library

[11]

Guohao Dai et al. Foregraph: Exploring large-scale graph processing on multi-fpga architecture. In FPGA, pages 217--226. ACM, 2017.

Digital Library

[12]

Junwhan Ahn et al. A scalable processing-in-memory accelerator for parallel graph processing. In ISCA, pages 105--117. IEEE, 2015.

Digital Library

[13]

Guohao Dai et al. Graphh: A processing-in-memory architecture for large-scale graph processing. TCAD, 2018.

[14]

Mingxing Zhang et al. Graphp: Reducing communication of pim-based graph processing with efficient data partition. In HPCA, pages 544--557. IEEE, 2018.

[15]

Fabien Alibart et al. High precision tuning of state for memristive devices by adaptable variation-tolerant algorithm. Nanotechnology, 23(7):075201, 2012.

[16]

Cong Xu et al. Overcoming the challenges of crossbar resistive memory architectures. In HPCA, pages 476--488. IEEE, 2015.

[17]

Lixue Xia et al. Technological exploration of rram crossbar array for matrix-vector multiplication. JCST, 31(1):3--19, 2016.

[18]

Lei Han et al. A novel reram-based processing-in-memory architecture for graph computing. In NVMSA, pages 1--6. IEEE, 2017.

[19]

Tianhao Huang et al. Hyve: Hybrid vertex-edge memory hierarchy for energy-efficient graph processing. In DATE. EDA Consortium, 2018.

[20]

Cong Xu et al. Understanding the trade-offs in multi-level cell reram memory design. In DAC, pages 1--6. IEEE, 2013.

Digital Library

[21]

Xiaowei Zhu et al. Gemini: A computation-centric distributed graph processing system. In OSDI, pages 301--316. USENIX, 2016.

Digital Library

[22]

Scott Beamer et al. Locality exists in graph processing: Workload characterization on an ivy bridge server. In IISWC, pages 56--65. IEEE, 2015.

Digital Library

[23]

Jianwei Cui and Qinru Qiu. Towards memristor based accelerator for sparse matrix vector multiplication. In ISCAS, pages 121--124. IEEE, 2016.

[24]

Dimin Niu et al. Design of cross-point metal-oxide reram emphasizing reliability and cost. In ICCAD, pages 17--23. IEEE, 2013.

Digital Library

[25]

Ping Chi et al. Prime: A novel processing-in-memory architecture for neural network computation in reram-based main memory. In ISCA, pages 27--39. IEEE, 2016.

Digital Library

[26]

Jure Leskovec et al. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.

[27]

Haewoon Kwak et al. What is twitter, a social network or a news media? In WWW, pages 591--600. ACM, 2010.

Digital Library

[28]

Yahoo WebScope. Yahoo! altavista web page hyper-link connectivity graph, circa 2002. http://webscope.sandbox.yahoo.com/, 2012.

[29]

Xiangyu Dong et al. Nvsim: A circuit-level performance, energy, and area model for emerging non-volatile memory. In Emerging Memory Technologies, pages 15--50. Springer, 2014.

[30]

Lixue Xia et al. Mnsim: Simulation platform for memristor-based neuromorphic computing system. TCAD, 37(5):1009--1022, 2018.

[31]

Shimeng Yu et al. Investigating the switching dynamics and multilevel capability of bipolar metal oxide resistive switching memory. Applied Physics Letters, 98(10):103514, 2011.

[32]

Steven JE Wilton and Norman P Jouppi. Cacti: An enhanced cache access and cycle time model. JSSC, 31(5):677--688, 1996.

[33]

Boris Murmann. Adc performance survey 1997--2017. http://web.stanford.edu/~murmann/adcsurvey.html, August 2017.

Cited By

Lyu BWang SWen SShi KYang YZeng LHuang T(2024)AutoGMap: Learning to Map Large-Scale Sparse Graphs on Memristive CrossbarsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.326538335:9(12888-12898)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2023.3265383
Wang YWang WChang YTsai CKuo TWu CHo CHu H(2024)TCAM-GNN: A TCAM-Based Data Processing Strategy for GNN Over Sparse GraphsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2023.332800812:3(891-904)Online publication date: Jul-2024
https://doi.org/10.1109/TETC.2023.3328008
He YLi BWang YLiu CLi HLi X(2024)A Task-Adaptive In-Situ ReRAM Computing for Graph Convolutional NetworksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337525143:9(2635-2646)Online publication date: Sep-2024
https://doi.org/10.1109/TCAD.2024.3375251
Show More Cited By

Recommendations

On the Multichromatic Number of s-Stable Kneser Graphs

For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...
Forbidden Subgraphs and Weak Locally Connected Graphs

A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called $$N^i$$Ni-locally connected if $$G[\{ x\in V(G): 1\le d_G(w, x)\le i\}]$$G[{x?V(G):1≤dG(w,x)≤i}] is connected and $$N_2$$N2-locally connected if $$G[\{uv: \{uw, vw\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPDAC '19: Proceedings of the 24th Asia and South Pacific Design Automation Conference

January 2019

794 pages

ISBN:9781450360074

DOI:10.1145/3287624

General Chair:
Toshiyuki Shibuya
Fujitsu Laboratories

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

In-Cooperation

IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IEEE CAS
IEEE CEDA
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 January 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

the project of Science and Technology on Reliability Physics and Application Technology of Electronic Component Laboratory
National Key R&D Program of China
National Natural Science Foundation of China

Conference

ASPDAC '19

Sponsor:

SIGDA

ASPDAC '19: 24th Asia and South Pacific Design Automation Conference

January 21 - 24, 2019

Tokyo, Japan

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
660
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)2

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lyu BWang SWen SShi KYang YZeng LHuang T(2024)AutoGMap: Learning to Map Large-Scale Sparse Graphs on Memristive CrossbarsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.326538335:9(12888-12898)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2023.3265383
Wang YWang WChang YTsai CKuo TWu CHo CHu H(2024)TCAM-GNN: A TCAM-Based Data Processing Strategy for GNN Over Sparse GraphsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2023.332800812:3(891-904)Online publication date: Jul-2024
https://doi.org/10.1109/TETC.2023.3328008
He YLi BWang YLiu CLi HLi X(2024)A Task-Adaptive In-Situ ReRAM Computing for Graph Convolutional NetworksIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337525143:9(2635-2646)Online publication date: Sep-2024
https://doi.org/10.1109/TCAD.2024.3375251
Zheng LHu AWang QHuang YHuang HYao PXiong SLiao XJin H(2024)PhGraph: A High-Performance ReRAM-Based Accelerator for Hypergraph ApplicationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.334322843:5(1318-1331)Online publication date: May-2024
https://doi.org/10.1109/TCAD.2023.3343228
Zhang ZJiang JWang QMao ZJing N(2024) 3 A -ReRAM: Adaptive Activation Accumulation in ReRAM-Based CNN Accelerator IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.329796843:1(176-188)Online publication date: Jan-2024
https://doi.org/10.1109/TCAD.2023.3297968
Gao YWang TGong LWang CHu YYang YLiu ZLi XZhou X(2024)Enhancing Graph Random Walk Acceleration via Efficient Dataflow and Hybrid Memory ArchitectureIEEE Transactions on Computers10.1109/TC.2023.334767473:3(887-901)Online publication date: Mar-2024
https://doi.org/10.1109/TC.2023.3347674
Wei XDeng JWang XLi ZJiang NYue H(2024)CraftRGP: A Comprehensive Reliability Analysis Framework Towards ReRAM-Based Graph Processing2024 IEEE International Test Conference in Asia (ITC-Asia)10.1109/ITC-Asia62534.2024.10661337(1-6)Online publication date: 18-Aug-2024
https://doi.org/10.1109/ITC-Asia62534.2024.10661337
Zahedi MCusters GShahroodi TGaydadjiev GWong SHamdioui S(2023)SparseMEM: Energy-efficient Design for In-memory Sparse-based Graph Processing2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137303(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137303
Choudhury DKalyanaraman APande P(2023)GraphIte: Accelerating Iterative Graph Algorithms on ReRAM Architectures via Approximate Computing2023 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE56975.2023.10137001(1-6)Online publication date: Apr-2023
https://doi.org/10.23919/DATE56975.2023.10137001
Wei YWang XZhang SYang JJia XWang ZQu GZhao W(2023)IMGA: Efficient In-Memory Graph Convolution Network Aggregation With Data Flow OptimizationsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.328850942:12(4695-4705)Online publication date: Dec-2023
https://doi.org/10.1109/TCAD.2023.3288509
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten