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

#### Abstract:

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 *N*log(*N*/*P*)
overhead of the previous fastest scaling simulation.
The first simulation has an overhead of log *P*log(*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.