Efficient all-to-all broadcast schemes in distributed-memory parallel computers

Distributed-memory parallel computers refer to parallel computers in which each processor has its own private memory. In such a system, processors communicate information by exchanging messages via the interconnection network rather than storing it in shared memory. One of the important communication methods in such systems is data broadcasting. All-to-all broadcasting is the process in which each processor sends its message to all other processors, and receives messages from all other processors in the system. Two complexity elements are usually considered when measuring the performance of a distributed-memory parallel model: time complexity and message complexity. In this paper we develop an efficient communication scheme to reduce both the communication time and the message complexity in the star network model under the half-duplex and full-duplex communication capability. The complexity measures of our scheme are compared against known bounds to verify the efficiency of the suggested scheme.