Параллельный прямой-обратный алгоритм для скрытой марковской модели

Question

В качестве побочного проекта я хочу реализовать скрытую марковскую модель для моей видеокарты NVidia, чтобы она могла выполняться быстро и с использованием множества ядер.

Я смотрю на алгоритм прямого-обратногои мне было интересно, что я могу сделать здесь параллельно?Например, если вы посмотрите на переднюю часть алгоритма, умножения матриц можно разделить для параллельного выполнения, но можно ли каким-либо образом распараллелить итеративные части алгоритма, которые зависят от предыдущего шага?Есть ли какой-то математический прием, который можно применить здесь?

Спасибо,

mj

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

Answer 1

Вы правы в своей оценке - вы можете распараллелить умножения матриц (т.е. по состояниям), но вы не можете распараллелить рекурсивные шагиЯ только что сделал сообщение в блоге о своей работе с HMM и GPU.Проверьте это здесь:

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

Answer 2

Если вы все еще работаете над этим проектом, вы можете проверить HMMlib и parredHMMlib .

sgmustadio справедливо указывает на то, что вы не можете распараллелить рекурсивные шаги, но кажется, что эти авторы придумали хитрый способ уменьшить алгоритмы Форварда и Витерби до серии умножений и сокращений матриц.