Title :
Optimal and efficient parallel algorithms for summing and prefix summing
Author :
Santos, Eunice E.
Author_Institution :
Dept. of Comput. Sci. & Electr. Eng., Lehigh Univ., Bethlehem, PA, USA
Abstract :
The author considers the problem of designing efficient parallel algorithms for summing and prefix summing. The author presents optimal algorithms for summing on a latency-dependent distributed-memory model and shows that any optimal summing algorithm must have an inherent structure. Moreover, the author presents optimal or near-optimal algorithms for prefix summing for both non-commutative and commutative binary operators. Furthermore, the author shows that the optimal algorithms for prefix summing for these two types of operators are not equivalent
Keywords :
distributed memory systems; mathematical operators; parallel algorithms; commutative binary operators; efficient parallel algorithms; inherent structure; latency-dependent distributed-memory model; near-optimal algorithms; noncommutative binary operators; optimal algorithms; optimal parallel algorithms; optimal summing algorithm; prefix summing; summing; Algorithm design and analysis; Binary trees; Commutation; Computational modeling; Computer science; Concurrent computing; Costs; Delay; Parallel algorithms; Phase change random access memory;
Conference_Titel :
Parallel and Distributed Processing, 1996., Eighth IEEE Symposium on
Conference_Location :
New Orleans, LA
Print_ISBN :
0-8186-7683-3
DOI :
10.1109/SPDP.1996.570375
