✦ LIBER ✦
Scaling multiple addition and prefix sums on the reconfigurable mesh
✍ Scribed by Jerry L. Trahan; Ramachandran Vaidyanathan
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 77 KB
- Volume
- 82
- Category
- Article
- ISSN
- 0020-0190
No coin nor oath required. For personal study only.
✦ Synopsis
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.