Transparent Neutral Element Elimination in MPI Reduction Operations

We describe simple and easy to implement MPI library internal functionality that enables MPI

reduction operations

to be performed more efficiently with increasing sparsity (fraction of neutral elements for the given operator) of the input (and intermediate result) vectors. Using this functionality we give an implementation of the

MPI_Reduce

collective operation that completely transparently to the application programmer exploits sparsity of both input and intermediate result vectors. Experiments carried out on a 64-core Intel Nehalem multi-core cluster with InfiniBand interconnect show considerable and worthwhile improvements as the sparsity of the input grows, about a factor of three with 1% non-zero elements which is close to best possible for the approach. The overhead incurred for dense vectors is negligible when compared to the same implementation not exploiting sparsity of input and intermediate results. The implemented

SPS_Reduce

function is for both very small and large vectors faster than the native

MPI_Reduce

of the used MPI library, indicating that the improvements reported are not artifacts of suboptimal reduction algorithms.