GraphRC: Accelerating graph processing on dual-addressing memory with vertex merging

Wei Cheng, Chun Feng Wu, Yuan Hao Chang, Ing Chao Lin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450392174
DOIs
StatePublished - 30 Oct 2022
Event41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022 - San Diego, United States
Duration: 30 Oct 20224 Nov 2022

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
ISSN (Print)1092-3152

Conference

Conference41st IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2022
Country/TerritoryUnited States
CitySan Diego
Period30/10/224/11/22

Keywords

  • dual-addressing memory
  • graph processing
  • over-read
  • RC-NVM
  • utilization
  • vertex merging

Fingerprint

Dive into the research topics of 'GraphRC: Accelerating graph processing on dual-addressing memory with vertex merging'. Together they form a unique fingerprint.

Cite this