''Scaling Simulation of the Fusing-Restricted Reconfigurable Mesh''

J. Alberto Fernandez-Zepeda

Ramachandran Vaidyanathan

Jerry L. Trahan

IEEE Transactions on Parallel & Distributed Systems, vol. 9, no. 9, pp. 861-871, 1998


This paper deals with the ability of a model to adapt algorithm instances of different sizes to run on a given model size without significant loss of efficiency. The overhead in simulating a step of a large instance of the model on a smaller instance can quantify this ability. A reconfigurable mesh (R-Mesh) can use its bus structure as a computational resource, presenting an obstacle to efficiently scaling down algorithms to run on a smaller R-Mesh. We construct a scaling simulation of a Fusing-Restricted Reconfigurable Mesh (FR-Mesh), a version of the R-Mesh. The overhead of this simulation depends only on the simulating machine size and not on the simulated machine size. Previously, the R-Mesh was not known to admit such a simulation overhead without significantly reducing its computational power. The small overhead holds importance for flexibility in algorithm design and for running algorithms with various input sizes on an available model of given size. The results of this paper extend to a variety of concurrent write rules and also translate to an improved scaling simulation of an unrestricted R-Mesh.

This work was supported in part by the National Science Foundation under grant number CCR-9503882 and the Louisiana Board of Regents through the Louisiana Education Quality Support Fund under contract number LEQSF(1994-96)-RD-A-07.