CS Paper Radar

Accelerating Direct Sparse Solvers with Graph Computing Accelerators

Jiya Su, François-Henry Rouet, Jeff Beisheim, Robert Lucas, Yuqing Wang, Alexander Fell, Chris Mccarthy, David F. Gleich, Andrew A Chien

cs.DC ·submitted 2026-11-09 04:53 UTC · v1

Abstract

Solving large sparse linear systems by Gaussian elimination is a challenging computational task due to the introduction of non-zero elements, or fill-in. Practitioners use heuristics such as the nested dissection reordering algorithm to try to reduce fill-in. In practice, reordering codes do not achieve the same parallel scaling as factorization, nor can they exploit AVX instructions or GPUs. Thus, reordering can be the primary runtime bottleneck in large-scale computer-aided engineering applications. We consider the use of a novel accelerator, the UpDown system, to accelerate the METIS multilevel nested dissection reordering algorithm. The UpDown system is designed for a broad class of graph computing and irregular algorithms. We report results for small-scale UpDown systems that will be available commercially in 2027, using validated simulation and FPGA emulation platforms. Our findings indicate that small UpDown systems can speed up METIS by two-orders of magnitude versus a single CPU. Compared to ParMETIS on hundreds of MPI ranks, we anticipate the same small UpDown systems offer speedups of 4 - 7, providing the potential to significantly speed finite element simulations

Closest papers

Nearest neighbours by meaning across the whole index.

Helix: A Unified Programmable Accelerator for Diverse Krylov Subspace Solvers

cs.AR cs.DC ·2026-10-15 ·Wei Chen, Yizhi Yuan, Linghao Song
similarity 0.69
Abstract

Domain-specific accelerators deliver high performance and energy efficiency through specialization but often lack support for extensible algorithm families. Existing FPGA accelerators for Krylov subspace methods, which iteratively solve sparse linear systems, typically support a single solver or require separate hardware configurations. Helix follows a systematic algorithm-family design methodology that first abstracts common computational primitives from diverse Krylov solvers and builds the architecture around efficient, programmable primitive kernels. Helix then introduces programmable datapaths to coordinate these primitives. Its architecture decouples hardware implementation from solver-specific execution, enabling HBM reuse and zero solver-switching latency. Finally, Helix provides a DSL compiler that efficiently maps different solvers onto the architecture while optimizing vector-operation performance for each solver. We prototype Helix on a Xilinx Alveo U55C FPGA and evaluate Helix's practicality and performance by using it to compile and execute eight solvers. Helix achieves up to 7.91x and 1.16x speedups over Xilinx XcgSolver and the state-of-the-art FPGA accelerator Callipepla, respectively, both of which support only JPCG. Across the eight solvers, Helix sustains 47.5% - 96.9% of the throughput of an NVIDIA RTX PRO 6000 GPU while delivering 2.29x - 4.66x higher energy efficiency and 1.89x - 3.85x higher throughput per unit peak memory bandwidth. The programmable components incur 0.25% - 0.57% execution-time overhead and 4.7% LUT and 4.0% FF overhead, demonstrating negligible overhead for programmability.

0.34

Accelerating Branch MPC with Two-Level Parallel Direct Solves on GPUs

eess.SY math.OC ·2026-09-24 ·Fenglong Song, Luyao Zhang, Liang Wu, Ján Drgoňa, Colin N. Jones
similarity 0.66
Abstract

Branch model predictive control optimizes multiple future trajectories coupled through shared decisions, with computational demands increasing as the number of scenarios and prediction horizon grow. We present a GPU-accelerated direct linear solver for branch MPC formulations in which all trajectories share a single root decision node and evolve independently thereafter. By operating at the linear-algebra level, the solver provides a reusable backend for multiple optimization algorithms whose reduced systems have the required symmetric positive-definite structure. The solver exploits two levels of parallelism: across scenarios and along each prediction horizon. A tailored variable ordering enables horizon-parallel Cholesky factorization while preserving a single root-tail coupling block per scenario in the factor. Numerical experiments demonstrate substantial speedups over state-of-the-art sparse direct solvers, achieving factorization speedups of up to 6.0$\times$ over cuDSS and 27.6$\times$ over eight-thread PARDISO, with triangular solve speedups of up to 3.5$\times$ and 15.8$\times$, respectively.

0.16

Accelerating the Solving of Many Tiny General Linear Systems on GPUs: Application to Constitutive Laws

cs.DC ·2026-09-14 ·Tristan Chenaille, Francesca Cuteri, Rapha{ë}l Prat, Guillaume Latu, Thomas Helfer
code/data similarity 0.66
Abstract

Many applications require solving large numbers of independent linear systems on GPUs. While this need is well addressed for small to large systems, tiny ones, understood here as systems of dimension below 32, remain challenging. This is especially relevant in constitutive law evaluation, where millions of integration points are handled independently, and where each constitutive update generally relies on a Newton iterative method. Each iteration then requires the double-precision solution of a tiny general square linear system using LU factorization with partial pivoting (LUpp). The present study was conducted within a closed-source prototype, which serves as a demonstrator for porting to NVIDIA GPUs constitutive law evaluations currently provided on CPUs by TFEL/MFront, an open-source code generation tool for material knowledge. We compare several double-precision LUpp solvers, including implementations from GPU linear algebra libraries as well as custom-designed CUDA kernels. The comparison is performed first on large batches of standalone linear systems, and then within the full constitutive-law evaluation workflow, where each integration point requires a sequence of distinct linear systems, one per iteration of its own Newton loop. The study shows that the best LUpp solving strategy strongly depends on several factors including system size and application context. We discuss several key aspects, including register pressure, occupancy, the ability to invoke the LUpp solver directly from device code, and whether assigning several threads to each system is the most efficient strategy. Experiments on an NVIDIA H100 GPU show that the specialized LUpp solvers proposed in this work can outperform existing state-of-the-art approaches for this class of workloads, with speedups of up to 6.5x over cuSolverDx, and up to 17.7x over MAGMA.

0.19

Distributed Linear Programming on GPU Clusters at Extreme Scale

cs.DC math.OC ·2026-09-08 ·Arnaud Deza, Santanu S. Dey, Pascal Van Hentenryck
publishedbenchmarkcode/data similarity 0.64
Abstract · 21 pages, 5 figures. Accepted at the 18th Annual Workshop on Optimization for Machine Learning (OPT 2026), NeurIPS 2026

Large linear programs can exceed the memory of a single compute node. Although first-order methods replace sparse factorizations with GPU-suited matrix-vector products, other solver phases can reintroduce a single-node memory limit. We present SHARDLP, a distributed GPU LP solver that keeps the matrix and primal-dual state partitioned from sharded input through solution output. On the Google PDLP benchmark, SHARDLP solves ten of eleven instances, compared with eight in the published CPU PDLP study. On the largest benchmark, eight H200 GPUs solve a 1.185-billion-variable, 6.338-billion-nonzero LP in 9.9 minutes; the published CPU experiment reports 21.06 hours on different hardware. Beyond this benchmark, separately checked multi-node solves reach up to 13.604 billion variables and 40.807 billion nonzeros, while validated executions span up to 76 GPUs across 29 compute nodes. For column-partitioned solves, support-aware communication skips GPUs that store no coefficients for a row; on an LP with 2.76 billion nonzeros, it cuts modelled communication by 92.97% and improves solver time by 1.27x-1.52x. The code for SHARDLP is available at https://github.com/ArnaudDeza/ShardLP.

0.76

Exploring spectral element methods on the Tenstorrent RISC-V accelerator

cs.DC ·2026-08-24 ·Daniyal Arshad, Nick Brown
similarity 0.63
Abstract · Author accepted version of paper to RISC-V for HPC International Workshop at ISC26

The growing availability of commodity RISC-V hardware has sparked interest in its use for High Performance Computing (HPC), with PCIe accelerator cards offering a practical near-term pathway to adoption. The Tenstorrent Wormhole is one example, with dedicated vector and matrix units across 128 Tensix cores, and is widely available. In this paper, we explore porting the AX kernel of Nekbone, a widely used HPC mini-application derived from the Gordon Bell Prize-winning Nek5000 spectral element solver, onto the Wormhole accelerator. This kernel evaluates the Poisson operator, and we describe the mapping of the algorithm onto the Tensix. The initial performance results reveal that the host-side data transposition, required for the z-direction gradient computation, is a severe bottleneck. Consequently, we investigated two optimisation strategies that yield dramatic improvements, achieving 242.97 GFLOPS for 100000 elements across 128 Tensix cores, outperforming a 24-core Xeon Platinum CPU and drawing approximately 7 times less power.

0.54

Multilevel Graph Partitioning on GPU Supercomputers

cs.DC ·2026-11-18 ·Michael S. Gilbert, Erik G. Boman, Kamesh Madduri
published similarity 0.63
Abstract · To appear in the proceedings of HiPC 2026

Graph partitioning is a key enabler in computational science, with applications to sparse linear algebra, load-balanced parallel computation, and graph computations. In recent years, graphics processing units (GPUs) have become the preferred accelerator on the world's top supercomputers. Despite this, most existing distributed graph partitioners do not utilize GPUs. In this work, we develop a new multi-GPU distributed partitioner based on Jet, a prior single-GPU partitioner. We seek to optimize scalability without sacrificing quality. Our partitioner utilizes CUDA-aware MPI, one-sided communication routines, and an overall bulk-synchronous parallel structure. We demonstrate solution quality comparable to Jet. Our experiments show excellent weak scaling up to 256 GPUs, enabling partitioning of instances significantly larger than a single-GPU partitioner can handle.

0.23

Ascend-SpMM: Accelerating Sparse Matrix-Dense Matrix Multiplication on Ascend NPUs

cs.DC cs.DB ·2026-11-01 ·Jiahe Wang, Yingxia Shao, Shuhan Wang, Qingbo Ge, Hongzheng Li +1 more
code/data similarity 0.63
Abstract

Sparse Matrix-Dense Matrix Multiplication (SpMM) is a fundamental kernel in graph neural networks and scientific computing, yet its optimization on Ascend NPUs remains largely unexplored. The physically decoupled Cube/Vector architecture and single-threaded scalar instruction dispatch of modern NPUs introduce unique challenges. We present Ascend-SpMM, a novel and systematic framework tailored to the physically decoupled architecture of Ascend NPUs.We introduce a memory-centric cost model that quantifies hardware affinity and guides a conflict-bounded, densityaware task-mapping strategy. The strategy maps dense regions to the high-throughput Cube path and sparse residuals to the flexible Vector path, with a theoretical bound on cross-processor conflicts. To execute these workloads with high efficiency, we further develop highly customized sub-kernels. These kernels leverage hierarchy-aware pipelining and round-robin ring buffer-based implicit synchronization to effectively mask memory latency and reduce instruction pipeline stalls. Extensive experiments demonstrate that Ascend-SpMM achieves a geometric-mean speedup of 12.70-20.55X over the strongest evaluated NPU baseline for each matrix, accelerates end-to-end GNN training by up to 6.8X, and delivers performance competitive with state-of-the-art GPU implementations. The source code of Ascend-SpMM is publicly available at https://github.com/IDMG-Lab/Ascend-SpMM.

0.32

How the Dirty Set Moves: Characterizing Schedule Reuse in Incremental Sparse Matrix Multiplication

cs.PF cs.DCcs.MS ·2026-10-14 ·Hunter Horne, Eric Spencer, Alex Henningfield, Arslan Bisharat
similarity 0.63
Abstract · 12 pages, 7 figures, 8 tables

Sparse matrices, in which most entries are zero, are central to scientific simulation, graph analytics and machine learning, and their multiplication with dense inputs is a core parallel kernel. In many applications the matrix stays fixed while only a few input rows change per step, so the result can be updated from those rows alone, which we call the dirty set. Sparse kernels often add a second optimization based on the inspector-executor principle, in which a tiled schedule is prepared once and reused across calls. However, when this reuse remains profitable as the dirty set moves is not well characterized. In this paper, we show that retained tiled execution rarely beats direct CSC in incremental sparse matrix multiplication, although incremental execution itself remains highly profitable. Across 21 SuiteSparse matrices and controlled patterns of motion, a direct column-wise incremental update is 2.1-8.2x faster than the best of eight full-recomputation codes, among them Intel oneMKL and PyTorch. Yet the same direct update outperforms a tiled executor that retains tile preparation and caches assembled schedules in 779 of 837 workloads. Separating reuse into per-tile preparation and cached schedules shows that the benefit comes from preparation; extra cache capacity seldom helps because a tile set rarely returns after a different one has intervened. Tiling is faster only when tiles merge many entries into each output write, a structural property that we predicted before measurement and confirmed on four held-out matrices of the same family. These results show that the structure of the matrix and the motion of the dirty set, rather than the sophistication of the schedule, determine whether reuse is profitable. We anticipate that our methodology and guidelines will help developers decide when to build schedule reuse into incremental sparse runtimes.

0.34