A Nonlinear Hash-based Optimization Method for SpMV on GPUs

• URL: http://arxiv.org/abs/2504.08860v1
• Date: Fri, 11 Apr 2025 08:31:44 GMT
• Title: A Nonlinear Hash-based Optimization Method for SpMV on GPUs
• Authors: Chen Yan, Boyu Diao, Hangda Liu, Zhulin An, Yongjun Xu,
• Abstract summary: We highlight the effectiveness of hash-based techniques in optimizing sparse matrix reordering.<n>In this paper, we introduce the Hash-based Partition (HBP) format, a lightweight SpMV approach.<n>In experiments, our method offers an average speedup of 3.53 times compared to the sorting approach and 3.67 times compared to the dynamic programming method employed in Regu2D.
• Score: 19.6395697341071
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sparse matrix-vector multiplication (SpMV) is a fundamental operation with a wide range of applications in scientific computing and artificial intelligence. However, the large scale and sparsity of sparse matrix often make it a performance bottleneck. In this paper, we highlight the effectiveness of hash-based techniques in optimizing sparse matrix reordering, introducing the Hash-based Partition (HBP) format, a lightweight SpMV approach. HBP retains the performance benefits of the 2D-partitioning method while leveraging the hash transformation's ability to group similar elements, thereby accelerating the pre-processing phase of sparse matrix reordering. Additionally, we achieve parallel load balancing across matrix blocks through a competitive method. Our experiments, conducted on both Nvidia Jetson AGX Orin and Nvidia RTX 4090, show that in the pre-processing step, our method offers an average speedup of 3.53 times compared to the sorting approach and 3.67 times compared to the dynamic programming method employed in Regu2D. Furthermore, in SpMV, our method achieves a maximum speedup of 3.32 times on Orin and 3.01 times on RTX4090 against the CSR format in sparse matrices from the University of Florida Sparse Matrix Collection.

Related papers

• Orthogonal Finetuning Made Scalable [87.49040247077389]
  Orthogonal finetuning (OFT) offers highly parameter-efficient adaptation while preventing catastrophic forgetting, but its high runtime and memory demands limit practical deployment.<n>We identify the core computational bottleneck in OFT as its weight-centric implementation, which relies on costly matrix-matrix multiplications with cubic complexity.<n>We propose OFTv2, an input-centric reformulation that instead uses matrix-vector multiplications (i.e., matrix-free computation), reducing the computational cost to quadratic.<n>These modifications allow OFTv2 to achieve up to 10x faster training and 3x lower GPU memory usage without compromising performance.
  arXiv  Detail & Related papers  (2025-06-24T17:59:49Z)
• SMM-Conv: Scalar Matrix Multiplication with Zero Packing for Accelerated Convolution [4.14360329494344]
  We present a novel approach for accelerating convolutions during inference for CPU-based architectures. Our experiments with commonly used network architectures demonstrate a significant speedup compared to existing indirect methods.
  arXiv  Detail & Related papers  (2024-11-23T21:43:38Z)
• 3DGS-LM: Faster Gaussian-Splatting Optimization with Levenberg-Marquardt [65.25603275491544]
  We present 3DGS-LM, a new method that accelerates the reconstruction of 3D Gaussian Splatting (3DGS) Our method is 30% faster than the original 3DGS while obtaining the same reconstruction quality optimization.
  arXiv  Detail & Related papers  (2024-09-19T16:31:44Z)
• Acceleration of Subspace Learning Machine via Particle Swarm Optimization and Parallel Processing [23.33955958124822]
  Subspace learning machine (SLM) has been proposed to offer higher performance in general classification and regression tasks. Performance improvement is reached at the expense of higher computational complexity. Experimental results show that the accelerated SLM method achieves a speed up factor of 577 in training time.
  arXiv  Detail & Related papers  (2022-08-15T06:33:15Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Discrete Morse Sandwich: Fast Computation of Persistence Diagrams for Scalar Data -- An Algorithm and A Benchmark [8.648433479399857]
  This paper introduces an efficient algorithm for persistence diagram computation, given an input piecewise linear scalar field f defined on a d-dimensional simplicial complex K. We express this algorithm within the setting of discrete Morse theory, which considerably reduces the number of input simplices to consider. We also introduce a stratification approach to the problem, that we call "sandwiching"
  arXiv  Detail & Related papers  (2022-06-27T10:54:24Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root and the inverse square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP), and the other method is to use Matrix Pad'e Approximants (MPA) A series of numerical tests show that both methods yield considerable speed-up compared with the SVD or the NS iteration.
  arXiv  Detail & Related papers  (2022-01-29T10:00:35Z)
• Fast Differentiable Matrix Square Root [65.67315418971688]
  We propose two more efficient variants to compute the differentiable matrix square root. For the forward propagation, one method is to use Matrix Taylor Polynomial (MTP) The other method is to use Matrix Pad'e Approximants (MPA)
  arXiv  Detail & Related papers  (2022-01-21T12:18:06Z)
• Nesterov Accelerated ADMM for Fast Diffeomorphic Image Registration [63.15453821022452]
  Recent developments in approaches based on deep learning have achieved sub-second runtimes for DiffIR. We propose a simple iterative scheme that functionally composes intermediate non-stationary velocity fields. We then propose a convex optimisation model that uses a regularisation term of arbitrary order to impose smoothness on these velocity fields.
  arXiv  Detail & Related papers  (2021-09-26T19:56:45Z)
• Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach [4.710916891482697]
  A pseudoinverse is a generalization of a matrix inverse, which has been extensively utilized in machine learning. FastPI is a novel incremental singular value decomposition (SVD) based pseudoinverse method for sparse matrices. We show that FastPI computes the pseudoinverse faster than other approximate methods without loss of accuracy.
  arXiv  Detail & Related papers  (2020-11-09T07:47:10Z)
• Fast Coherent Point Drift [4.369046007546103]
  Coherent point drift (CPD) is a classical method for nonrigid point set registration. By introducing a simple corresponding constraint, we develop a fast implementation of CPD. Experimental results in 3D point cloud data show that our method can significantly reduce burden of the registration process.
  arXiv  Detail & Related papers  (2020-06-11T09:35:23Z)

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.