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