28th Annual IEEE International Conference on Local Computer Networks (LCN'03)
A Methodology for Devising Optimal All-port All-to-all Broadcast Algorithms in 2-Dimensional Tori
Bonn/K?nigswinter, Germany
October 20-October 24
ISBN: 0-7695-2037-5
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.
Index Terms:
Distributed Memory Parallel Computers, Multidimensional tori, all-to-all broadcast, NODUP, Store-and-Forward routing, Message combining
Citation:
Jean-Pierre Jung, Ibrahima Sakho, "A Methodology for Devising Optimal All-port All-to-all Broadcast Algorithms in 2-Dimensional Tori," lcn, pp.558, 28th Annual IEEE International Conference on Local Computer Networks (LCN'03), 2003