Using Bus Linearization to Scale the Reconfigurable Mesh
Using Bus Linearization to Scale the Reconfigurable Mesh
复制标题
使用总线线性化来缩放可重构网格
DOI：
10.1006/jpdc.2001.1810
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
J. Trahan
中科院分区：
文献类型：
--
作者：
José Alberto Fernández;Ramachandran Vaidyanathan;J. Trahan
近年来，可重构网格（R-Mesh）引起了人们的广泛兴趣，部分原因是它能够采用极快的算法来解决大量问题。无限制的 R-Mesh 创建了多种总线形状，有利于算法设计并减少运行时间。在本文中，我们提出了一种总线线性化过程，它将 R-Mesh 的任意非线性总线配置转换为可在线性 R-Mesh (LR-Mesh)（无限制 R-Mesh 的较弱版本）上实现的等效非循环线性总线配置。此过程使算法设计者可以自由地使用任意形状的总线，同时自动将算法转换为在更简单的平台上运行。我们通过两个重要的应用来说明我们的总线线性化方法。第一个可以加快不受限制的 R-Mesh 的缩放模拟。本次缩放模拟的开销为logN（小于之前最快缩放模拟的logPlogNP开销），并使用独占写入LR-Mesh作为模拟模型；之前的模拟需要并发写入。第二个应用程序采用为 R-Meshes 设计的算法，以在具有管道光学总线的模型上运行。
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 nonlinear 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 logN (smaller than the logPlogNP 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.