''Using Bus Linearization to Scale the
Reconfigurable Mesh''
J. Alberto Fernandez-Zepeda
Ramachandran Vaidyanathan
Jerry L. Trahan
Journal on Parallel and Distributed Computing,
vol. 62, no. 4, pp. 495-516, 2002.
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. The unrestricted
R-Mesh creates a great variety of bus shapes that facilitate
algorithm design and reduce running time. In this paper, we present a
``bus linearization'' procedure that transforms an arbitrary
non-linear bus configuration of an R-Mesh into an equivalent
acyclic linear bus configuration implementable on a Linear
R-Mesh (LR-Mesh), a weaker version of the unrestricted
R-Mesh. This procedure gives an algorithm designer the liberty
of using buses of arbitrary shape, while automatically translating the
algorithm to run on a simpler platform.
We illustrate our bus linearization method through two important
applications. The first leads to a faster scaling simulation for the
unrestricted R-Mesh. This scaling simulation has an overhead
of log N (smaller than the log P log(N/P) overhead of the
previous fastest scaling simulation), and uses an exclusive write
LR-Mesh as the simulating model; prior simulations needed
concurrent write. The second application adapts algorithms designed
for R-Meshes to run on models with pipelined optical buses.
This work was supported in part by
the National Science Foundation under grant number CCR-9503882.