@inproceedings{5dc09497bf5e4497a1480fe02efb88fd,
title = "An efficient cache-oblivious parallel viterbi algorithm",
abstract = "The Viterbi algorithm is used to find the most likely path through a hidden Markov model given an observed sequence, and has numerous applications. Due to its importance and high computational complexity, several algorithmic strategies have been developed to parallelize it on different parallel architectures. However, none of the existing Viterbi decoding algorithms designed for modern computers with cache hierarchies is simultaneously cache-efficient and cache-oblivious. Being oblivious of machine resources (e.g., caches and processors) while also being efficient promotes portability. In this paper, we present an efficient cache- and processor-oblivious Viterbi algorithm based on rank convergence. The algorithm builds upon the parallel Viterbi algorithm of Maleki et al. (PPoPP 2014). We provide empirical analysis of our algorithm by comparing it with Maleki et al.{\textquoteright}s algorithm.",
keywords = "Cache-efficient, Cache-oblivious, Divide-and-conquer, Multi-instance, Parallel, Rank convergence, Recursive, Viterbi algorithm",
author = "Rezaul Chowdhury and Pramod Ganapathi and Vivek Pradhan and Tithi, \{Jesmin Jahan\} and Yunpeng Xiao",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016 ; Conference date: 24-08-2016 Through 26-08-2016",
year = "2016",
doi = "10.1007/978-3-319-43659-3\_42",
language = "English",
isbn = "9783319436586",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "574--587",
editor = "Pierre-Fran{\c c}ois Dutot and Denis Trystram",
booktitle = "Parallel Processing - 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016, Proceedings",
}