Temporal Parallelization of Inference in Hidden Markov Models

Syeda Sakira Hassan*, Simo Särkkä, Ángel García-Fernández

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

10 Downloads (Pure)


This paper presents algorithms for the parallelization of inference in hidden Markov models (HMMs). In particular, we propose a parallel forward-backward type of filtering and smoothing algorithm as well as a parallel Viterbi-type maximum-a-posteriori (MAP) algorithm. We define associative elements and operators to pose these inference problems as all-prefix-sums computations and parallelize them using the parallel-scan algorithm. The advantage of the proposed algorithms is that they are computationally efficient in HMM inference problems with long time horizons. We empirically compare the performance of the proposed methods to classical methods on a highly parallel graphics processing unit (GPU).

Original languageEnglish
Article number9512397
Pages (from-to)4875-4887
Number of pages13
JournalIEEE Transactions on Signal Processing
Publication statusPublished - 12 Aug 2021
MoE publication typeA1 Journal article-refereed


  • Parallel forward-backward algorithm
  • parallel max-product algorithm
  • parallel sum-product algorithm
  • parallel Viterbi algorithm


Dive into the research topics of 'Temporal Parallelization of Inference in Hidden Markov Models'. Together they form a unique fingerprint.

Cite this