The fast evaluation of hidden Markov models on GPU

Abstract

It is compute-intensive to evaluate the probability of an observation sequence on a hidden Markov model. Some fast algorithms exit, the forward-backward procedure is the most popular one among them. The forward-backward procedure can save much computation, but its time complexity is N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> T, in other words, there is a high computational complexity in the algorithm. In this paper, we present a parallel evaluation algorithm using a commodity graphics processing unit. The algorithm exploits the single-instruction-multiple-thread architecture of GPU to get high-performance. First, the forward probabilities are calculated in parallel, and then they are summed up also in parallel to get the probability of an observation sequence. The optimal using of memory bandwidth is studied in the algorithm to obtain the best performance. The algorithm was implemented on a NVIDIA 9800 GTX+ GPU, experimental results showed the parallel algorithm can evaluate the probability of an observation sequence on a hidden Markov model 4∼25 times fast than the classic one does.