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 ...
详细信息
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. (C) 2002 Elsevier Science (USA).
暂无评论