Abstract
We present a round-optimal algorithm for broadcasting n indivisible blocks of data over p processors communicating in a regular, logarithmic degree circulant graph pattern. This broadcast algorithm immediately leads to partly new, likewise round-optimal algorithms for the reduction to root, all-to-all broadcast (allgatherv) and irregular and regular reduce-scatter operations. The broadcast algorithm relies on block schedules with certain properties which we indicate can be computed optimally in O(\log p) operations per processor without communication. The communication pattern and algorithms are attractive for implementing most of the standard, dense collective operations of MPI.
Bio
Jesper Larsson Träff is professor for Parallel Computing at TU Wien (Vienna University of Technology) since 2011. From 2010 to 2011 he was guest professor for Scientific Computing at the University of Vienna. From 1998 until 2010 he was working at the NEC Laboratories Europe in Sankt Augustin, Germany on efficient implementations of MPI for NEC vector supercomputers; this work led to a doctorate (Dr. Scient.; Habilitation) from the University of Copenhagen in 2009. From 1995 to 1998 he spent four years as PostDoc/Research Associate in the Algorithms Group of the Max-Planck Institute for Computer Science in Saarbrücken, and the Efficient Algorithms Group at the Technical University of Munich. He received an M.Sc. in computer science in 1989, and, after two interim years at the industrial research center ECRC in Munich, a Ph.D. in 1995, both from the University of Copenhagen.