@inproceedings{61686652a3844fb7a6d8f90fbc51ce7b,
title = "GraphRC: Accelerating graph processing on dual-addressing memory with vertex merging",
abstract = "Architectural innovation in graph accelerators attracts research attention due to foreseeable inflation in data sizes and the irregular memory access pattern of graph algorithms. Conventional graph accelerators ignore the potential of Non-Volatile Memory (NVM) crossbar as a dual-addressing memory and treat it as a traditional single-addressing memory with higher density and better energy efficiency. In this work, we present GraphRC, a graph accelerator that leverages the power of dual-addressing memory by mapping in-edge/out-edge requests to column/row-oriented memory accesses. Although the capability of dual-addressing memory greatly improves the performance of graph processing, some memory accesses still suffer from low-utilization issues. Therefore, we propose a vertex merging (VM) method that improves cache block utilization rate by merging memory requests from consecutive vertices. VM reduces the execution time of all 6 graph algorithms on all 4 datasets by 24.24% on average. We then identify the data dependency inherent in a graph limits the usage of VM, and its effectiveness is bounded by the percentage of mergeable vertices. To overcome this limitation, we propose an aggressive vertex merging (AVM) method that outperforms VM by ignoring the data dependency inherent in a graph. AVM significantly reduces the execution time of ranking-based algorithms on all 4 datasets while preserving the correct ranking of the top 20 vertices.",
keywords = "dual-addressing memory, graph processing, over-read, RC-NVM, utilization, vertex merging",
author = "Wei Cheng and Wu, {Chun Feng} and Chang, {Yuan Hao} and Lin, {Ing Chao}",
note = "Publisher Copyright: {\textcopyright} 2022 Association for Computing Machinery.; 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022 ; Conference date: 30-10-2022 Through 04-11-2022",
year = "2022",
month = oct,
day = "30",
doi = "10.1145/3508352.3549408",
language = "English",
series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022",
address = "美國",
}