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


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.