A novel ReRAM-based processing-in-memory architecture for graph traversal

Lei Han, Zhaoyan Shen, L. I.U. Duo, Zili Shao, H. Howie Huang, L. I. Tao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

11 Citations (Scopus)

Abstract

Graph algorithms such as graph traversal have been gaining ever-increasing importance in the era of big data. However, graph processing on traditional architectures issues many random and irregular memory accesses, leading to a huge number of data movements and the consumption of very large amounts of energy. To minimize the waste of memory bandwidth, we investigate utilizing processing-in-memory (PIM), combined with non-volatile metal-oxide resistive random access memory (ReRAM), to improve both computation and I/O performance. We propose a new ReRAM-based processing-in-memory architecture called RPBFS, in which graph data can be persistently stored and processed in place. We study the problem of graph traversal, and we design an efficient graph traversal algorithm in RPBFS. Benefiting from low data movement overhead and high bank-level parallel computation, RPBFS shows a significant performance improvement compared with both the CPU-based and the GPU-based BFS implementations. On a suite of real-world graphs, our architecture yields a speedup in graph traversal performance of up to 33.8×, and achieves a reduction in energy over conventional systems of up to 142.8×.

Original languageEnglish
Article number9
JournalACM Transactions on Storage
Volume14
Issue number1
DOIs
Publication statusPublished - 1 Feb 2018

Keywords

  • Architecture
  • BFS
  • Processing-in-memory
  • ReRAM

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this