Binomial tree broadcast in remote memory access model
Alexey A. Paznikov · Vestnik Tomskogo gosudarstvennogo universiteta Upravlenie vychislitel naya tekhnika i informatika · 2024
This article introduces a broadcast (one-to-all scheme) algorithm, designed to enhance the efficiency of utilizing Remote Memory Access (RMA), a one-sided communication model within the MPI standard, for parallel programming in distributed computing systems. The algorithm leverages a binomial tree structure to organize interprocess interactions, a scheme widely employed for classic collective operations within the MPI standard. With logarithmic complexity, this algorithm proves to be more efficient than linear counterparts. The article also provides analytical complexity estimates within the LogP and LogGP models. Experimental results confirm the algorithm's advantages, although the ultimate efficiency depends on several factors, including the number of processes in the communicator, data transmission size, and the performance of the interconnect.