Collective communication such as scatter, gather, broadcast, and total exchange plays an important role on the performance of parallel and distributed processing. So far, several parallel collective communication algorithms have been studied in synchronous communication models, but it is necessary to design and analyze parallel algorithms using a more realistic communication model. This paper introduces an asynchronous communication model between processors, and evaluates the execution time of operations which include scatter, gather and some computations for data initially located at one processor. The results show that the execution time in sending data in a single direction is less than that of dual directions for asynchronous communication. This paper also introduces the logarithmic correction of the bisection communication tree, and evaluates the communication time of several instances.
This paper is available at Postscript.
Copyright 2000 ACM
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy
otherwise, to republish, to post on servers or to redistribute to lists,
requires prior specific permission and or fee.
SAC 2000 March 19-21 Como, Italy
(c) 2000 ACM 1-58113-239-5/00/003>...>$5.00