Efficient algorithms for all-to-all communications in multiport message-passing systems
Jehoshua Bruck, Ching‐Tien Ho, Shlomo Kipnis, Eli Upfal, Derrick Weathersby · IEEE Transactions on Parallel and Distributed Systems · 1997
We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast). We assume a model of a fully connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair. We also assume that each processor has k/spl ges/1 ports, through which it can send and receive k messages in every communication round. The complexity measures we use are independent of the particular system topology and are based on the communication start-up time, and on the communication bandwidth.