Talks and Poster Presentations (without Proceedings-Entry):
"On Optimal Trees for Irregular Gather and Scatter Collectives";
Talk: Kolloquium Mathematische Informatik, Goethe-Universität Frankfurt am Main,
Frankfurt am Main, Germany (invited);
Gather and scatter collectives are useful operations for distributed-memory parallel computers and therefore included in interfaces like MPI. While simple, optimal algorithms for the regular (homogeneous) variants are known and also implemented for many communication and system models, the irregular (heterogeneous) variants of the problems where different processors may have different amounts of data are much more difficult and have been much less studied. In the first part of the talk, we present recent, simple, logarithmic round and volume optimal algorithms for the irregular gather and scatter problems that can be easily implemented in and for MPI. In the second part of the talk we discuss the complexity of finding truly time optimal algorithms for the problems. We show that under certain, natural ordering constraints on data and processors, optimal communication trees can be found in polynomial time, although at some expense, whereas finding optimal trees without the ordering constraints is an NP-complete problem.
Created from the Publication Database of the Vienna University of Technology.