The fast evaluation of hidden Markov models on GPU
Comput. Dept., Jinan Univ., Jinan, China
IEEE International Conference on Intelligent Computing and Intelligent Systems, 2009. ICIS 2009
@conference{li2009fast,
title={The fast evaluation of hidden Markov models on GPU},
author={Li, J. and Chen, S. and Li, Y.},
booktitle={Intelligent Computing and Intelligent Systems, 2009. ICIS 2009. IEEE International Conference on},
volume={4},
pages={426–430},
organization={IEEE}
}
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^2T, 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.
April 12, 2011 by hgpu
