Accelerating Viterbi algorithm on graphics processing units

被引：8

作者：

Hanif, Muhammad Kashif ^{[1
]}

Zimmermann, Karl-Heinz ^{[2
]}

机构：

[1] Govt Coll Univ, Dept Comp Sci, Faisalabad, Pakistan

[2] Hamburg Univ Technol, Inst Embedded Syst, D-21071 Hamburg, Germany

来源：

COMPUTING | 2017年 / 99卷 / 11期

关键词：

Hidden Markov model; Viterbi algorithm; Matrix product; Graphics processing unit; CUDA; IMPLEMENTATION; GPU;

D O I：

10.1007/s00607-017-0557-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：1105 / 1123

页数：19

共 50 条

[21] Accelerating protein structure recovery using graphics processing units
Payne, BR
Owen, GS
Weber, I
COMPUTATIONAL SCIENCE - ICCS 2005, PT 1, PROCEEDINGS, 2005, 3514 : 451 - 459
[22] Accelerating dust temperature calculations with graphics-processing units
Jonsson, Patrik
Primack, Joel R.
NEW ASTRONOMY, 2010, 15 (06) : 509 - 514
[23] Accelerating Euler Equations Numerical Solver on Graphics Processing Units
Kestener, Pierre
Chateau, Frederic
Teyssier, Romain
ALGORITHMS AND ARCHITECTURES FOR PARALLEL PROCESSING, PT 2, PROCEEDINGS, 2010, 6082 : 281 - +
[24] Accelerating Sparse Linear Algebra Using Graphics Processing Units
Spagnoli, Kyle E.
Humphrey, John R.
Price, Daniel K.
Kelmelis, Eric J.
MODELING AND SIMULATION FOR DEFENSE SYSTEMS AND APPLICATIONS VI, 2011, 8060
[25] Accelerating the Gillespie Exact Stochastic Simulation Algorithm Using Hybrid Parallel Execution on Graphics Processing Units
Komarov, Ivan
D'Souza, Roshan M.
PLOS ONE, 2012, 7 (11):
[26] Accelerating radio astronomy cross-correlation with graphics processing units
Clark, M. A.
La Plante, P. C.
Greenhill, L. J.
INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS, 2013, 27 (02): : 178 - 192
[27] Accelerating Sparse Matrix Operations in Neural Networks on Graphics Processing Units
Argueta, Arturo
Chiang, David
57TH ANNUAL MEETING OF THE ASSOCIATION FOR COMPUTATIONAL LINGUISTICS (ACL 2019), 2019, : 6215 - 6224
[28] Accelerating B-Spline Registration Using Graphics Processing Units
Sagedy, C.
Kandasamy, N.
Sharp, G.
MEDICAL PHYSICS, 2009, 36 (06)
[29] Accelerating molecular dynamics simulations using Graphics Processing Units with CUDA
Liu, Weiguo
Schmidt, Bertil
Voss, Gerrit
Mueller-Wittig, Wolfgang
COMPUTER PHYSICS COMMUNICATIONS, 2008, 179 (09) : 634 - 641
[30] Accelerating spectral atomic and molecular collisions methods with graphics processing units
Colavecchia, F. D.
COMPUTER PHYSICS COMMUNICATIONS, 2014, 185 (07) : 1955 - 1964

← 1 2 3 4 5 →