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


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.