Copyright ACM, 2000

SAC2000 Interactive Programme

Paper PD-18

Scatter and Gather Operations on an Asynchronous Communication Model

Susumu Shibusawa, Hiroyuki Makino, Shigeki Nimiya and Jun-ichi Hatta Ibaraki University


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