Fused3S: Fast Sparse Attention on Tensor Cores

• URL: http://arxiv.org/abs/2505.08098v1
• Date: Mon, 12 May 2025 22:09:05 GMT
• Title: Fused3S: Fast Sparse Attention on Tensor Cores
• Authors: Zitong Li, Aparna Chandramowlishwaran,
• Abstract summary: This paper introduces Fused3S, the first fused 3S algorithm that jointly maximizes tensor core utilization and minimizes data movement.<n>Across real-world graph datasets, Fused3S $1.6- 16.3times$ and $1.5-14times$ speedup over state-of-the-art on H100 and A30 GPU.
• Score: 3.6068301267188
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Sparse attention is a core building block in many leading neural network models, from graph-structured learning to sparse sequence modeling. It can be decomposed into a sequence of three sparse matrix operations (3S): sampled dense-dense matrix multiplication (SDDMM), softmax normalization, and sparse matrix multiplication (SpMM). Efficiently executing the 3S computational pattern on modern GPUs remains challenging due to (a) the mismatch between unstructured sparsity and tensor cores optimized for dense operations, and (b) the high cost of data movement. Previous works have optimized these sparse operations individually or addressed one of these challenges. This paper introduces Fused3S, the first fused 3S algorithm that jointly maximizes tensor core utilization and minimizes data movement. Across real-world graph datasets, Fused3S achieves $1.6- 16.3\times$ and $1.5-14\times$ speedup over state-of-the-art on H100 and A30 GPUs. Furthermore, integrating Fused3S into Graph Transformer inference accelerates end-to-end performance by $1.05-5.36\times$, consistently outperforming all 3S baselines across diverse datasets (single and batched graphs) and GPU architectures.

Related papers

• TriADA: Massively Parallel Trilinear Matrix-by-Tensor Multiply-Add Algorithm and Device Architecture for the Acceleration of 3D Discrete Transformations [0.0]
  Multilinear transformations are key in high-performance computing ( HPC) and artificial intelligence (AI) workloads.<n> scaling computation by enlarging the number of parallel processing units substantially increases energy consumption.<n>TriADA is capable of performing a variety of trilinear transformations with hypercubic arithmetic complexity in a linear number of time-steps.
  arXiv  Detail & Related papers  (2025-06-28T08:42:01Z)
• An Efficient Sparse Kernel Generator for O(3)-Equivariant Deep Networks [0.5737287537823071]
  Rotation equivariant graph neural networks yield state of the art performance on spatial deep learning tasks.<n>Key to these models is the Clebsch-Gordon (CG) tensor product, a kernel that contracts two dense feature vectors with a highly-structured sparse tensor to produce a dense output vector.<n>We introduce a GPU sparse kernel generator for the CG tensor product that provides significant speedups over the best existing open and closed-source implementations.
  arXiv  Detail & Related papers  (2025-01-23T08:20:47Z)
• 3DGS$^2$: Near Second-order Converging 3D Gaussian Splatting [26.94968605302451]
  3D Gaussian Splatting (3DGS) has emerged as a mainstream solution for novel view synthesis and 3D reconstruction.<n>This paper introduces a (near) second-order convergent training algorithm for 3DGS, leveraging its unique properties.
  arXiv  Detail & Related papers  (2025-01-22T22:28:11Z)
• Compute Better Spent: Replacing Dense Layers with Structured Matrices [77.61728033234233]
  We identify more efficient alternatives to dense matrices, as exemplified by the success of convolutional networks in the image domain. We show that different structures often require drastically different initialization scales and learning rates, which are crucial to performance. We propose a novel matrix family containing Monarch matrices, the Block-Train, which we show performs better than dense for the same compute on multiple tasks.
  arXiv  Detail & Related papers  (2024-06-10T13:25:43Z)
• Boosting the effective performance of massively parallel tensor network state algorithms on hybrid CPU-GPU based architectures via non-Abelian symmetries [0.0]
  Non-Abelian symmetry related tensor algebra based on Wigner-Eckhart theorem is fully detached from the conventional tensor network layer. We have achieved an order of magnitude increase in performance with respect to results reported in arXiv:2305.05581 in terms of computational complexity. Our solution has an estimated effective performance of 250-500 TFLOPS.
  arXiv  Detail & Related papers  (2023-09-23T07:49:53Z)
• INR-Arch: A Dataflow Architecture and Compiler for Arbitrary-Order Gradient Computations in Implicit Neural Representation Processing [66.00729477511219]
  Given a function represented as a computation graph, traditional architectures face challenges in efficiently computing its nth-order gradient. We introduce INR-Arch, a framework that transforms the computation graph of an nth-order gradient into a hardware-optimized dataflow architecture. We present results that demonstrate 1.8-4.8x and 1.5-3.6x speedup compared to CPU and GPU baselines respectively.
  arXiv  Detail & Related papers  (2023-08-11T04:24:39Z)
• GLEAM: Greedy Learning for Large-Scale Accelerated MRI Reconstruction [50.248694764703714]
  Unrolled neural networks have recently achieved state-of-the-art accelerated MRI reconstruction. These networks unroll iterative optimization algorithms by alternating between physics-based consistency and neural-network based regularization. We propose Greedy LEarning for Accelerated MRI reconstruction, an efficient training strategy for high-dimensional imaging settings.
  arXiv  Detail & Related papers  (2022-07-18T06:01:29Z)
• Instant Neural Graphics Primitives with a Multiresolution Hash Encoding [67.33850633281803]
  We present a versatile new input encoding that permits the use of a smaller network without sacrificing quality. A small neural network is augmented by a multiresolution hash table of trainable feature vectors whose values are optimized through a gradient descent. We achieve a combined speed of several orders of magnitude, enabling training of high-quality neural graphics primitives in a matter of seconds.
  arXiv  Detail & Related papers  (2022-01-16T07:22:47Z)
• Mesh Convolution with Continuous Filters for 3D Surface Parsing [101.25796935464648]
  We propose a series of modular operations for effective geometric feature learning from 3D triangle meshes. Our mesh convolutions exploit spherical harmonics as orthonormal bases to create continuous convolutional filters. We further contribute a novel hierarchical neural network for perceptual parsing of 3D surfaces, named PicassoNet++.
  arXiv  Detail & Related papers  (2021-12-03T09:16:49Z)
• 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)
• RT3D: Achieving Real-Time Execution of 3D Convolutional Neural Networks on Mobile Devices [57.877112704841366]
  This paper proposes RT3D, a model compression and mobile acceleration framework for 3D CNNs. For the first time, real-time execution of 3D CNNs is achieved on off-the-shelf mobiles.
  arXiv  Detail & Related papers  (2020-07-20T02:05:32Z)

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.