Träff, J. L. (2022). Fast(er) Construction of Round-optimal n-Block Broadcast Schedules. In Proceedings IEEE International Conference on Cluster Computing (CLUSTER 2022) (pp. 142–151). IEEE. https://doi.org/10.1109/CLUSTER51413.2022.00028
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 full bidirectional communication. For any p and n , broadcasting in this model requires n-1+ceil(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^3 p) time steps per processor, each of which can compute its part of the schedule independently of the other processors in O(log p) space. The result is a significant improvement over the sequential O(p log^2 p) time and O(p log p) 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 for the broadcast and (irregular) allgather collective operations as found in MPI (the Message-Passing Interface), and significantly and practically improve over the implementations in standard MPI libraries for certain problem ranges. The application to the irregular allgather operation is entirely new.
Computer Engineering and Software-Intensive Systems: 90% Computer Science Foundations: 10%