OPTIMAL COMMUNICATION ALGORITHMS ON STAR GRAPHS USING SPANNING TREE CONSTRUCTIONS

In this paper we consider three fundamental communication problems on the star interconnection network: the problem of simultaneous broadcas ting of a message from every node to all other nodes, or multinode bro adcasting, the problem of a single node sending distinct messages to e ach one of the other nodes, or single-node scattering, and finally the problem of each node sending distinct messages to every other node, o r total exchange. All of these problems are studied under two differen t assumptions: the assumption that each node can transmit a message of fixed length to one of its neighbors and simultaneously receive a mes sage of fixed length from one of its neighbors (not necessarily the sa me one) at each time step, or single-link availability, and the assump tion that each node can exchange messages of fixed length with all of its neighbors at each time step, or multiple-link availability. In bot h cases communication is assumed to be bidirectional. The cases where the originating processor wishes to send only one or more than one mes sage to each one of the other processors are distinguished when necess ary. Lower bounds are derived for these problems under the stated assu mptions, and optimal algorithms are designed in terms of both time and number of message transmissions. Although the algorithms derived for the first two problems require the minimum amount of the above resourc es, the algorithm designed for the total exchange problem is optimal o nly to within a multiplicative factor. All the communication algorithm s presented in this paper are based on the construction of spanning tr ees with special properties on the star graph to fit different communi cation needs. A special framework is developed to facilitate the const ruction of these trees. The scheduling disciplines that lead to optima l results in each case are described. (C) 1995 Academic Press, Inc.