High speed decoding for hidden semi-Markov models using GPUs
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
Machine LearningDistributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
Hidden Semi-Markov Models are tools used to find hidden patterns in sequences, but the standard method to decode them is slow and runs one step at a time. The authors created a new way to rewrite this method so it can run many steps at once, especially on graphics cards (GPUs) designed for parallel tasks. This leads to hundreds of times faster decoding, making these models practical for much bigger or more complex problems. Their work provides faster tools for anyone who uses these models in areas like biology, finance, or signal processing.
What this means in practice
- •For bioinformatics teams: Run biological sequence analyses faster by decoding hidden state sequences using GPU-accelerated HSMM Viterbi implementations.
- •For financial modelers: Speed up detection of market regimes or events with large-scale HSMM decoding on GPUs enabled by the new tensor-based algorithm.
Authors
Lorenzo Piarulli, Elia Belli, Daniele De Sensi
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.