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

[Torsten Hoefler]

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




* 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://lists.mpi-forum.org/pipermail/mpi-22/attachments/20090112/a15f5b3f/attachment.pgp>