CS Paper Radar

High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models

Lorenzo Piarulli, Elia Belli, Daniele De Sensi

cs.LG cs.DCcs.DS ·submitted 2026-09-15 01:45 UTC · v1

Abstract

Hidden Semi-Markov Models (HSMMs) are fundamental probabilistic models widely adopted across diverse domains, from computational biology to finance and signal processing. The Viterbi algorithm decodes the most likely state sequence given an HSMM and can be applied iteratively for ab initio model learning. However, existing Viterbi implementations remain sequential, and GPU-accelerated solutions are entirely absent, making HSMM decoding impractical for large-scale workloads. We present a tensor-based formulation of the Viterbi algorithm for HSMMs, restructuring the inner loops into tensor operations that naturally map onto SIMD units and massively parallel architectures. Building on this formulation, we provide optimized implementations spanning single- and multi-core CPUs, and, for the first time, GPU. Experimental evaluation demonstrates speedups of up to 14x on a single core, over 200x with multi-core, and over 570x on GPU over the state-of-the-art sequential baseline, establishing a new performance baseline for large-scale HSMM decoding.

Closest papers

Nearest neighbours by meaning across the whole index.

An HPC Approach to Accelerate Tensor Decompositions

cs.DC cs.MS ·2026-08-25 ·Markus Hellgren, Erna Begovic Kovac, Hans O. Karlsson, Roman Iakymchuk
similarity 0.66
Abstract

Quantum systems grow in complexity so rapidly that even modest models become difficult to simulate, creating a strong need for methods that can handle high-dimensional data, also known as tensors. In this work, we investigate a novel Jacobi-type tensor algorithm for tensor decomposition and develop a CUDA-based algorithm that supports tensors of arbitrary order on a single GPU. We test the implementation on NVIDIA H100 GPUs and show that the algorithm converges correctly for diagonalizable tensors up to nine dimensions, with runtime scaling in a predictable way as tensor order grows. Finally, our general algorithm outperforms the original MATLAB reference by more than two orders of magnitude.

0.30

AscSpMM: Efficient SpMM on Ascend NPUs via Pipelined Vector-Cube Collaboration

cs.AR ·2026-11-09 ·Fei Li, Haoxin Li, Kehong Liu, Yanzi Zhou, Weiguo Wu +3 more
code/data similarity 0.62
Abstract · 13 pages, 11 figures

Neural processing units (NPUs) provide high compute density and energy efficiency through specialized matrix engines and software-managed on-chip memory. However, their libraries primarily target dense computation. Sparse matrix-dense matrix multiplication (SpMM), a key kernel in graph analytics, sparse neural networks, and scientific computing, requires index-driven operand selection, indirect addressing, scattered memory accesses, and load balancing. These requirements conflict with the fixed shapes and contiguous layouts preferred by NPU matrix engines. GPU Tensor Core SpMM methods cannot be directly transferred to NPUs with decoupled vector and matrix engines. We present AscSpMM, which separates irregular operand preparation from regular matrix computation through a parameterized Vector-CSR representation. The vector engine decodes indices and gathers and reorganizes dense operands, while the Cube engine performs matrix multiply-accumulate operations. A double-slot ring buffer enables dependency-aware asynchronous pipelining, while operand reuse and runtime-adaptive tiling reduce cross-engine stalls. On an Ascend 910B3, AscSpMM achieves geometric-mean speedups of 2.36x over GEMM, 19.92x over an existing SpMM implementation, and 5.82x over cuSPARSE on an A100. It reduces matrix-input storage and peak HBM footprint by 48.24% and 22.98% on average, while remaining competitive with specialized GPU Tensor Core SpMM kernels. The code is available at https://github.com/LfLab-AI/Ascend-NPU-SpMM.

0.31

Integrated GPU Core for Mamba-3

cs.AR cs.LG ·2026-11-16 ·Shiva Raja, William Desueza, Ajay Joshi
similarity 0.62
Abstract

Mamba-3, the latest Mamba state-space model (SSM), enables efficient long-context modeling, matching Mamba-2 perplexity with half the state size and increasing decoding arithmetic intensity. However, its multi-input multi-output (MIMO) computation, exponential-trapezoidal discretization, and rotary positional embeddings (RoPE) introduce dense, element-wise, and sequential operations. Despite kernel fusion, conventional GPUs execute these operations inefficiently. Our characterization of Mamba-3 hybrid models reveals numerous kernel launches, substantial data movement, and increased register pressure that reduces warp occupancy and memory-latency hiding. We propose RescuCore, a specialized GPU execution unit for Mamba-3 inference that retains other hybrid model layers on existing GPU resources. Integrated alongside CUDA Cores and Tensor Cores within each Streaming Multiprocessor (SM) sub-partition, RescuCore shares the register file, shared memory, and warp schedulers. Dense projections remain on conventional GPU resources, while RescuCore pipelines discretization, normalization, RoPE, MIMO computation, recurrent state updates, and output gating to reduce kernel fragmentation and intermediate data movement. We select BF16 after evaluating multiple numerical formats, preserving model accuracy with an estimated area overhead of 5.9% of an A100 die for state size 32 and MIMO rank 4. We evaluate RescuCore using cycle-accurate Accel-Sim simulation, RTL synthesis, and synthesis-informed AccelWattch power modeling. Compared with conventional GPU execution, RescuCore achieves 1.4-9.4x speedup and 1.4-5.0x energy reduction during prefill, and 1.3-2.8x speedup and 1.2-2.6x energy reduction during autoregressive decoding. These results demonstrate the potential of GPU-integrated specialized execution for SSM-based hybrid models.

0.17

Dual-Core Tensor Wheel Decomposition with Structure-Cached Acceleration for Tensor Recovery

cs.LG ·2026-11-10 ·Wenchao Xie, Qingsong Wang
similarity 0.62
Abstract

Tensor wheel decomposition captures complex correlations in high-dimensional data through interactions between outer-ring factors and a high-order central core. However, updating these components requires the explicit construction and manipulation of large-scale matrices, which limits computational efficiency and incurs particularly high computational and memory costs for the central-core update. To address these limitations, we propose dual-core tensor wheel decomposition (DCTW), which factorizes the central core into two lower-order cores linked by a shared latent bond. Each core is coupled to a different group of outer-ring factors. We further propose a structure-cached acceleration strategy that avoids explicit large-scale matrix multi- plications and caches intermediate tensors generated during tensor network contractions for reuse across block updates. This reuse reduces redundant computation and avoids the explicit construction of large matrices. Complexity analysis and experiments show that the strategy based on structural caching accelerates optimization compared with explicit and implicit up- date schemes while limiting the increase in peak memory as the ranks grow. Experiments on color video completion and robust denoising show that DCTW matches or outperforms representative tensor network methods in reconstruction quality, computational efficiency, and scalability.

0.22

CAFIN: CUDA-accelerated Adaptive Fisher Information Matrix Network Optimization via GPU-Native Kernel Fusion

cs.LG cs.AI ·2026-11-10 ·Maryam Arshad, Muhammad Khuram Shahzad
similarity 0.61
Abstract

Second-order optimizers improve deep neural network training using curvature information, but their practical efficiency is limited by GPU execution overhead. AdaFisher reduces Fisher Information Matrix (FIM) approximation costs through diagonal Kronecker structures and exponential moving averages, yet its PyTorch implementation requires sequential CUDA kernel launches, intermediate tensor allocations, and repeated memory accesses. We introduce CAFIN, a GPU-native CUDA kernel fusion framework that improves AdaFisher execution efficiency without changing its optimization formulation. The proposed approach progressively integrates FIM preconditioner construction, exponential moving average updates, gradient preconditioning, momentum accumulation, weight decay, and parameter updates into fused CUDA kernels. Shared-memory reuse, register-resident computation, and in-place operations further reduce memory traffic and intermediate allocations. Experiments using ResNet-18 on CIFAR-10, CIFAR-100, and Tiny ImageNet across NVIDIA GTX 1660 Ti and RTX 3060 Laptop GPUs demonstrate up to 78.4% lower isolated FIM construction latency and 2.1-26.9% lower optimizer-step latency. The implementation also eliminates approximately 18.91 MB of intermediate GPU memory allocations per optimizer step. Numerical validation confirms consistency within the predefined FP32 tolerance, while convergence accuracy remains comparable across evaluated datasets and random seeds. These findings demonstrate that CUDA kernel fusion can substantially accelerate second-order optimization while preserving AdaFisher's underlying mathematical formulation and learning behavior.

0.20

Bio-inspired Learning and Decision-Making with Probabilistic In-Memory Computing Hardware: Part 2

cs.AR ·2026-09-10 ·Thomas Dalgaty, Eiji Kawasaki, Miguel de Prado, Tommaso Salvatori, Germain Haugou +1 more
similarity 0.61
Abstract

This report extends our previous work (Part 1), which introduced an energy-based model for learning and decision-making under uncertainty. The model leverages stochastic Langevin dynamics to continuously evolve approximate probability distributions over neuron states and model weights. However, as noted in Part 1 and confirmed through GPU-based implementations, large-scale probabilistic energy-based models of this nature face significant scalability challenges due to excessive execution latency. This latency stems from a fundamental mismatch: massively parallel models with low arithmetic intensity (such as energy-based models) are being executed on processor architectures like GPUs that rely on high-bandwidth memory (HBM) interfaces. The HBM imposes brutally sequential execution constraints on inherently parallelizable models, creating the false impression that such models are unscalable. In reality, it is the GPU architecture itself, with its dependence on HBM interfaces, that is not a scalable processor architecture for this class of AI model. In this report, we demonstrate using a detailed transaction-level model (TLM) of a probabilistic analogue in-memory computing (AIMC) processor that the same energy-based model can execute well over 1000x faster than data-center-grade hardware by eliminating the HBM interface and performing computation directly within on-chip memory.

0.11

Beyond Masked Sparsity: SNACK Enables Truly Sparse Neural Networks on GPU

cs.LG cs.DC ·2026-10-02 ·Jafar Badour, Maurice van Keulen, Elena Mocanu
top venuecode/data similarity 0.61
Abstract · Accepted at NeurIPS 2026. 23 pages, 9 figures. Code: https://github.com/JafarBadour/Snack-SNN

Deep neural networks continue to grow in parameter count, driving up training and inference cost on GPUs. Sparse neural networks and Dynamic Sparse Training (DST) promise to reduce these costs, but most implementations rely on binary masks over dense tensors and recover little of the theoretical compute, memory, or energy savings. We propose SNACK, a truly sparse GPU layer that stores and computes only non-zero connections. SNACK exposes a simple PyTorch API for restructuring connections and backpropagating gradients entirely in the sparse paradigm, and ships SNACK-COO, a custom COO-format SpMM CUDA kernel with a batch-to-Streaming-Multiprocessor mapping tuned for the small-batch, high-sparsity regime typical of large-model training and single-stream inference. At the kernel level, SNACK is up to 7x faster than the masked dense baseline (Dense+Mask) and competitive with cuSPARSE, Sputnik, and FlashSparse at 95% sparsity. At 90% sparsity, a single SNACK layer accelerates training by 8x and 3.7x, and inference by 4x and 2x, over Dense+Mask and fully dense layers, respectively, while using 72% less memory than dense and substantially less energy. End-to-end, SNACK reduces GPT-2 peak training memory by up to 40% and graph-style inference latency by 4.8x over Dense+Mask at 99% sparsity.

0.51

HIERA: Workload-Aware Planning Across Implementation Spaces for GPU Kernel Optimization

cs.DC cs.AI ·2026-08-21 ·Jinghao Wang, Qiqi Gu, Chenpeng Wu, Jianguo Yao, Haibing Guan +1 more
similarity 0.60
Abstract

High-performance GPU kernels underpin modern deep learning and scientific computing. As workloads become increasingly diverse and GPU hardware evolves rapidly, developing efficient methods for automated GPU kernel generation and optimization has become increasingly important. Existing LLM-based methods typically optimize within a fixed implementation space, limiting either optimization flexibility or search efficiency. We propose \textsc{HIERA}, a hierarchical search-space planning framework for GPU kernel optimization. \textsc{HIERA} constructs contract-augmented task specifications, selects an appropriate implementation space across PyTorch operators, CUDA libraries, and custom CUDA kernels, and uses profiling feedback and expert knowledge to guide structured iterative refinement. Experiments on KernelBench across multiple various workload levels and base LLMs show that \textsc{HIERA} delivers stronger overall implementation validity, sample efficiency, and optimization performance than existing training-free methods, while remaining competitive with the training-based CUDA-L1 without additional model training. A case study on a specialized stencil operator from scientific computing further achieves a \(1.53\times\) speedup over cuDNN, demonstrating the potentiality of the general framework beyond standard machine-learning workloads.

0.38