mpiforumbot
commented
8 years ago Originally by gropp on 2008-10-26 10:26:38 -0500
All new routines proposed for 2.2 must have an open-source implementation. In addition, a clear benefit must be demonstrated. In addition, this will need a specific proposal (all text, page/line numbers).
Originally by traff on 2008-10-10 08:15:19 -0500
New binary operators (for segmented scans etc.) on (value,index) pair datatypesSep 8 2008 straw vote:
|| Yes || Maybe || No for 2.2 || Abstain || || 1 || 25 || 0 || 7 ||
Author: Jesper Larsson Träff
Description
It is proposed to exploit the (value,index) pair-datatypes for a few other useful types of operation, namely segmented scans, selective reductions/scans, and "consensus" functions. Global, segmented scans are useful in many applications. The global minimum and maximum operations with indicator can save computations when a global minimum/maximum is needed together with an indication of whether all processes have reached the miminum/maximum.
History
Proposed Solution
The following four binary operation types all operate on (value,index) datatypes
MPI_FLOAT_INTetc. They can be used with any of the reduction collectivesMPI_Reduce,MPI_Allreduce,MPI_Reduce_scatter(MPI_Reduce_scatter_block),MPI_ScanandMPI_Exscan.MPI_SEGMENTED_SUM/PROD/MIN/MAX/.../BXORis defined by the associative operation (val,,0,, , index,,0,,)+(val,,1,, , index,,1,,) = [if index,,1,,=0 then (value,,0,,+value,,1,, , index) else (value,,1,, , index), where index is set to 1 if index,,0,,=1 and set to index,,1,, otherwise]. The indices are supposed to mark the start of segments (index=1). Thus if the second argument is a start of a segment, no reduction is performed, otherwise the two arguments are combined, and if the first argument is the start of a segment, the result will likewise be marked as starting a segment.When used with
MPI_ScanorMPI_ExscantheMPI_SEGMENTED_SUMoperation computes for the process with rankithe (inclusive or exclusive) sum of the contributions from the highest ranked processjwithj<ithat starts a segment (index=1). When used with global reductionsMPI_Reduceetc. the result will be the sum from the highest ranked process starting a segment up tosize-1.MPI_SELECTSUM/PROD/MIN/MAX/.../BXORis defined by the associative operation (val,,0,, , index,,0,,)+(val,,1,, , index,,1,,) = [if index,,0,,=1 and index,,1,,=1 then (val,,0,,+val,,1,, , 1), else if index,,0,,=1 then (val,,0,, , 1), else (val,,1,, , index,,1,,)]. The indices are supposed to indicate elements that are selected for reduction. A global sum (if used withMPI_Reduceetc.) or scan (if used withMPI_Scanetc.) is computed over the selected elements only.MPI_ALL_MINis defined by the associative operation (val,,0,, , index,,0,,)+(val,,1,, , index,,1,,) = (min(val,,0,, , val,,1,,),[1 if val,,0,,=val,,1,, otherwise 0]). It computes a minimum over the two values, and sets the index if the two values are identical. When used with a reduction collective, a global minimum can be computed and at the same time the index will indicate whether all processes contributed the same value.MPI_ALL_MAXis analogous toMPI_ALL_MINwith maximum instead of minimum.Impact on Implementations
Some implementation effort, but not huge.
Impact on Applications / Users
It is an addition, so no direct consequence.
Alternative Solutions
The operations can all (with some effort) be implemented as user-defined operations - for instance in a library. The arguments in favor are convenience and efficiency.
Entry for the Change Log