All-to-all broadcasting which is one of the most papular communication pattern on multicomputer system refers to the process of distributing common data from each node to all other nodes. In this thesis, we consider the all-to-all broadcasting problem on meshes and recursive circulants under the condition that at any step each node can send to and receive from its all adjacent nodes simultaneously.
This thesis first presents a new all-to-all broadcasting algorithm on arbitrary 2-dimensional meshes. Second, an optimal all-to-all broadcasting algorithm on arbitrary 3-dimensional meshes is also developed. Finally, an optimal all-to-all broadcasting algorithm on recursive circulants is presented.
