Re: parallelization of potential operations

Alex Kozlov) (alexvk@vostok.engr.sgi.com)
Mon, 16 Nov 1998 10:16:24 -0800 (PST)

Anders L Madsen wrote:
> Hi All,
>
> As has been mentioned by many researchers, a good way of exploiting
> parallelisme in multiprocessor computers when performing Bayesian
> inference is to have the table operations split up in independent
> subtasks.
>
> Does anyone know of any algorithms developed for performing
> multiplication, division, and marginalization of multiple dimensioned
> probability potentials or more general multiple dimensioned structures?
>
> Any replies will be appreciated.
>

Parallelization of probabilistic inference was part of my thesis. You
can find it at:

http://robotics.Stanford.EDU/~alexvk/Public/thesis.ps

The relevant parts were also published at the IEEE journal (although
the thesis version is more complete):

IEEE Computer, Dec. 1996, vol.29, no. 12, pp. 33-40.

You can also find the paper online at:

http://robotics.Stanford.EDU/~alexvk/Public/Papers/parallel-ieee-96.ps

In the thesis I show that, given care of data locality---which is an
important factor to achieve a good speedups on a multiprocessor---
parallelization of operations on potentials and global conditioning
are very similar in spirit (different in results). One can consider
parallelization of message propagation as an optimization of global
conditioning (we optimize out some redundant computations this way).

I'll be happy to hear any development/criticism of this work.

-- 
Alexander V. Kozlov | alexvk@engr.sgi.com | (650) 933-8493