About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
Collaborative Computing: Networking, Applications and Worksharing. 19th EAI International Conference, CollaborateCom 2023, Corfu Island, Greece, October 4-6, 2023, Proceedings, Part II

Research Article

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

Cite
BibTeX Plain Text
  • @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
Baoke Li1, Cong Cao1, Fangfang Yuan1, Yuling Yang1, Majing Su, Yanbing Liu1,*, Jianhui Fu
  • 1: Institute of Information Engineering, Chinese Academy of Sciences
*Contact email: liuyanbing@iie.ac.cn

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

Keywords
Graph computing Adaptive updating strategy Data-driven algorithms Hybrid memory NUMA
Published
2024-02-23
Appears in
SpringerLink
http://dx.doi.org/10.1007/978-3-031-54528-3_12
Copyright © 2023–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL