A methodology for devising optimal all-port all-to-all broadcast algorithms in 2-dimensional tori

All-to-all broadcast is a collective communication in a network with the constraint that every node must send to each other certain piece of its data. This paper reports a methodology to devise all-port efficient algorithms for such communication in multidimensional tori. Efficiency criteria being minimum steps of no duplicated data exchange while balancing the communication links-load. Resulting algorithms are message combining algorithms. To complete an all-to-all broadcast these algorithms require the number of data exchange steps in terms of link hops to be equal to the diameter of the interconnection network. The number of data exchanged at each step varies as a Gaussian curve whose maximum equals the half of the network diameter per link.