''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


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.