''On Designing Implementable Algorithms for the Linear Reconfigurable Mesh''
Hatem M. El-Boghdadi
Ramachandran Vaidyanathan
Jerry L. Trahan
Suresh Rai
Proc. Int'l. Conf. Parallel and Distributed Processing Techniques and Applications,
2003, pp. 241-246.
Abstract:
Although algorithms for the reconfigurable mesh (R-Mesh) are fast,
they are difficult to implement because most algorithms on
N inputs employ buses that span at least N processors.
On such buses, the constant bus-delay assumption, that is
central to all reconfigurable algorithms, does not hold.
In this paper we show that a large class of fundamental
algorithms in the Linear R-Mesh (LR-Mesh) model can be
efficiently implemented using limited delay buses.
We introduce a new measure of bus delay, called ``bends-cost,''
and give an LR-Mesh implementation for which bends-cost
is a faithful measure of bus delay.
Next, we show that an important class of LR-Mesh algorithms
(that includes algorithms for prefix sums, multiple addition,
and sorting) can be implemented efficiently using buses with
at most D delay, where D is a parameter of the implementation.
In particular, if D is arbitrarily small, but polynomial
in the problem size, then the running times of the
algorithms with limited delay buses are to within a
constant of their idealized LR-Mesh counterparts.
We also present results for less restricted
versions of the LR-Mesh.
This work was supported in part by
the National Science Foundation under grant number CCR-0073429.