[Mpi-22] [MPI Forum] #96: MPI_OP_CREATE and associativity

Jesper Larsson Traeff traff at [hidden]
Mon Jan 12 10:11:24 CST 2009



On Mon, Jan 12, 2009 at 10:36:58AM -0500, Torsten Hoefler wrote:
> 
> To optimize this, and retain the order of summation, one could employ
> similar strategies as for gather to reduce the messaging complexity
> (e.g. from O(N) to O(log_N)). 
Since you cannot do anything on intermediate nodes in your gather tree,
the message complexity is O(Nm), m: size of vector... You only gain 
something for small problems by reducing the number of receives at the root. 
In the case where you use some dynamic algorithm where things may arrive in
some unspecified order, you'd again have to buffer the contributions from
the processes before you can do the reduction.

> yes, they can still be treated as associative (for all internal types),
> but thet user should have a chance to define non-associative reductions.
> 
In the apps you refer to, I guess they often want an MPI_SUM on an MPI_FLOAT
done in some particular order with a particular bracketing. Thus, what
you need is some ability to control each individual MPI_Reduce call?

Jesper



More information about the Mpi-22 mailing list