COMPLEXITY ANALYSIS OF BROADCASTING IN HYPERCUBES WITH RESTRICTED COMMUNICATION CAPABILITIES

Typical algorithms for broadcasting in distributed memory multicomputers generally assume that the communication cost between two neighboring processors is one. A more elaborate model uses a sum of a start-up time and a propagation time which is proportional to the message length. This paper proposes a new model which incorporates into the cost function the number of communication links simultaneously used by each processor, and thus can also take into account the possibility of communicating in a restricted number of directions. Under these new hypotheses, we analyze and discuss the cost of broadcasting, gossiping, scattering, and multiscattering algorithms in n-dimensional hypercubes. In each case, a lower bound is computed, an asymptotically optimal algorithm is given, and efficient algorithms for short messages are described. © 1992.