Results show that template-anchored decomposition and stage-specific GPU execution can scale matrix completion beyond device-memory capacity, and show that template-anchored decomposition and stage-specific GPU execution can scale matrix completion beyond device-memory capacity.
Abstract
Matrix completion supports large-scale recommendation and scientific computing, yet existing GPU solvers commonly assume that the observed matrix or its dense factors fit in device memory. On real workloads, this assumption leads to out-of-memory failures or severe PCIe overhead under naive paging. We present TIDE-MC, a bounded-memory GPU framework built on Two-Sided Interpolative Decomposition (TSID). TSID uses a sampled template submatrix as an anchor for reconstructing the full low-rank matrix, allowing computation and storage to scale with the template and active data chunks rather than the complete matrix. TIDE-MC realizes this formulation through two execution stages. First, a conflict-free synchronization engine recovers the template using parallel factorization and hierarchical gradient aggregation. Second, a chunked reconstruction pipeline extends the recovered template to the remaining matrix while overlapping PCIe transfers with GPU computation. An asymmetric gradient-clipping scheme stabilizes mixed-precision Tensor Core execution. Across 15 benchmarks, TIDE-MC completes workloads that cause existing GPU solvers to run out of memory. Compared with the evaluated state-of-the-art baselines, it achieves up to 11,647x speedup, reduces peak memory usage by up to 8.5x, and lowers reconstruction error by up to 99.7%. These results show that template-anchored decomposition and stage-specific GPU execution can scale matrix completion beyond device-memory capacity.
Triangular Solve with Multiple Right-hand Sides (TRSM) is a fundamental BLAS Level-3 operation that underpins LU/Cholesky decomposition, sparse direct solvers, and matrix inversion. In the left-side lower-triangular case studied in this paper, efficient GPU implementation remains challenging because forward substitution introduces strict row-wise dependencies, and shared memory is too scarce to hold both operand matrices for wide data types such as double complex. This paper presents HSMA-TRSM, a hierarchical shared memory-aware optimization framework for left-side lower-triangular TRSM on NVIDIA A100, NVIDIA H800, and Hygon DCU Z100 accelerators. For the small-scale regime (m, n ≤ 64), we design a pipelined compute-memory overlap mechanism through loop unrolling and instruction reordering, and propose a dual thread-group seven-stage pipeline strategy to address shared memory constraints for double complex types. For large-scale problems, we introduce a diagonal block decoupling optimization with an O(IB) shared-memory footprint for diagonal block inversion, enabling adaptive block size selection based on matrix scale and hardware characteristics. A compile-time configuration selection framework based on offline profiling and online lookup selects the optimal block size per platform with zero runtime overhead. Evaluated on NVIDIA A100, H800, and Hygon DCU Z100, HSMA-TRSM achieves peak speedups of 2.05 × over cuBLAS and 2.06 × over rocBLAS. The gains are strongest in shared-memory-constrained double-complex small cases and in large real-type cases where adaptive blocking improves GEMM-dominated updates, while mature vendor kernels leave less optimization headroom in some regimes.
Xin-Zhe Chen, Hao-Wei Li, Li-Juan Hu et al.· Proceedings of the Internati...· 0 citations
Sparse Matrix-Matrix Multiplication (SpMM) is a fundamental operation in scientific computing and artificial intelligence. However, the inherent sparsity and irregularity of real-world datasets present significant challenges for developing high-performance SpMM kernels on modern GPUs. Existing approaches typically focus on a single type of compute unit, leaving the potential for cooperative parallelism between heterogeneous GPU cores largely under-explored. This paper introduces CoTC-SpMM, a cooperative Tensor–CUDA cores scheme for efficient SpMM on GPUs. Specifically, we first propose the HTC format to partition sparse matrices into dense and sparse components, enabling specialized kernels to leverage the distinct advantages of different computing units and maximize hardware utilization. Moreover, we implement several low-level runtime optimizations, including 1-D resource mapping for load balancing, software pipelining to hide memory latency, and PTX-level instruction tuning to enhance SpMM throughput. Experimental results on NVIDIA A100 and H800 GPUs demonstrate that CoTC-SpMM achieves substantial performance speedups over state-of-the-art implementations.
Qi Du, Shengle Lin, Yuedan Chen et al.· Proceedings of the Internati...· 0 citations
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 reaches the published criterion on nine 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
Arnaud Deza, S. Dey, P. Van Hentenryck· 0 citations
Celty, a co-designed sparse format, GPU kernel, and SIMT microarchitecture for efficient spMspV in LLM inference is proposed, which introduces a Run-Length Compressed CSC format that enables vectorized loading of compressed weight columns and exploits both sparsity sources to skip unnecessary memory accesses.
Following the Scaling Law, Deep Neural Networks face immense parameter scales and costs, making high-compression unstructured pruning attractive. Additionally, rising edge-side deployment demands have revived interest in activation sparsity. Consequently, unstructured sparse-dense and sparse-sparse matrix multiplications are becoming prevalent in LLM training and inference. However, as the most common general-purpose AI accelerators, GPUs do not provide efficient support for unstructured sparse matrices. Although existing works have proposed GPU architectural enhancements for unstructured sparsity, they are often limited to optimizing Tensor Core computation patterns through dataflows such as outer-product and row-by-row. These methods fail to adequately resolve the poor load balancing and low Multiply-Accumulate utilization in unstructured sparse workloads, especially lacking targeted optimizations for the latest GPU architectural features. To address these issues, we propose RODIS, a two-level acceleration scheme. It utilizes row-orchestration at the data loading level to achieve inter-block load balancing and employs dynamic instruction scheduling at the underlying computation level to enhance MAC utilization. Experimental results show that with minimal area and power overhead, RODIS achieves an average 1.35 × performance improvement compared to other state-of-the-art sparse Tensor Core schemes.
Jian-Feng Cui, Bo Yuan, Ze-Kun Jiang et al.· Proceedings of the Internati...· 0 citations
Tensors provide a natural representation for multi-dimensional data, and Tucker decomposition via Higher-Order Orthogonal Iteration (HOOI) is widely used to uncover their latent structure. Many tensors that arise in practice are highly sparse. On GPUs, sparse HOOI is bottlenecked by the tensor-times-matrix chain (TTMc) and the full singular value decomposition (SVD). TTMc suffers from load imbalance, while SVD incurs high time and workspace costs. Prior GPU work has focused primarily on TTMc, leaving the SVD update largely unoptimized. At high sparsity, SVD can dominate iteration time. At large mode dimensions, it can exhaust GPU memory entirely. We present SAKTHI, an end-to-end GPU framework that optimizes the full sparse HOOI pipeline. For TTMc, SAKTHI operates on the Compressed Sparse Fiber (CSF) format and adaptively selects between two kernels. IntraDyn uses intra-SM dynamic scheduling to eliminate global atomics for third-order tensors when fibers are reasonably uniform. FullDyn combines a one-time task decomposition with global warp scheduling to address both intra- and inter-slice imbalance when the fiber-length distribution is highly irregular. For SVD, SAKTHI replaces the full SVD with a Gram-matrix-based truncated SVD, gated at runtime by a gap-to-noise-ratio condition derived from a perturbation analysis. On a range of real-world and synthetic sparse tensors, SAKTHI delivers orders-of-magnitude end-to-end speedups over the prior state of the art, runs successfully on tensors where previous methods fail due to memory exhaustion, and produces matching fit.
Bhaskar Marati, Raghavendra Kanakagiri· ACM Transactions on Architec...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
