''Implementing Prefix Sums and Multiple Addition Algorithms for the Reconfigurable Mesh on the Reconfigurable Tree Array''

Hatem M. El-Boghdadi

Ramachandran Vaidyanathan

Jerry L. Trahan

Suresh Rai

Proc. 2002 International Conference on Parallel and Distributed Processing Techniques and Applications, vol. 3, pp. 1068-1074.


Although algorithms for the reconfigurable mesh (R-Mesh) are fast, they are very difficult to implement because most algorithms employ buses whose delay is proportional to the problem size. On such buses, the constant bus-delay assumption that is central to all R-Mesh algorithms, does not hold. In this paper, we use the Reconfigurable Tree Array (RTA) structure which admits buses with much smaller delay. The RTA builds on that of the Self Reconfigurable Gate Array (SRGA). We implement R-Mesh algorithms for prefix sums of N bits and multiple addition of N b-bit integers on the RTA using buses with D >= log N delay. The RTA algorithms incur an overhead of O(log N / (log D - loglog N)) in time while using the same number of processors as the corresponding R-Mesh algorithms. In particular, if D = N^{epsilon} for an arbitrarily small constant epsilon > 0, then the running times of the RTA algorithms are to within a constant of their R-Mesh counterparts.

This work was supported in part by the National Science Foundation under grant number CCR-0073429.