[mpich-discuss] Create account for bug tracker

[Dave Goodell]

A tree-based scan pattern can cause a problem, for example.  Basically, the MPI library is allowed to play with the associativity of the operations in order to provide better performance.  The operation provided in the MPI standard example is not associative:

(w,j) = (u,i)*(v,j), with w={ u+v if i=j, v if i!=j }

i,j are booleans (0 or 1)

If this operator is associative, then it must hold that:

((a,x)*(b,y))*(c,z) = (a,x)*((b,y)*(c,z)), for all (a,x),(b,y),(c,z)

So here's a counterexample proving non-associativity:

(a,x) = (a,0)
(b,y) = (b,1)
(c,z) = (c,0)

The left-hand side of the equation yields "(c,0)", while the right-hand side yields "(a+c,0)", which are clearly not equal.

The scheme that I worked out a while ago to deal with this problem involves adding a third variable to the pair, turning it into a triple.  Unfortunately I left my notes containing the scheme at home, so I'll have to send an explanation later.  In the meantime, you may wish to use the traditional edge-triggered version of the operator (cribbed from Jesper's proposed ticket https://svn.mpi-forum.org/trac/mpi-forum-web/ticket/28):

(val0 , index0)+(val1, index1) = [if index1=0 then (value0+value1 , index) else (value1 , index), where index is set to 1 if index0=1 and set to index1 otherwise]

-Dave

On Dec 18, 2012, at 9:27 PM CST, n n wrote:

> I do not actually need this functionality, but can you show example of robust code, which will work for mpi_scan in all cases?
> And can you clarify, why the order of output is not preserved, as in openmpi version?
> 
> On Wed, Dec 19, 2012 at 1:52 AM, Dave Goodell <goodell at mcs.anl.gov> wrote:
>> This scan operator is known to be buggy, unfortunately.  It will not do the correct thing for many (entirely valid) scan implementation patterns.  It's something that ought to be fixed in the next version of the MPI standard (it fell through the cracks in the MPI-3 process).
>> 
>> Do you actually need this functionality?  If so, I can describe how to implement it in a way that will be robust.  Alternatively, most segmented scan algorithms assume an "edge triggered" segmented scan, rather than a "level" triggered one like what is described in the MPI standard.
>> 
>> -Dave