Optimal Broadcast Schedules in Logarithmic Time with Applications to Broadcast, Reduction, All-Broadcast and All-Reduction

We give optimally fast O (log p ) time (per processor) algorithms for computing round-optimal broadcast schedules for message-passing parallel computing systems. This affirmatively answers difficult questions posed in a SPAA 2022 BA and a CLUSTER 2022 paper. We observe that the computed schedules and circulant communication graph can likewise be used for reduction, all-broadcast and all-reduction as well, leading to new, round-optimal algorithms for these problems. These observations affirmatively answer open questions posed in a CLUSTER 2023 paper. The problem is to broadcast n indivisible blocks of data from a given root processor to all other processors in a (subgraph of a) fully connected network of p processors with fully bidirectional, simultaneous send-receive, one-ported communication capabilities. In this model, \(n-1+\lceil \log _2 p\rceil\) send-receive communication rounds are required. Our new algorithms work for any number of processors p , and compute for each processor in the network receive and send schedules each of size \(\lceil \log _2 p\rceil\) that determine uniquely in O (1) time for each communication round the new block that the processor will receive, and the already received block it has to send. Schedule computations are done independently per processor without communication. The broadcast communication subgraph is an easily computable, directed, \(\lceil \log _2 p\rceil\) -regular circulant graph also used elsewhere. We show how the schedule computations can be done in optimal time and space of O (log p ), improving significantly over previous results of \(O(p\log ^2 p)\) and O (log 3 p ), respectively, for any number of processors. The schedule computation and broadcast algorithms are simple to implement, but correctness and complexity are not obvious. By dividing a given input of m Bytes into n indivisible blocks, the schedules are used for new, best possible pipelined implementations of the MPI (Message-Passing Interface) collectives MPI_Bcast , MPI_Reduce , MPI_Allgatherv , and MPI_Reduce_scatter . Indicative, experimental results are given. The schedules can also be used for replicating large arrays on an EREW PRAM.