Parallel Forward-Backward Algorithm for Hidden Markov Model

Question

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

sgmustadio · Accepted Answer · 2012-03-02 01:14:12Z

2

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/

answered Mar 2, 2012 at 1:14

sgmustadio

211 bronze badge

Sign up to request clarification or add additional context in comments.

Comments

mortonjt · Accepted Answer · 2013-06-18 13:51:16Z

1

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.

answered Jun 18, 2013 at 13:51

mortonjt

6801 gold badge6 silver badges23 bronze badges

Collectives™ on Stack Overflow

Parallel Forward-Backward Algorithm for Hidden Markov Model

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related