Résumé | Increasing the performance of HPC and cloud environments involves to optimize the reduction phase, which is present in many applications. This optimization problem arises in at least two contexts: the MPI_Reduce collective function that allows to combine several arrays by performing a pairwise reduction operation on every arrays; and, the Reduce part of MapReduce applications, where a single result is generated from several inputs. By assuming the associativity of the reduction operation, it is possible to determine a spanning tree that schedules data transfers and reduction operations. Two algorithms are proposed for the cases where the number of reducers or the number of concurrent transfers is bounded. When there is no limitation, two specific optimal spanning trees are also characterized for specific transfer and computation costs.
Orateur: Louis-Claude Canon |