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

[Jesper Larsson Traeff]

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?

Thus, I think it is right that the standard requires the operators to
be associative. 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).

I therefore think this extension requires a lot more thought for it to
be "mathematically well-defined" and also otherwise make sense

Jesper

On Fri, Jan 02, 2009 at 05:26:48PM -0000, MPI Forum wrote:
> #96: MPI_OP_CREATE and associativity
> -------------------------------------+--------------------------------------
> Reporter:  htor                      |       Owner:  htor                 
>     Type:  Enhancements to standard  |      Status:  new                  
> Priority:  Forum feedback requested  |   Milestone:  2009/02/09 California
>  Version:  MPI 2.2                   |    Keywords:                       
> -------------------------------------+--------------------------------------
>  Information about associativity can not be attached to user-defined
>  operations. This prevents any dynamic reordering of trees, based on
>  different arrival patterns (strongly recommended by the Advice to
>  Implementors in Sec. 5.9.1). Architecture-dependent associativity can be
>  derived for predefined types (e.g., MPI_INT is associative while MPI_FLOAT
>  is not on most architectures). No such statements can be made about user-
>  defined operations. This seems to be mathematically incomplete.
> 
>  == History ==
>  This has been the status quo since MPI-1.
> 
>  == Proposed Solution ==
>  Add an additional (bool) in-argument to MPI_OP_CREATE that indicates if
>  the operation is associative or not.
> 
>  == Impact on Implementations ==
>  low, nothing needs to be changed and the argument can be ignored. However,
>  it reveals rather interesting optimization possibilities at large scale.
> 
>  == Impact on Applications / Users ==
>  low, an additional argument can be supplied which could just be "false" to
>  retain the status quo.
> 
>  == Alternative Solutions ==
>  none
> 
>  == Entry for the Change Log ==
>  added associativity argument to MPI_OP_CREATE
> 
> -- 
> Ticket URL: <https://svn.mpi-forum.org/trac/mpi-forum-web/ticket/96>
> MPI Forum <https://svn.mpi-forum.org/>
> MPI Forum