Abstract
Graph algorithms such as breadth-first search (BFS) have been gaining ever-increasing importance in the era of Big Data. However, the memory bandwidth remains the key performance bottleneck for graph processing. To address this problem, we utilize processing-in-memory (PIM), combined with non-volatile metal-oxide resistive random access memory (ReRAM), to improve the performance of both computation and I/O. The idea is to integrate the computation logic into the memory in which the data accesses are located. We propose and implement a new ReRAM-based processing-in-memory architecture called RPBFS, in which graphs can be processed and persistently stored. We also design an efficient graph traversal scheme. Benefited from low data movement overhead and bank-level parallel computation, RPBFS shows a significant performance improvement compared with both the CPU-based and GPU-based BFS implementations. On a suite of real world graphs, our architecture yields up to 33.8× speedup.
Original language | English |
---|---|
Title of host publication | NVMSA 2017 - 6th IEEE Non-Volatile Memory Systems and Applications Symposium |
Publisher | IEEE |
ISBN (Electronic) | 9781538617687 |
DOIs | |
Publication status | Published - 10 Oct 2017 |
Event | 6th IEEE Non-Volatile Memory Systems and Applications Symposium, NVMSA 2017 - Hsinchu, Taiwan Duration: 16 Aug 2017 → 18 Aug 2017 |
Conference
Conference | 6th IEEE Non-Volatile Memory Systems and Applications Symposium, NVMSA 2017 |
---|---|
Country/Territory | Taiwan |
City | Hsinchu |
Period | 16/08/17 → 18/08/17 |
ASJC Scopus subject areas
- Hardware and Architecture