Jul 2026· ACM Transactions on Storage· 0 citations· 20 references
TL;DR
This paper introduces a novel chunk-based graph representation model, featuring classified and hierarchical vertex storage and chunk layout optimization, to improve I/O utilization and presents a latency-optimized access mechanism featuring user-space asynchronous I/O execution and hotness-aware chunk caching management to accelerate I/O and boost cache efficiency.
Abstract
Existing external graph processing systems struggle with low I/O efficiency, high computational overhead, and substantial development costs on modern NVMe SSDs, due to their reliance on complex loading and computing models that transform random I/Os into sequential access. While in-memory graph systems with general-purpose memory-storage caches (like OS page cache or TriCache) offer improved support for fine-grained I/Os and simplified programming, they often fail to leverage specific graph access patterns, resulting in suboptimal performance. This paper aims to enhance the I/O efficiency of large-scale graph processing on NVMe SSDs. We first introduce a novel chunk-based graph representation model, featuring classified and hierarchical vertex storage and chunk layout optimization, to improve I/O utilization. Additionally, we present a latency-optimized access mechanism featuring user-space asynchronous I/O execution and hotness-aware chunk caching management to accelerate I/O and boost cache efficiency. Our prototype, ChunkGraph, enables flexible graph algorithm implementation and efficient execution. Experiments demonstrate ChunkGraph significantly outperforms existing external graph systems and in-memory graph systems using general-purpose cache subsystems, delivering several-fold speedups on overall performance and superior I/O efficiency.
FAST is presented, a holistic framework that accelerates end-to-end TGNN training by jointly optimizing sampling, memory I/O, and computation and designs thread-efficient graph operators tailored to sparse temporal subgraphs, improving GPU cache locality and reducing the latency of aggregation and edge softmax.
Traditional graph processing systems are built on monolithic servers, which couple a fixed ratio of compute and memory resources but often result in resource under-utilization in data centers. Although the disaggregated memory (DM) architecture has emerged to address this inefficiency, we identify that existing graph processing systems on DM remain highly impractical. They rely on unscalable architectures that fail to scale beyond a single memory node and a single compute node, and they require compute-side caches that are orders of magnitude larger than conventional practice in DM. To this end, this paper presents DMG, the first practical graph processing system on DM, which demonstrates superior system scalability and cache efficiency while delivering high performance. To improve efficiency of graph retrieval on DM, DMG proposes a DM-friendly graph store with retrieval optimizations. To mitigate costly update propagation, DMG presents an adaptive update coordinator that coordinates compute and memory nodes to perform update propagation with low overhead. To enable fast and effective load balancing, DMG employs a two-stage workload manager that includes a coarse-grained initial partitioning and a fine-grained runtime re-scheduling. Experimental results substantiate that compared with the state-of-the-art DM-based graph processing system, DMG can elastically scale up both compute and memory resources, delivering up to 4.9X better performance and accommodating graphs with ever-increasing sizes; meanwhile, it effectively tames the compute-side cache demands by up to 18.9X, positioning itself as a DM-ready solution in practice.
Yizou Chen, Tsun-Yu Yang, Zhisheng Hu et al.· 0 citations
Thanks to notable performance and capacity advantages, NVMe SSDs promise an effective cache tier for alleviating the load pressure of back-end storage servers. Compared with DRAM, an NVMe SSD exhibits up to hundreds of times larger capacity but delivers two orders of magnitude smaller bandwidth per gigabyte. This paper reveals that these hardware characteristics challenge fundamental design goals of caches: (1) storing tons of objects in a large-capacity SSD easily induces severe, persistent fragmentation, resulting in low cache space utilization; (2) intensive front-end requests contend for limited SSD bandwidth, causing unpredictable cache lookup latency. To tackle these challenges, this paper presents Gemini. The core of Gemini is heat-informed, group-based object management with a hardware-assisted I/O prioritization mechanism. Specifically, we introduce a tree-based prediction model for agile object grouping and fast reaction to hotspot shift. It provides SSD-friendly, bulk object eviction with a zero-write, remapping-based migration mechanism. In addition, to ensure request performance, we propose a novel I/O model that mitigates bandwidth congestion and prioritizes their processing at the hardware layer. Evaluation results show that Gemini delivers up to 3.8<inline-formula><tex-math notation="LaTeX">${\boldsymbol{\times}}$</tex-math><alternatives><mml:math><mml:mrow><mml:mo mathvariant="bold">×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cai-ieq1-3711088.gif"/></alternatives></inline-formula> throughput improvement, 2<inline-formula><tex-math notation="LaTeX">${\boldsymbol{\times}}$</tex-math><alternatives><mml:math><mml:mrow><mml:mo mathvariant="bold">×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cai-ieq2-3711088.gif"/></alternatives></inline-formula> tail latency reduction, and 2.7<inline-formula><tex-math notation="LaTeX">${\boldsymbol{\times}}$</tex-math><alternatives><mml:math><mml:mrow><mml:mo mathvariant="bold">×</mml:mo></mml:mrow></mml:math><inline-graphic xlink:href="cai-ieq3-3711088.gif"/></alternatives></inline-formula> higher cache space utilization than state-of-the-art caches for both YCSB workloads and production applications.
Connected Components (CC) is a foundational primitive in graph analytics, yet scaling it to billion-edge graphs on GPUs remains challenging as real-world graphs exceed GPU capacity. A naïve solution to oversubscribe GPU memory is UVM. However, UVM triggers excessive page faults under the irregular access patterns, while out-of-GPU-memory frameworks either introduce significant preprocessing overhead or suffer from random-access I/O bottlenecks. We present ExCC, an external-memory CC algorithm that keeps the full graph in host-pinned RAM and streams edge batches to the GPU through a three-phase pipeline of union-find merging. ExCC achieves predictable sequential I/O behavior across all phases, demonstrating average speedups of 1.98x over UVM, 4.03x over Subway, and 2.81x over EMOGI on billion-scale graphs.
Prajjwal Nijhara, D. Banerjee· IEEE International Symposium...· 0 citations
Graph-based approximate nearest neighbor search (ANNS) is increasingly used in vector databases and retrieval-augmented generation services, but large vector indexes often exceed the memory capacity of a single GPU server. NVMe over Fabrics (NVMe-oF) provides an attractive storage-disaggregation substrate, yet existing remote storage paths are still largely CPU-centered: the CPU forms I/O requests, drives transport progress, and determines when GPU computation can resume. This organization is poorly matched to graph ANNS, where the next data access is discovered inside GPU graph traversal. This paper presents GORIO, a system study that extends GPU-centered local I/O to remote storage and specializes the resulting substrate for graph ANNS over NVMe-oF. GORIO keeps query evolution, page-miss generation, pending-query state, and resume decisions on the GPU, while the CPU acts only as an NVMe-oF transport and completion proxy. The design has two layers: a GPU-direct remote I/O path that turns local page-cache misses into split-phase remote operations, and ANNS-specific scheduling mechanisms that overlap graph traversal with remote page service. On a SIFT1M DiskANN-style graph workload over an RDMA NVMe-oF path, GORIO is 1.31X faster than the state-of-the-art remote-I/O reference path and 4.89X faster than the direct remote page-cache path. These results demonstrate a concrete GPU-centered remote I/O substrate for graph ANNS.
Gen Zhang, Wenhao Gu, Shang-Rong Huang et al.· 0 citations
Approximate nearest neighbor search (ANNS) on CPUs is increasingly constrained by candidate-vector movement and decoding rather than peak arithmetic throughput. Although the RISC-V Vector Extension (RVV) provides vector-length-agnostic execution and LMUL-based register grouping, generic low-precision decoding still incurs conversion overhead, while irregular graph traversal generates scattered accesses that degrade cache locality and memory-level parallelism. We present RVANNS, an RVV-oriented ANNS engine that jointly optimizes vector representation and graph locality. Its Mixed-Precision Multi-Layer Index (MPMI) represents each vector with a dense 8-bit affine base and sparse FP16/FP32 residuals, fusing reconstruction with distance accumulation and aligning widening with LMUL-sized register groups. ROrder co-locates likely co-visited graph nodes and sorts remapped adjacency lists, transforming scattered payload probes into denser, predominantly forward-moving address streams. Integrated into Milvus, RVANNS achieves 3.39x and 4.94x speedups over scalar execution on real 128-bit and 256-bit RVV processors, respectively. Under controlled HNSW configurations, it improves throughput by 2.27--2.76x over RVV SIMD+FP32 and by 1.18--1.59x over the corresponding AVX-512 and SVE baselines. On Cohere10M, it further delivers 1.82--2.27x higher QPS/W than the evaluated GPU baselines.
Chengying Huan, Yudong Liu, Jianguo Wang et al.· 0 citations
