Optimizing the Forward Algorithm for Hidden Markov Model on IBM Roadrunner clusters
| Autor: | Stefania-Iuliana Soiman, Stefan Gheorghe Pentiuc, Ionela Rusu |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Physics::General Physics
lcsh:Computer engineering. Computer hardware Theoretical computer science General Computer Science business.operation Computer science parallel hybrid architectures Forward–backward algorithm lcsh:TK7885-7895 forward algorithm multicore processing Viterbi algorithm Markov model symbols.namesake Markov algorithm performance analysis Electrical and Electronic Engineering Hidden Markov model parallel programming hidden Markov models Maximum-entropy Markov model Roadrunner symbols lcsh:Electrical engineering. Electronics. Nuclear engineering Forward algorithm business lcsh:TK1-9971 |
| Zdroj: | Advances in Electrical and Computer Engineering, Vol 15, Iss 2, Pp 103-108 (2015) |
| ISSN: | 1844-7600 1582-7445 |
| Popis: | In this paper we present a parallel solution of the Forward Algorithm for Hidden Markov Models. The Forward algorithm compute a probability of a hidden state from Markov model at a certain time, this process being recursively. The whole process requires large computational resources for those models with a large number of states and long observation sequences. Our solution in order to reduce the computational time is a multilevel parallelization of Forward algorithm. Two types of cores were used in our implementation, for each level of parallelization, cores that are graved on the same chip of PowerXCell8i processor. This hybrid architecture of processors permitted us to obtain a speedup factor over 40 relative to the sequential algorithm for a model with 24 states and 25 millions of observable symbols. Experimental results showed that the parallel Forward algorithm can evaluate the probability of an observation sequence on a hidden Markov model 40 times faster than the classic one does. Based on the performance obtained, we demonstrate the applicability of this parallel implementation of Forward algorithm in complex problems such as large vocabulary speech recognition. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|