ALCOMFT-TR-01-12

P. Sanders and R. Solis-Oba
How Helpers Hasten h-Relations
MPI. Work packages 1, 2 and 4. January 2001.

Abstract: We study the problem of exchanging a set of messages among a group of processors, using the model of simplex communication. Messages may consist of different numbers of packets. Let L denote the maximum number of packets that a processor must send and receive. If all the packets need to be delivered directly, at least (3/2)L communication steps are needed to solve the problem in the worst case. We show that by allowing forwarding, only (6/5)L+O(1) time steps are needed to exchange all the messages, and this is optimal. Our work was motivated by the importance of irregular message exchanges in distributed-memory parallel computers, but it can also be viewed as an answer to an open problem on scheduling file transfers posed by Coffmann, Garey, Johnsson, and LaPaugh in 1985.

Postscript file: ALCOMFT-TR-01-12.ps.gz (93 kb).