Research Article
NPGraph: An Efficient Graph Computing Model in NUMA-Based Persistent Memory Systems
@INPROCEEDINGS{10.1007/978-3-031-54528-3_12, author={Baoke Li and Cong Cao and Fangfang Yuan and Yuling Yang and Majing Su and Yanbing Liu and Jianhui Fu}, title={NPGraph: An Efficient Graph Computing Model in NUMA-Based Persistent Memory Systems}, proceedings={Collaborative Computing: Networking, Applications and Worksharing. 19th EAI International Conference, CollaborateCom 2023, Corfu Island, Greece, October 4-6, 2023, Proceedings, Part II}, proceedings_a={COLLABORATECOM PART 2}, year={2024}, month={2}, keywords={Graph computing Adaptive updating strategy Data-driven algorithms Hybrid memory NUMA}, doi={10.1007/978-3-031-54528-3_12} }- Baoke Li
Cong Cao
Fangfang Yuan
Yuling Yang
Majing Su
Yanbing Liu
Jianhui Fu
Year: 2024
NPGraph: An Efficient Graph Computing Model in NUMA-Based Persistent Memory Systems
COLLABORATECOM PART 2
Springer
DOI: 10.1007/978-3-031-54528-3_12
Abstract
The massive volume and the inherent imbalance of graphs are inevitable challenges for efficient graph computing, primarily due to the limited capacity of main memory (DRAM). Fortunately, a promising solution has emerged in the form of hybrid memory systems (HMS) which combine DRAM and persistent memory (PMEM) to enable data-centric graph computing. However, directly transitioning existing DRAM-based models to HMS can lead to inefficiency issues, especially when crossing Non-Uniform Memory Access (NUMA) nodes. In this paper, we present NPGraph, a novel approach that fully exploits the advantages of HMS for in-memory graph computing models. The main contributions of NPGraph lie in three aspects. Firstly, a dual-block graph representation strategy is devised to accelerate the process of subgraph construction. By utilizing data layering, it fully utilizes the storage architecture of HMS and optimizes the data access process. Secondly, an adaptive push-pull update strategy is proposed to optimize the message-updating process. With data-driven algorithms, it dynamically migrates subgraphs which are used in future iterations. Thirdly, the effectiveness of NPGraph is evaluated on five public graph data sets. Our model can improve the temporal locality and the spatial locality of graph computing concurrently. Extensive evaluation results show that NPGraph outperforms state-of-the-art graph computing models by 21.67%–32.03%.
