''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.
Abstract:
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.