DocumentCode :
1451492
Title :
Efficient algorithms for the reduce-scatter operation in LogGP
Author :
Iannello, Giulio
Author_Institution :
Dipartimento di Inf. e Sistemistica, Naples Univ., Italy
Volume :
8
Issue :
9
fYear :
1997
fDate :
9/1/1997 12:00:00 AM
Firstpage :
970
Lastpage :
982
Abstract :
We consider the problem of efficiently performing a reduce-scatter operation in a message passing system. Reduce-scatter is the composition of an element-wise reduction on vectors of n elements initially held by n processors, with a scatter of the resulting vector among the processors. In this paper, we present two algorithms for the reduce-scatter operation, designed in LogGP. The first algorithm assumes an associative and commutative reduction operator and it is optimal in LogGP within a small constant factor. The second algorithm allows the reduction operator to be noncommutative, and it is asymptotically optimal when values to be combined are large arrays. To achieve these results, we developed a complete analysis of both algorithms in LogGP, including the derivation of lower bounds for the reduce-scatter operation, and the study of the m-item version of the problem, i.e., the case when the initial elements are vectors themselves. Reduce-scatter has been included as a collective operation in the MPI standard message passing library, and can be used, for instance, in parallel matrix-vector multiply when the matrix is decomposed by columns. To model a message passing system, we adopted the LogGP model, an extension of LogP that allows the modeling of messages of different length. While this choice makes the analysis somewhat more complex, it leads to more realistic results in the case of gather/scatter algorithms
Keywords :
message passing; parallel algorithms; LogGP; lower bounds; m-item version; message passing system; parallel matrix-vector multiply; reduce-scatter operation; Algorithm design and analysis; Computer Society; Libraries; Matrix decomposition; Message passing; Parallel algorithms; Performance analysis; Scattering; Telephony;
fLanguage :
English
Journal_Title :
Parallel and Distributed Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
1045-9219
Type :
jour
DOI :
10.1109/71.615442
Filename :
615442
Link To Document :
بازگشت