COMPUTING GLOBAL COMBINE OPERATIONS IN THE MULTIPORT POSTAL MODEL

Consider a message-passing system of n processors, in which each proce ssor holds one piece of data initially. The goal is to compute an asso ciative and commutative reduction function on the n pieces of data and to make the result known to all the n processors. This operation is f requently used in many message-passing systems and is typically referr ed to as global combine, census computation, or gossiping. This paper explores the problem of global combine in the multiport postal model. This model is characterized by three parameters: n-the number of proce ssors, k-the number of ports per processor, and lambda-the communicati on latency. In this model, in every round r, each processor can send k distinct messages to k other processors, and it can receive k message s that were sent from k other processors lambda - 1 rounds earlier. Th is paper provides an optimal algorithm for the global combine problem that requires the least number of communication rounds and minimizes t he time spent by any processor in sending and receiving messages.