''Improved Scaling Simulations of the General Reconfigurable Mesh''

J. Alberto Fernandez-Zepeda

Ramachandran Vaidyanathan

Jerry L. Trahan

Proc. 6th Reconfig. Arch. Workshop (Parallel and Distributed Processing; Lect. Notes Comp. Sci. #1586), (IEEE, San Juan, PR, April 1999), pp. 616-624.


The reconfigurable mesh (R-Mesh) has drawn much interest in recent years, due in part to its ability to admit extremely fast algorithms for a large number of problems. For these algorithms to be useful in practice, the R-Mesh must be scalable; that is, any algorithm designed for a large R-Mesh should be able to run on a smaller R-Mesh without significant loss of efficiency. This amounts to designing a ``scaling simulation'' that simulates an arbitrary step of an N x N R-Mesh on a smaller P x P R-Mesh in O((N^2 / P^2) f(N,P)) steps; f(N,P) is a non-decreasing function representing the simulation overhead. The aim is to minimize this overhead, ideally to a constant.

In this paper, we present two scaling simulations for the general (unconstrained) R-Mesh. The overhead of both simulations is smaller than the log Nlog(N/P) overhead of the previous fastest scaling simulation. The first simulation has an overhead of log Plog(N/P) Moreover, the log P factor of this overhead is due only to the time for leader election on a P x P R-Mesh. The second simulation has an overhead of log N, using a CREW LRN-Mesh (a weaker version of the General R-Mesh) as the simulating model; prior simulations needed concurrent write.

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