CODEWITHSUNDEEP
mathparallel-processinghidden-markov-models
mj_
mj_

Reputation: 6447

Parallel Forward-Backward Algorithm for Hidden Markov Model

As a side project, I want to implement a Hidden Markov Model for my NVidia graphics card so that I can have it execute quickly and using many cores.

I'm looking at the Forward-Backward algorithm and was wondering what is there that I can make parallel here? If you look at the forward part of the algorithm for instance, the matrix multiplications can be divided up to be done in parallel, but can the iterative parts of the algorithm that depend on the previous step be parallelized in any way? Is there some kind of a mathematical trick that can be applied here?

Thanks,

mj

http://en.wikipedia.org/wiki/Forward%E2%80%93backward_algorithm#Example

Upvotes: 1

Views: 1369

Answers (2)

mortonjt
mortonjt

Reputation: 680

If you are still working on this project, you may want to check out HMMlib and parredHMMlib.

sgmustadio is right to point out that you cannot parallelize recursive steps, but it seems that these authors have come up with a clever way to reduce the Forward and Viterbi algorithms to a series of matrix multiplications and reductions.

Upvotes: 1

sgmustadio
sgmustadio

Reputation: 21

You are correct in your assessment - you can parallelize the matrix multiplications (i.e. across states), but you can't parallelize the recursive steps. I just made a blog post on my work with HMMs and GPUs. Check it out here:

http://sgmustadio.wordpress.com/2012/02/27/hidden-markov-models-in-cuda-gpu/

Upvotes: 2

Related Questions