Options
Accelerating Viterbi algorithm on graphics processing units
Publikationstyp
Journal Article
Date Issued
2017-05-19
Sprache
English
Author(s)
Institut
TORE-URI
Journal
Volume
99
Issue
11
Start Page
1105
End Page
1123
Citation
Computing 11 (99): 1105-1123 (2017)
Publisher DOI
Scopus ID
Publisher
Springer
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.
Subjects
CUDA
Graphics processing unit
Hidden Markov model
Matrix product
Viterbi algorithm
DDC Class
380: Handel, Kommunikation, Verkehr
600: Technik