FAST COLLECTIVE COMMUNICATION BY PACKETS IN THE POSTAL MODEL

Collective communication operations play an important role in message- passing systems and have been extensively investigated. We study two w idely used collective communication operations: gossiping and all-to-a ll personalized communication. We assume the multiport postal model of communication that seems particularly suited for developing fast and portable algorithms on current technology parallel computers. Unlike m ost of the previous work on the subject, we assume that processors com municate by sending messages of limited size. Indeed, when the maximum size of a message is fixed, the number of rounds required by a commun ication algorithm gives a realistic measure of the performance of the algorithm. We provide an optimal algorithm for the gossiping operation and an almost-optimal algorithm for the all-to-all personalized commu nication operation. (C) 1998 John Wiley & Sons, Inc.