Gram: Graph Processing in a ReRAM-based Computational Memory

Minxuan Zhou; Mohsen Imani; Saransh Gupta; Yeseong Kim; Tajana Rosing

doi:10.1145/3287624.3287711

Gram: Graph Processing in a ReRAM-based Computational Memory

Minxuan Zhou
, Mohsen Imani
, Saransh Gupta
, Yeseong Kim
, Tajana Rosing

Department of Electrical Engineering and Computer Science

University of California at San Diego

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

23 Scopus citations

Abstract

The performance of graph processing for real-world graphs is limited by inefficient memory behaviours in traditional systems because of random memory access patterns. Offloading computations to the memory is a promising strategy to overcome such challenges. In this paper, we exploit the resistive memory (ReRAM) based processing-in-memory (PIM) technology to accelerate graph applications. The proposed solution, GRAM, can efficiently executes vertex-centric model, which is widely used in large-scale parallel graph processing programs, in the computational memory. The hardware-software co-design used in GRAM maximizes the computation parallelism while minimizing the number of data movements. Based on our experiments with three important graph kernels on seven real-world graphs, GRAM provides 122.5× and 11.1× speedup compared with an in-memory graph system and optimized multi-threading algorithms running on a multi-core CPU. Compared to a GPU-based graph acceleration library and a recently proposed PIM accelerator, GRAM improves the performance by 7.1× and 3.8× respectively.

Original language	English
Title of host publication	ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	347-351
Number of pages	5
ISBN (Electronic)	9781450360074
DOIs	https://doi.org/10.1145/3287624.3287711
State	Published - 21 Jan 2019
Event	24th Asia and South Pacific Design Automation Conference, ASPDAC 2019 - Tokyo, Japan Duration: 21 Jan 2019 → 24 Jan 2019

Publication series

Name	Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Conference

Conference	24th Asia and South Pacific Design Automation Conference, ASPDAC 2019
Country/Territory	Japan
City	Tokyo
Period	21/01/19 → 24/01/19

Bibliographical note

Publisher Copyright:
© 2019 Association for Computing Machinery.

Access to Document

10.1145/3287624.3287711

Cite this

Zhou, M., Imani, M., Gupta, S., Kim, Y., & Rosing, T. (2019). Gram: Graph Processing in a ReRAM-based Computational Memory. In ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference (pp. 347-351). (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/3287624.3287711

@inproceedings{fc28999179544d89bfcbff22de9370bd,

title = "Gram: Graph Processing in a ReRAM-based Computational Memory",

abstract = "The performance of graph processing for real-world graphs is limited by inefficient memory behaviours in traditional systems because of random memory access patterns. Offloading computations to the memory is a promising strategy to overcome such challenges. In this paper, we exploit the resistive memory (ReRAM) based processing-in-memory (PIM) technology to accelerate graph applications. The proposed solution, GRAM, can efficiently executes vertex-centric model, which is widely used in large-scale parallel graph processing programs, in the computational memory. The hardware-software co-design used in GRAM maximizes the computation parallelism while minimizing the number of data movements. Based on our experiments with three important graph kernels on seven real-world graphs, GRAM provides 122.5× and 11.1× speedup compared with an in-memory graph system and optimized multi-threading algorithms running on a multi-core CPU. Compared to a GPU-based graph acceleration library and a recently proposed PIM accelerator, GRAM improves the performance by 7.1× and 3.8× respectively.",

author = "Minxuan Zhou and Mohsen Imani and Saransh Gupta and Yeseong Kim and Tajana Rosing",

note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 24th Asia and South Pacific Design Automation Conference, ASPDAC 2019 ; Conference date: 21-01-2019 Through 24-01-2019",

year = "2019",

month = jan,

day = "21",

doi = "10.1145/3287624.3287711",

language = "English",

series = "Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "347--351",

booktitle = "ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference",

}

Zhou, M, Imani, M, Gupta, S, Kim, Y & Rosing, T 2019, Gram: Graph Processing in a ReRAM-based Computational Memory. in ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference. Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC, Institute of Electrical and Electronics Engineers Inc., pp. 347-351, 24th Asia and South Pacific Design Automation Conference, ASPDAC 2019, Tokyo, Japan, 21/01/19. https://doi.org/10.1145/3287624.3287711

Gram: Graph Processing in a ReRAM-based Computational Memory. / Zhou, Minxuan; Imani, Mohsen; Gupta, Saransh et al.
ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference. Institute of Electrical and Electronics Engineers Inc., 2019. p. 347-351 (Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Gram

T2 - 24th Asia and South Pacific Design Automation Conference, ASPDAC 2019

AU - Zhou, Minxuan

AU - Imani, Mohsen

AU - Gupta, Saransh

AU - Kim, Yeseong

AU - Rosing, Tajana

PY - 2019/1/21

Y1 - 2019/1/21

N2 - The performance of graph processing for real-world graphs is limited by inefficient memory behaviours in traditional systems because of random memory access patterns. Offloading computations to the memory is a promising strategy to overcome such challenges. In this paper, we exploit the resistive memory (ReRAM) based processing-in-memory (PIM) technology to accelerate graph applications. The proposed solution, GRAM, can efficiently executes vertex-centric model, which is widely used in large-scale parallel graph processing programs, in the computational memory. The hardware-software co-design used in GRAM maximizes the computation parallelism while minimizing the number of data movements. Based on our experiments with three important graph kernels on seven real-world graphs, GRAM provides 122.5× and 11.1× speedup compared with an in-memory graph system and optimized multi-threading algorithms running on a multi-core CPU. Compared to a GPU-based graph acceleration library and a recently proposed PIM accelerator, GRAM improves the performance by 7.1× and 3.8× respectively.

AB - The performance of graph processing for real-world graphs is limited by inefficient memory behaviours in traditional systems because of random memory access patterns. Offloading computations to the memory is a promising strategy to overcome such challenges. In this paper, we exploit the resistive memory (ReRAM) based processing-in-memory (PIM) technology to accelerate graph applications. The proposed solution, GRAM, can efficiently executes vertex-centric model, which is widely used in large-scale parallel graph processing programs, in the computational memory. The hardware-software co-design used in GRAM maximizes the computation parallelism while minimizing the number of data movements. Based on our experiments with three important graph kernels on seven real-world graphs, GRAM provides 122.5× and 11.1× speedup compared with an in-memory graph system and optimized multi-threading algorithms running on a multi-core CPU. Compared to a GPU-based graph acceleration library and a recently proposed PIM accelerator, GRAM improves the performance by 7.1× and 3.8× respectively.

UR - https://www.scopus.com/pages/publications/85061117017

U2 - 10.1145/3287624.3287711

DO - 10.1145/3287624.3287711

M3 - Conference contribution

AN - SCOPUS:85061117017

T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

SP - 347

EP - 351

BT - ASP-DAC 2019 - 24th Asia and South Pacific Design Automation Conference

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 21 January 2019 through 24 January 2019

ER -

Gram: Graph Processing in a ReRAM-based Computational Memory

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this