Jul 2026· International Conference on Supercomputing· pp. 699-713· 0 citations· 38 references
Computer Science
TL;DR
The results show that cuMIS outperforms ECL-MIS and MG-MIS—the state-of-the-art single-GPU and multi-GPU baselines—achieving speedups of up to 6.5 × and 156 × , respectively, while maintaining comparable or superior solution quality.
Abstract
This paper addresses the problem of computing a maximal independent set (MIS), defined as a set of vertices where no two vertices are connected by an edge and no additional vertex can be added without violating the independence property. While several GPU-accelerated algorithms exist to find the MIS efficiently, the problem remains challenging for graphs exceeding the memory of a single GPU. In this paper, we present cuMIS, a unified scalable framework for computing MIS on single-GPU, multi-GPU, and distributed multi-node configurations. cuMIS employs a data-driven approach that processes only an active set of undecided vertices for reduced memory access and a degree-aware workload distribution that mitigates imbalance and thread divergence. Our results show that cuMIS outperforms ECL-MIS and MG-MIS—the state-of-the-art single-GPU and multi-GPU baselines—achieving speedups of up to 6.5 × and 156 × , respectively, while maintaining comparable or superior solution quality. Finally, we demonstrate that cuMIS scales effectively to process trillion-edge graphs in distributed multi-node environments where existing approaches fail to operate.
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
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
Cohesive subgraph mining is a fundamental task in graph data analytics. We re-visit the problem of listing all minimal $k$-cores, where a $k$-core is a subgraph in which every vertex has degree at least $k$, and minimality requires that no proper subset remains a $k$-core. Existing methods are computationally prohibitive due to explosive branching and costly branch state update, leading to the trivial worst-case bound $O^{*}\left(2^{n}\right)$ for the basic branch-and-bound baseline wh, where $O^{*}$ suppresses polynomial factors and $n$ is the number of vertices. In this paper, we present an improved method IMinC based on three key ideas: (i) a principled branching state with lineartime update; (ii) a pivot strategy that guides branching toward promising vertices; and (iii) a divide-and-conquer framework that initializes each subproblem to enable our pivot strategy throughout and reduce recursion depth. We further introduce three reduction rules that aggressively prune infeasible branches. Together, these components yield the worst-case time complexity of $O^{*}\left(\alpha_{\ell}^{n}\right)$, where $\alpha_{\ell}$ is a positive number strictly smaller than 2. We also extend IMinC to list minimal $k$-cores under a size bound, addressing practical needs such as size-bounded community search. Extensive experiments on 12 real-world graphs demonstrate that IMinC outperforms the baselines by up to 2 order of magnitude, delivering substantial gains in efficiency.
Yukai Sun, Kaiqiang Yu, Shengxin Liu et al.· IEEE International Conferenc...· 0 citations
Graph coloring at scale on GPUs forces a quality–performance trade-off: strict priority orderings such as Smallest-Last (SL) reduce the number of colors but serialize the priority-allocation (PA) phase and throttle parallelism, leaving the high-quality, GPU-fast region of the coloring-quality versus execution-time plane historically empty. Our prior conference framework, CHROMA, populated this region with cuSL—the first GPU-parallel realization of SL priority allocation—plus three quality/runtime optimizations, a learned predictor for its elastic parameter, and a partitioner-agnostic module for graph exceeding single-GPU memory capacity. For single GPU configuration, CHROMA achieves up to a <inline-formula> <tex-math notation="LaTeX">$17.4\times $ </tex-math></inline-formula> geometric-mean PA speedup over a parallel CPU baseline at comparable quality. In this paper, we propose CHROMAv2 that pushes CHROMA further along this Pareto frontier with three contributions: Adaptive Workload-balance Decrement (AWD), a per-iteration warp-/CTA-centric dispatch that removes the residual decrement imbalance of static policies; an aggressive elastic-parameter prediction (AEP) family that enlarges the elastic parameter’s range without color quality degradation; and an online bumping controller that widens peeling granularity through PA’s long tail. AWD alone delivers a 1.18–<inline-formula> <tex-math notation="LaTeX">$1.28\times $ </tex-math></inline-formula> geometric-mean PA speedup (1.13–<inline-formula> <tex-math notation="LaTeX">$1.17\times $ </tex-math></inline-formula> end-to-end), online bumping improves large-graph runtime by up to 54% without sacrificing coloring quality, and CHROMAv2 overall attains up to a <inline-formula> <tex-math notation="LaTeX">$1.68\times $ </tex-math></inline-formula> geometric-mean single-GPU speedup compared with our previous version. We open-source CHROMA to facilitate future research.
This work presents SAGA, a high-performance framework for real-time combinatorial optimization on dynamic graphs that adopts a state-aware execution model in which each vertex maintains compact local state, enabling incremental and localized updates in response to graph changes.
Rohit Prajapati, Prajjwal Nijhara, D. Banerjee· IEEE International Symposium...· 0 citations
Two independent families of parallel algorithms exist for hypergraph k-core decomposition—the HK codebase (OpenMP, vertex-centric) and HyperCD (ParlayLib, edge-centric with frontier scheduling). Yet work that systematically compares them at the level of individual optimization flags is surprisingly scarce. We constructed 10 new HK variants by toggling 7 compile-time preprocessor flags, benchmarked them alongside 5 HyperCD variants on 7 real-world datasets (489 timed runs at 32 threads), and probed which optimizations actually drive the performance gap. The first seven constructed variants improve on the official baseline by 21% through per-dataset routing, with three cross-pollinated variants adding another 7%. The strongest HK variants sit at an Amdahl’s Law ceiling—their parallel efficiency is lower than the naive baseline. A scalability analysis across 2–32 threads confirms that HK scales with thread count (3.1×–6.2×) while HyperCD does not (∼1.0×). Adding HyperCD through a size-based routing rule yields a combined 1.46× cumulative speedup, from 27.05 s down to 18.63 s, with all results verified byte-for-byte against golden baselines.
Yun-Ze Jiang· 2026 8th International Confe...· 0 citations