Method and device for efficient parallel message computation for map inference
A message passing scheme for MAP inference on Markov Random Fields based on a message computation using an intermediate input vector I, an output message vector M, an auxiliary seed vector S, all of equal length N, and a pairwise function r=d(x,y), where r, x, y are real numbers, includes: for each element j of vector S, do S(j)=j consider an index distance Δ=2^floor(log 2(N)); repeat while Δ>0 for each index of vector I, namely i, do in parallel: consider the set of all indices within distance Δ from a given i, augmented by i; for every k belonging to this set, calculate its distance from i using the function: d(i,k)+I(S(k)); find the minimum distance and call n the index corresponding to this minimum distance do S ( i )= S ( n ) Δ=floor (Δ/2) for each j of vector M, do M(j)=I(S(j))+d(j,S(j)).
1. A method to be carried out by a processing device for efficiently performing a message passing algorithm encoded in software executable by said processing device and stored in a memory of said computer device, the method causing the processing device to preform steps comprising:
for each node i in the message passing algorithm, iteratively:
for each node j linked to node i:
combine incoming messages to form an intermediate vector I,
determining an output message vector M by:
considering an auxiliary seed vector S; a pairwise function r=d(x,y), where r, x, y are real numbers; and an index distance Δ≧2^floor(log 2(N)), N being the length of message vector M and the seed vector S,
initializing S as S(m)=m for each element m of vector S,
for each index p of the vector I and while Δ>0,computing in parallel, by:
considering the set of all indices within distance Δ from given index p, augmented by index p, for every index k belonging to this set, computing its distance from p using the function: d(p,k)+I(S(k)) in order to determine the minimum distance,
computing S(p)=S(n), n being the index corresponding to this minimum distance, and
computing Δ=floor(Δ/2),
determining the message vector M by computing M(m)=I(S(m))+d(m,S(m)) for each element m of vector M,
communicating the vector M to node i.
2. The computer-implemented method according to claim 1 , wherein during the step of combining incoming messages, all incoming messages are combined except the one coming from j.
3. The computer-implemented method according to claim 1 , wherein after the step of determining an output message vector M, a normalization of messages is made.
4. A device comprising a non-transitory computer-readable storage medium encoded with computer-executable instructions which, when executed, efficiently perform a message passing algorithm comprising:
using a computer to perform the following:
for each node i in a message passing algorithm, iteratively:
for each node j linked to node i:
combine incoming messages to form an intermediate vector I,
determining an output message vector M by:
considering an auxiliary seed vector S, a pairwise function r=d(x,y), where r,x,y are real numbers, and an index distance Δ≧2^floor(log 2(N)), N being the length of message vector M and the seed vector S,
initializing S as S(m)=m for each element m of vector S,
for each index p of the vector I and while Δ>0, computing in parallel, by:
considering the set of all indices within distance Δ from given index p, augmented by index p, for every index k belonging to this set, computing its distance from p using the function: d(p,k)+I(S(k)) in order to determine the minimum distance,
computing S(p)=S(n), n being the index corresponding to this minimum distance, and
computing Δ=floor(Δ/2),
determining the message vector M by computing M(m)=I(S(m))+d(m,S(m)) for each element m of vector M,
communicating the vector M to node i.
5. The device according to claim 4 , wherein during the step of combining incoming messages, all incoming messages are combined except the one coming from j.
6. The device according to claim 4 , wherein after the step of determining an output message vector M, a normalization of messages is made.
7. The device according to claim 4 , wherein the method is implemented in a CUDA(Compute Unified Device Architecture) used to exploit a set of SIMD (Single Instruction Multiple Data) coprocessors.
8. The device according to claim 7 , wherein instructions are programmed in the thread level, threads being executed concurrently in blocks within which they share memory in order to communicate, the sum of all blocks forming a grid of threads that executes a common set of instructions called kernel.
9. The computer-implemented method according to claim 2 , wherein after the step of determining an output message vector M, a normalization of messages is made.
10. The device according to claim 5 , wherein after the step of determining an output message vector M, a normalization of messages is made.
11. The device according to claim 5 , wherein the method is implemented in a CUDA (Compute Unified Device Architecture) used to exploit a set of SIMD (Single Instruction Multiple Data) coprocessors.
12. The device according to claim 6 , wherein the method is implemented in a CUDA (Compute Unified Device Architecture) used to exploit a set of SIMD (Single Instruction Multiple Data) coprocessors.