The Fast Evaluation of Hidden Markov Models on GPU
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 N2T, 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-instructionmultiple-thread architecture of GPU to get highperformance. 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.
hidden markov model GPGPU evaluation probability
Jun Li Shuangping Chen Yanhui Li
Computer Department,Zhuhai College Jinan University Zhuhai,China
国际会议
上海
英文
2955-2959
2009-11-20（万方平台首次上网日期，不代表论文的发表时间）