  This paper presents algorithms for parallelization of inference in hidden
Markov models (HMMs). In particular, we propose parallel backward-forward type
of filtering and smoothing algorithm as well as parallel Viterbi-type
maximum-a-posteriori (MAP) algorithm. We define associative elements and
operators to pose these inference problems as parallel-prefix-sum computations
in sum-product and max-product algorithms and parallelize them using
parallel-scan algorithms. 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 graphical processing unit (GPU).
