''Scaling Multiple Addition and Prefix Sums on the
Jerry L. Trahan and Ramachandran Vaidyanathan
Information Processing Letters,
vol. 82, no. 6, pp. 277-282, 2002
Multiple addition is the problem of adding N b-bit integers.
Prefix sums and multiple addition play fundamental roles in
many algorithms, particularly on the reconfigurable mesh
Scaling algorithms on the R-Mesh to run with the same or
increased efficiency on fewer processors is a challenging and
In this paper, we present algorithms that scale with increasing
efficiency for multiple addition, prefix sums, and
Along the way, we obtain an improved multiple addition algorithm.
This work was supported in part by
the National Science Foundation under grant number CCR-0073429.