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

Question

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

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

Спасибо,

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 имеет право указать, что вы не можете распараллеливать рекурсивные шаги, но, похоже, эти авторы придумали умный способ уменьшить алгоритмы Forward и Viterbi до серии матричных умножений и сокращений.