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