An effective utilization of communication resources is crucial for good overall performance in multicomputer systems. All-to-all broadcasting problem, distribution of common message from each node to all other nodes, is one of the most popular communication patterns on multicomputer systems. In this thesis, we consider all-to-all broadcasting problems with d-port communication model in 2-dimensional mesch. In d-port communication model, each node on multicomputer systems can receive and send messages with two or more nodes concurrently. We propose two optimal all-to-all broadcasting algorithms for mxn meshconfigured multicomputer systems. One is for model with the buffer size n. We prove this algorithm is optimal in the number of communication steps and has time complexity O(m+n-2). The other is for model with the buffer size 1. We propose the methods of embedding the ring and the tree on mxn meshes and design the algorithm based on these methods. We prove that the ring and the tree embedded on mxn meshes using these methods are edge-disjoint and that the algorithm has the Time complexity O((mm-1)/2). This algorithm is optimal in the number of communication steps.
