On Mon, Jan 12, 2009 at 03:19:12PM +0100, Jesper Larsson Traeff wrote:

For non-associative operators, in order to get any meaningful result, all you can do is to perform the operations in some predefined order (eg. rank-order) with a predefined "bracketing", ((((0+1)+2)+3)+...)+n). That seems to imply a linear time algorithm?

yes, it does but: linear time in computation, not in communication though! I know, this sounds counter-intuitive, but I heard from other scientists that there are fields that need this functionality (i.e., they can't guarantee numerical stability). Examples are mainly financial markets not so much simulations (most simulations are full of approximations anyway).

Thus, I think it is right that the standard requires the operators to be associative. That's exactly what I would criticize. Don't get me wrong, I am not pushing hard, but the argument that there seems limited optimization potential, and thus we should ignore mathematical properties seems weak.

Also, optimization potential is actually not that limited. The two implementations that I've seen just do a loop over all ranks: if(rank == 0) for(i=0;i<comm_size;i++) { MPI_Recv(buf, ...); sum += buf; } else MPI_Send(buf, ..., 0); 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)). Now one could argue that the user could just do MPI_Gather and then sum up the buffer, but what if the user doesn't have enough memory to store the entire array. An MPI implementation could use flow control and messaging algorithms in order to receive the data at rank 0 and reduce it piece by piece. Allreductions have even more potential.

Operators on FLOATs are usually treated as if they are associative (with some/many MPI libraries providing a possibility to switch to an algorithm with some predefined ordering and bracketing, for the cases where this is desired). yes, they can still be treated as associative (for all internal types), but thet user should have a chance to define non-associative reductions.

I therefore think this extension requires a lot more thought for it to be "mathematically well-defined" and also otherwise make sense why? Making it mathematically consistent is as simple as stated. Some optimization possibilities are shown above. What else is required?

Don't get me wrong, I'm not pushing and I'm happy to withdraw the ticket if the general consensus is that it's nonsense. It just seems rather inconsistent to me that associativity is just half-assumed. It is stated on page 160:44: "The operation op is always assumed to be associative." but then on page 161:1, we admit that we actually know the mathematical properties of IEEE-754 and say: "This may change the result of the reduction for operations that are not strictly associative and commutative, such as floating point addition.". And the following advice to implementors makes the situation even worse (I think), because it says that there is only one wrong result that is right for MPI. This advice also disables optimizations that could be done based on arrival patterns (as Bronis mentioned before). This would be much clearer if we would make the associativity explicit. But this might as well be an MPI-3 discussion. Best, Torsten -- bash$ :(){ :|:&};: --------------------- http://www.unixer.de/ ----- Torsten Hoefler | Postdoctoral Researcher Open Systems Lab | Indiana University 150 S. Woodlawn Ave. | Bloomington, IN, 474045, USA Lindley Hall Room 135 | +01 (812) 855-3608 *