hide
Free keywords:
-
Abstract:
We study the problem of exchanging a set of messages among a group of
processors, where messages may consist of different numbers of
packets. We consider the model of half-duplex communication. Let
$\Lmax$ denote the maximum number of packets that a processor must
send and receive. If all the packets need to be delivered directly,
at least $\frac{3}{2}\Lmax$ communication steps are needed to solve
the problem in the worst case. We show that by allowing forwarding,
only $\frac{6}{5}\Lmax + \Oh{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.