Accelerating Viterbi algorithm on graphics processing units

作者：Hanif Muhammad Kashif^*; Zimmermann Karl Heinz

来源：Computing, 2017, 99(11): 1105-1123.

DOI：10.1007/s00607-017-0557-6

• Hidden Markov model
• Viterbi algorithm
• Matrix product
• Graphics processing unit
• CUDA

Viterbi algorithm is used in different scientific applications including biological sequence alignment, speech recognition, and probabilistic inference. However, high computational complexity of the Viterbi algorithm is a major concern. Accelerating the Viterbi algorithm is important, especially when the number of states or the length of the sequences increase significantly. In this paper, a parallel solution to improve the performance of Viterbi algorithm is presented. This is achieved by formulating a matrix product based algorithm. This algorithm has been mapped to a NVIDIA graphics processing unit. The performance for different parameters and realizations are compared. The results depicts matrix product is not a viable option for small number of states. However, matrix product solution using shared memory for large number of states gains good performance when compared with the serial version.

• 出版日期2017-11