To get a desired performance using multicomputers, an efficient communication algorithm reflecting the characteristics of the interconnection topology is highly desirable. Among all the communication patterns on multicomputers, all-to-all broadcasting is one of the most popular communication patterns. In all-to-all broadcasting, all the nodes in the multicomputers want to send their own messages to all the other nodes and receive messages from all the other nodes for the sharing of some useful informations.
In this thesis, we firstly compute the lower bound of communication steps of all-to-all broadcasting on the torus topology with respect to the size of the communication buffers of each nodes. Secondly, we suggest an all-to-all broadcasting algorithm that satisfy such lower bound. The effect of the size of communication buffer on the communication time of all-to-all broadcasting is also analyzed.
