[Back]

J. Träff:
"(Poly)Logarithmic Time Construction of Round-optimal n-Block Broadcast Schedules for Broadcast and irregular Allgather in MPI";
Report for CoRR - Computing Research Repository; Report No. arXiv:2205.10072, 2022; 18 pages.

We give a fast(er), communication-free, parallel construction of optimal communication schedules that allow broadcasting of n distinct blocks of data from a root processor to all other processors in 1-ported, p-processor networks with fully bidirectional communication. For any p and n, broadcasting in this model requires n−1+⌈log ₂ p⌉ communication rounds. In contrast to other constructions, all processors follow the same, circulant graph communication pattern, which makes it possible to use the schedules for the allgather (all-to-all-broadcast) operation as well. The new construction takes O(log ³ p) time steps per processor, each of which can compute its part of the schedule independently of the other processors in O(logp) space. The result is a significant improvement over the sequential O(plog ² p) time and O(plogp) space construction of Träff and Ripke (2009) with considerable practical import. The round-optimal schedule construction is then used to implement communication optimal algorithms the broadcast and (irregular) allgather collective operations as found in MPI (the \emph{Message-Passing Interface}), and significantly and practically improve over the implementations in standard MPI libraries (\texttt{mpich}, OpenMPI, Intel MPI) for certain problem ranges. The application to the irregular allgather operation is entirely new.