''Scaling Multiple Addition and Prefix Sums on the
Reconfigurable Mesh''
Jerry L. Trahan and Ramachandran Vaidyanathan
Information Processing Letters,
vol. 82, no. 6, pp. 277-282, 2002
Abstract:
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
(R-Mesh).
Scaling algorithms on the R-Mesh to run with the same or
increased efficiency on fewer processors is a challenging and
important proposition.
In this paper, we present algorithms that scale with increasing
efficiency for multiple addition, prefix sums, and
matrix-vector multiplication.
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.