''Improved Scaling Simulations of the
General Reconfigurable Mesh''
J. Alberto Fernandez-Zepeda
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
The aim is to minimize this overhead, ideally to a constant.
In this paper, we present two scaling simulations for the general
The overhead of both simulations is smaller than the
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.