Reducing Data Movement in the Galerkin Product of Block Algebraic Multigrid on GPUs

• URL: http://arxiv.org/abs/2607.28891v3
• Date: Tue, 04 Aug 2026 11:34:29 GMT
• Title: Reducing Data Movement in the Galerkin Product of Block Algebraic Multigrid on GPUs
• Abstract summary: For 3D elasticity the fine operator has $3times3$ blocks, the sparse prolongator $3times6$, and the coarse operator $6times6$, a shape no vendor sparse library supports.<n>We present a sharedmemory-tiled kernel with a sorted search-free schedule that moves fewer bytes in less than half the time of the portable Kokkos team kernels.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The Galerkin triple product $A_c = P^T A P$ dominates the recurring per-solve setup cost of algebraic multigrid (AMG). For AMG on systems of PDEs the product is a rectangular-block sparse matrix triple product: for 3D elasticity the fine operator has $3\times3$ blocks, the prolongator $3\times6$, and the coarse operator $6\times6$, a shape no vendor sparse library supports. We map its algorithm space -- classical two-pass, fused-recompute, schedule-reordered, shared-memory-tiled, and inspector-executor variants -- under an explicit DRAM/L2 traffic model, and implement the leading variants in portable Kokkos (CUDA) and native CUDA backends using new PETSc blocked matrix types. Validated on an NVIDIA A100, the model predicts per level which variant moves the fewest bytes. Guided by it, a shared-memory-tiled kernel with a sorted, search-free schedule moves fewer bytes in less than half the time of the portable Kokkos team kernels on the fine-level product (10.5 vs 17.4 GB of DRAM, 45 vs 82 ms), within $2.5\times$ of the model's streaming floor for the full product and $1.9\times$ on its $A\cdot P$ stage. We further present prolongator filtering, a new PETSc GAMG algorithm that drops small blocks from the coarse space under a Frobenius criterion with a kernel-preserving projection; it reduces $P^TAP$ traffic, coarse-operator fill, and memory, and cuts the hot $P^TAP$ time $2.9\times$ on the fine grid with iteration counts unchanged. The driving application is a fully GPU-resident blocked pipeline in PETSc: finite-element assembly writes directly into the blocked device matrix, and the AMG setup, Galerkin products, and solve all operate on primary blocked data with no scalar expansion and no operator-sized device-host transfers in the recurring phases.

Related papers

• Memristive-Friendly Hadamard Reservoir Computing: Structured, Multiplier-Free Recurrences at Scale [10.72107520133713]
  Reservoir Computing (RC) designs Recurrent Neural Networks around a fixed, untrained, recurrent layer, and is a natural candidate for neuromorphic hardware.<n>We replace the dense matrix with a structured orthogonal operator, built from sign diagonals, a permutation, and a fast Walsh-Hadamard transform.<n>We time the recurrent step on three hardware platforms, where it is up to $50times$ faster than a dense product and $104times$ smaller in memory.
  arXiv  Detail & Related papers  (2026-08-28T12:58:42Z)
• SURGE: SuperBatch Unified Resource-efficient GPU Encoding for Heterogeneous Partitioned Data [3.1624024957575982]
  SURGE is a streaming encoding system deployed in production to generate embeddings for over 800 million texts across 40,000 logical partitions.<n>On 10M texts with 4 NVIDIA L4768, SURGE delivers 26,413 texts/s -- matching fixed-times throughput using 12.6times less memory.
  arXiv  Detail & Related papers  (2026-05-01T19:51:50Z)
• Cache Hierarchy and Vectorization Analysis of Lindblad Master Equation Simulation for Near-Term Quantum Control [0.0]
  Simulation of open quantum systems via the Lindblad master equation is a computational bottleneck in near-term quantum control.<n>We develop a system that straddles the L1, L2, and L3 cache boundaries of modern CPUs.<n>We show that SoA layout combined with -O3 -march=native -ffast-math yields $2$--$4times$ speedup over scalar array-of-structures baselines.
  arXiv  Detail & Related papers  (2026-03-17T21:53:31Z)
• FHECore: Rethinking GPU Microarchitecture for Fully Homomorphic Encryption [2.7777199166440827]
  Fully Homomorphic Encryption (FHE) enables computation directly on encrypted data but incurs massive computational and memory overheads.<n>Custom accelerators can mitigate these costs, but their long time-to-market and the rapid evolution of FHE algorithms threaten their long-term relevance.<n>We propose FHECore, a specialized functional unit integrated directly into the GPU's Streaming Multiprocessor.
  arXiv  Detail & Related papers  (2026-02-10T02:55:10Z)
• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  Generalized Spatial Propagation Network (GSPN) addresses this by replacing quadratic self-attention with a line-scan propagation scheme.<n>GSPN-2 establishes a new efficiency frontier for modeling global spatial context in vision applications.
  arXiv  Detail & Related papers  (2025-11-28T07:26:45Z)
• Evolution Strategies at the Hyperscale [57.75314521465674]
  We introduce EGGROLL, an evolution strategies (ES) algorithm designed to scale backprop-free optimization to large population sizes.<n>ES is a set of powerful blackbox optimisation methods that can handle non-differentiable or noisy objectives.<n>EGGROLL overcomes these bottlenecks by generating random matrices $Ain mathbbRmtimes r, Bin mathbbRntimes r$ with $rll min(m,n)$ to form a low-rank matrix perturbation $A Btop$
  arXiv  Detail & Related papers  (2025-11-20T18:56:05Z)
• StelLA: Subspace Learning in Low-rank Adaptation using Stiefel Manifold [51.93627542334909]
  Low-rank adaptation (LoRA) has been widely adopted as a parameter-efficient technique for fine-tuning large-scale pre-trained models.<n>We propose a geometry-aware extension of LoRA that uses a three-factor decomposition $U!SVtop$.
  arXiv  Detail & Related papers  (2025-10-02T11:59:13Z)
• Tensor Decomposition Networks for Fast Machine Learning Interatomic Potential Computations [48.46721044282335]
  tensor decomposition networks (TDNs) achieve competitive performance with dramatic speedup in computations.<n>We evaluate TDNs on PubChemQCR, a newly curated molecular relaxation dataset containing 105 million DFT-calculated snapshots.<n>Results show that TDNs achieve competitive performance with dramatic speedup in computations.
  arXiv  Detail & Related papers  (2025-07-01T18:46:27Z)
• FedSVD: Adaptive Orthogonalization for Private Federated Learning with LoRA [68.44043212834204]
  Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)<n>Low-Rank Adaptation (LoRA) is widely used for efficient fine-tuning of language models in learning (FL)
  arXiv  Detail & Related papers  (2025-05-19T07:32:56Z)
• Density Matrix Renormalization Group with Tensor Processing Units [0.0]
  Google's Processing Units (TPUs) are integrated circuits specifically built to accelerate and scale up machine learning workloads. In this work we demonstrate the use of TPUs for accelerating and scaling up the density matrix renormalization group (DMRG), a powerful numerical approach to compute the ground state of a local quantum many-body Hamiltonian.
  arXiv  Detail & Related papers  (2022-04-12T10:40:14Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.