Journal article
Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines
Journal of parallel and distributed computing, v 62(4), pp 517-543
01 Apr 2002
Abstract
The problem of designing efficient parallel algorithms for summing and prefix summing for certain classes of the LogP model is studied. We present optimal algorithms for summing and show that any optimal summing algorithm must have a certain inherent structure. Moreover, we present optimal or near-optimal algorithms for prefix summing for both non-commutative and commutative binary operators. Furthermore, we show that the optimal algorithms for prefix summing for these two types of operators are not equivalent.
Metrics
1 Record Views
Details
- Title
- Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines
- Creators
- Eunice E. Santos - Virginia Tech
- Publication Details
- Journal of parallel and distributed computing, v 62(4), pp 517-543
- Publisher
- Elsevier Inc
- Number of pages
- 27
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- School of Engineering
- Web of Science ID
- WOS:000175601500002
- Scopus ID
- 2-s2.0-0036106373
- Other Identifier
- 991022207144904721