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

[Jesper Larsson Traeff]

On Mon, Jan 12, 2009 at 02:05:47PM -0500, Torsten Hoefler wrote:
> 
> > > 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?
> yes, but I guess controlling each call is not necessary. However,
> controlling the order of operations might be necessary to ensure
> correctness. But I don't know a particular app, so the whole argument is
> weak. I just want to discuss the issue and either understand why we
> don't have this feature or discuss its addition. My point is that there
> are (limited) optimization possibilities and that we limit ourselves
> enourmously by enforcing the same reduction order for all float/double
> operations and all user-defined operations in MPI-2.1. If associativity
> would be an explicit property of a user-defined operation, then we could
> apply dynamic optimizations based on arrival time, which we can't right
> now (side-note: we can do this for associative ops, such as all ops on
> non-fp types). 
> 
maybe I misunderstand you, but I don't see that allowing operators to
be explicitly non-associative would give you more freedom for optimizations.
Doesn't your arguments above show that there are rather less than for 
associative ops? But maybe it is better to discuss this at the next meeting?

If your argument is: "there are natural (user-defined) operators in app 
A, B and C that are mathematically not associative, and users want to perform 
reductions with these" - then I agree that MPI is missing something.

Maybe an "MPI_Op_create_nonassoc(...)"? (I also don't think an extra function
for setting the associativity of an already defined function fits with MPI;
although a function like MPI_Op_use_some_special_canonical_order(MPI_Op f),
where f could be a user as well as a predefined MPI_Op,
could perhaps make sense, and would allow to control the evaluation order 
each time MPI_Reduce/MPI_Allreduce/... is called, but then such a function
would either have to be collective or users would be required to use it
consistently, ... that is, many complications)

Note also that non-associativity does put some non-trivial burden on 
implementers: for non-associative (with or without hyphen?) operators, 
a special algorithm that does the reduction in the sequential order is needed

Jesper