Xing Cai

About

D-core decomposition (DCD) identifies groups of nodes with strong cohesion at different levels of granularity, supporting e.g. clustering and community detection in directed graphs. Given the inefficiency of computing DCD, the computational power of GPUs is an attractive target. However, existing algorithms are ill-suited due to their restrictive programming model, as well as memory constraints in the widely available consumer-level GPUs. In particular, we show that any trivial adaptation of peeling algorithms, state-of-the-art for DCD, suffers from workload imbalance, redundant operations, and repeated atomic operations. To address these challenges, we propose a novel dynamic strategy to balance the computation on nodes with varying vertex degree and an enumeration-based lightweight memor

Selected publications

• Scientific articles and book chapters
• Huang, Cheng; Langguth, Johannes; Cai, Xing; Mottin, Davide & Assent, Ira (2026). Geld: Load-balanced D-Core Decomposition for Consumer GPUs. Proceedings of the ACM on Management of Data (PACMMOD). 4(3), p. 1–26. doi: 10.1145/3802064. Full text in Research Archive Show summary D-core decomposition (DCD) identifies groups of nodes with strong cohesion at different levels of granularity, supporting e.g. clustering and community detection in directed graphs. Given the inefficiency of computing DCD, the computational power of GPUs is an attractive target. However, existing algorithms are ill-suited due to their restrictive programming model, as well as memory constraints in the widely available consumer-level GPUs. In particular, we show that any trivial adaptation of peeling algorithms, state-of-the-art for DCD, suffers from workload imbalance, redundant operations, and repeated atomic operations. To address these challenges, we propose a novel dynamic strategy to balance the computation on nodes with varying vertex degree and an enumeration-based lightweight memory footprint with greatly reduced thread contention. We conduct extensive experiments on 12 datasets showing that Geld achieves an average speedup of 31× over GPU peeling DCD, 6× over GPU H-Index DCD, 22× over the best existing parallel DCD algorithm with 33% memory efficiency, and 3 orders of magnitude over the best serial DCD algorithm.
• Sæternes, Erik Hide & Cai, Xing (2026). A control-theoretic approach to adaptive time stepping in reservoir simulations and its impacts on efficiency and robustness. Communications in nonlinear science & numerical simulation. ISSN 1007-5704. 158, p. 109828–109828. doi: 10.1016/j.cnsns.2026.109828. Full text in Research Archive Show summary Adaptive time stepping is a central feature of most simulators solving time-dependent differential equations. Ideally, the time-stepping procedure should contribute to efficient and robust simulations. In this work, we first present a general overview of the adaptive-time-stepping design problem which is expected to help guide researchers and practitioners in constructing time-stepping procedures for their specific applications. Next, we provide a synthesis of the theory related to a control-theoretic approach to adaptive time stepping, and explain how this may form some of the parts of an adaptive-time-stepping procedure by helping to propose time-step sizes and decide whether executed time steps should be accepted or rejected. We combine our design framework with the control-theoretic approach, and formulate adaptive-time-stepping algorithms for reservoir simulations; a little-investigated application area for control theory. When doing so, we construct controllers which use the relative change in pressure and saturation as a proxy for the temporal discretisation error to propose new time steps, with the goal of keeping the relative change close to a target value. We then apply this complete time-stepping algorithm to real-field black-oil reservoir models using the industry-standard reservoir simulator OPM Flow. The simulator and all the tested reservoir models are open-source. By testing various versions of the novel time-stepping algorithm in the context of reservoir simulations, we arrive at a preferred third-order controller which seems to work well for several models. Our experiments also reveal that the choice of time-stepping algorithm has a notable impact on the efficiency of the simulator, and we observe impactful differences in robustness.
• Krishnasamy, Ezhilmathi; Trotter, James David; Cai, Xing; Pleiter, Dirk; Kos, Leon & Saavedra, Laura [Show all 7 contributors for this article] (2026). Performance and Programmability of MPI+X Integration with CUDA, HIP, SYCL, OpenACC, and OpenMP Offloading for Supercomputing: A Case Study on Dense Matrix–Vector Multiplication. In Mohr, Bernd; Fukaya, Takeshi & Miki, Yohei (Ed.), Proceedings of Supercomputing Asia and International Conference on High Performance Computing in Asia Pacific Region Workshops (SCA/HPCAsia 2026 Workshops). Association for Computing Machinery (ACM). ISSN 9798400723285. p. 457–468. doi: 10.1145/3784828.3786264. Full text in Research Archive Show summary Dense matrix-vector multiplication is a fundamental operation widely used in various application areas, including deep learning, computer graphics, and numerical analysis. With the increasing prevalence of large, heterogeneous high-performance computing (HPC) systems equipped with multiple Graphical Processing Units (GPUs), it is crucial to analyze effective strategies for utilizing these accelerators to enhance the efficiency of numerical computation. This study thus centers on the intricacies of accelerating dense matrix-vector multiplication on multi-GPU systems. We explore the combination of the Message Passing Interface (MPI) with various programming models—collectively referred to as MPI + X—highlighting its potential for advancing capabilities in large HPC environments, particularly those aimed at exascale computing and beyond. Here, "X" encompasses a range of programming models compatible with MPI. Specifically, this study investigates Compute Unified Device Architecture (CUDA), HIP, SYCL, Open Accelerators (OpenACC), and Open Multi-Processing (OpenMP) Offloading programming models within the context of large heterogeneous systems, as all can be integrated with MPI. We conduct a thorough examination of parallel dense matrix-vector multiplication and provide a detailed performance analysis of these programming models on NVIDIA, AMD, and Intel GPUs, addressing scenarios involving both GPU-aware and non-GPU-aware MPI. Our findings are substantiated by openly available code, which is essential for validation and the progression of scientific research.
• Ha, Hoai Phuong; Cai, Xing & Nguyen, Tan (2025). CAC: An asynchronous non-blocking consistency model with bounded staleness for distributed machine learning. Future Generation Computer Systems. ISSN 0167-739X. 178, p. 108317–108317. doi: 10.1016/j.future.2025.108317. Full text in Research Archive Show summary Relaxed consistency models have been reported to significantly improve the performance of training machine learning (ML) models compared to strong consistency models. However, the existing relaxed consistency models for distributed ML either force fast workers to wait for stragglers (e.g., stale-synchronous models) or have no upper bound on data staleness (e.g., asynchronous models), thus negatively affecting the quality and performance of training ML models. We propose a new asynchronous non-blocking consistency model with bounded staleness for distributed ML that overcomes the drawbacks of blocking and unbounded staleness in previous relaxed consistency models. The new model, named Chained Asynchronous Consistency (CAC), guarantees an upper bound on data staleness in asynchronous computation without forcing fast workers to wait for slow workers. We theoretically prove that the Stochastic Gradient Descent (SGD) algorithm under CAC converges and the upper bound on the convergence expectation is independent of the number of workers. Based on the CAC model, we develop a new staleness-aware cacheable distributed object (CAC-object) for distributed ML where shared parameters are distributed among workers in a peer-to-peer manner. This approach avoids intermediate centralized storage, such as parameter servers, while maintaining simple one-sided communication (e.g., get and put). The CAC-object allows remote parameters to be cached and reused locally following a consistency model (e.g., CAC, stale-synchronous or asynchronous model). To demonstrate the applicability of the CAC-object in asynchronous distributed ML, we introduce a new asynchronous distributed matrix completion algorithm (CAC-MF) using the CAC-object. We develop the CAC-object and CAC-MF using UPC++, a Partitioned Global Address Space (PGAS) library for high-performance computing (HPC), and evaluate them in different execution scenarios (e.g., with and without stragglers and crash failures, different minibatch sizes) on HPC clusters. Our experimental results show that the CAC model scales with increasing workers, tolerates stragglers and crash failures, and achieves better convergence than stale-synchronous and asynchronous models. Particularly, in the case of halted stragglers, CAC’s Root Mean Square Error (RMSE) is up to 25 times less than the baseline models’ RMSE for the Netflix dataset, and 170 times less for the MovieLens dataset.
• Trotter, James David; Ekmekçibaşı, Sinan; Sağbili, Doğan; Langguth, Johannes; Cai, Xing & Unat, Didem (2025). CPU- and GPU-initiated Communication Strategies for Conjugate Gradient Methods on Large GPU Clusters. In Diachin, Lori; Schulz, Martin & Randles, Amanda (Ed.), SC '25: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery (ACM). ISSN 9798400714665. p. 298–315. doi: 10.1145/3712285.3759774. Full text in Research Archive Show summary The Conjugate Gradient (CG) method is a key building block in numerous applications, yet its low computational intensity and sensitivity to communication overhead make it difficult to scale efficiently on multi-GPU systems. In light of recent advances in multi-GPU communication technologies, we revisit CG parallelization for large-scale GPU clusters. This work presents scalable CG and pipelined CG solvers targeting NVIDIA and AMD GPUs, using GPU-aware MPI, NCCL/RCCL and NVSHMEM to implement both CPU- and GPU-initiated communication schemes. We also introduce a monolithic variant that offloads the entire CG loop to the GPU, enabling fully device-initiated execution via NVSHMEM. Optimizations across all variants reduce unnecessary data transfers and synchronization overheads; the GPU-initiated variant eliminates CPU involvement altogether. We benchmark our implementations on NVIDIA- and AMD-based supercomputers using SuiteSparse matrices and a real-world finite element application. By avoiding data transfers and synchronization bottlenecks, our single-GPU implementations achieve 8–14 % performance gains over state-of-the-art solvers. In strong scaling tests on over 1,000 GPUs, we outperform existing approaches by 5–15 %. While CPU-initiated variants remain favorable due to a lack of vendor supported device-side computational kernels and suboptimal NVSHMEM configurations at the clusters, the strong scaling properties of the GPU-initiated CG variant indicates that it will be highly competitive at even larger GPU counts and with further tuning.
• Langguth, Johannes; Trotter, James David & Cai, Xing (2025). Modelling Load Imbalance In Shared Memory Multicore Systems. In Pericàs, Miquel & Ellsworth, Danielle (Ed.), Proceedings of the SC '25 Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery (ACM). ISSN 9798400718717. p. 1433–1441. doi: 10.1145/3731599.3767707. Full text in Research Archive Show summary Memory bandwidth has become the primary limiting factor of performance in many modern HPC applications, and it poses a limit to scalability because the achievable memory bandwidth only grows linearly with a small number of CPU cores. When the number of cores concurrently using the memory system exceeds a threshold, the aggregate memory bandwidth quickly saturates. To estimate the time usage of a computation dominated by memory traffic, the mainstream strategy is to divide the expected total memory traffic volume by the maximum memory bandwidth. However, this implicitly assumes homogeneous memory traffic which is often not the case, leading to inaccurate time estimates by the mainstream strategy. In this paper, we present a new performance model that specifically targets inhomogeneity in per-core memory traffic. The new requires only three hardware parameters. Using several cases of uneven per-core memory traffic, we demonstrate its advantage over the mainstream strategy.
• Zhao, Max; Burchard, Luk Bjarne; Schroeder, Daniel Thilo; Langguth, Johannes & Cai, Xing (2024). iPuma: High-Performance Sequence Alignment on the Graphcore IPU. In Taufer, Michela; Hoefler, Torsten; Hammond, Jeff & Randles, Amanda (Ed.), ISC High Performance 2024 Research Paper Proceedings (39th International Conference). IEEE (Institute of Electrical and Electronics Engineers). ISSN 9783982633602. doi: 10.23919/ISC.2024.10528941. Full text in Research Archive Show summary String alignment algorithms are an essential tool for understanding DNA and protein sequences. They demand substantial computation in real-world applications, and are thus a prime target for hardware acceleration. However, GPUs struggle to provide sufficient acceleration. Meanwhile, the recent MIMD-capable AI accelerators such as the Graphcore Intelligence Processing Unit (IPU) have become technologically viable. In this paper we present iPuma, a new implementation of Smith-Waterman sequence alignment for the IPU, which offers generalized short and medium length, one-to-one, and many-to-many high-throughput alignments for both DNA and protein sequences. iPuma is integrated into two bioinformatics pipelines, MetaHipMer2 and PASTIS. On protein datasets, iPuma shows speedups of 2.7x and 1.6x over state-of-the-art GPU and CPU implementations, respectively. We test the scalability on up to 64 IPUs, attaining a peak scoring performance of 1763 GCUPS for protein and 1168 GCUPS for DNA sequences.
• Sæternes, Erik Hide; Thune, Andreas; Rustad, Alf Birger; Skeie, Tor & Cai, Xing (2024). Automated parameter tuning with accuracy control for efficient reservoir simulations. Journal of Computational Science. ISSN 1877-7503. 75. doi: 10.1016/j.jocs.2023.102205. Full text in Research Archive Show summary Computer simulations of complex physical processes typically require sophisticated numerical schemes that internally involve many parameters. Different choices of such internal numerical parameters may lead to considerably different levels of computational efficiency, some may even result in wrong simulation results. The task of finding an optimal set of the numerical parameters (e.g. for the purpose of minimising the simulation time), while ensuring an accepted level of numerical accuracy, is therefore extremely important but challenging. In this paper, we propose a new automated search algorithm that is based on constrained stochastic searches within the parameter space. This iterative search scheme is also equipped with an accuracy check, which adopts several complementary measures for quantifying the similarities between time series from different simulations, such that parameter choices that lead to insufficiently accurate results will be automatically rejected. As a concrete scenario of usage, we have applied the automated parameter search scheme to the open-source reservoir simulation framework OPM. An empirical study shows that a suitable design of the optimisation objective function, together with an appropriate choice of the number of trials per search iteration and the perturbation scale per trial, can produce fast and convergent improvements with respect to the optimisation objective. For example, for a set of 12 numerical parameters, 30 trials from five search iterations are sufficient for reducing the objective function by 30% for the open Norne black-oil reservoir model. The robustness of the automated search scheme is also demonstrated for two other open reservoir models. Moreover, it is found that the parameter values automatically identified for the Norne model can also greatly improve the simulation efficiency of another proprietary reservoir model that has drastically different scale, resolution and geological properties.