NPGraph: An Efficient Graph Computing Model in NUMA-Based Persistent Memory Systems

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%.