Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes
type: Item
instance of: scholarly article
title: Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes
zbMATH Open document ID: 0783.68050
DOI: 10.1016/0020-0190(93)90138-Y
author: Ramachandran Vaidyanathan
author: Jerry L. Trahan
published in: Information Processing Letters
publication date: 1993-11-28T00:00:00Z
review text: A \(d\)-dimensional reconfigurable mesh (denoted by \(RM^ d)\) consists of processors arranged as a \(d\)-dimensional mesh, in which each processor is connected to its neighbors via input/output ports. Each processor may also internally partition its ports so as to short-circuit all ports in each block of the partition. This partition may change during each step of the algorithm. The ability of each processor to short-circuit, or fuse, its ports allows the \(RM^ d\) to create various buses connecting processors. We consider the simulation of a \(P_ 0\times P_ 1\times\cdots\times P_{d-1}\) \(RM^ d\) (where \(P_{d-1} \geq P_ 0\), \(P_ 1,\ldots,P_{d-2})\) by an \(RM^ 2\). \textit{A. Schuster} [Dynamic reconfiguring networks for parallel computers: Algorithms and complexity bounds, Doctoral Dissertation, Dept. of Computer Science, Hebrew University, Israel (1991)] has shown that a step of any \(RM^ d\), for any constant \(d>2\), can be simulated by an \(RM^ 2\) in constant time. The simulation proposed in this paper is more efficient. We show that for constant \(d\), any \(RM^ 2\) that simulates a \(P_ 0 \times P_ 1 \times \cdots \times P_{d-1}\) \(RM^ d\) in constant time requires \(\Omega \bigl( \prod^{d-2}_{i=0}P^ 2_ i \bigr)\) processors. We give a method for simulating the above \(RM^ d\) in constant time on a \(\biggl( 2d \prod^{d-1}_{i=1}P_ i \times (2d+1) P_ 0+ \sum^{d-2}_{i=1} \prod^ i_{j=0}P_ j \biggr)\) \(RM^ 2\). If \(P_ 0=\Theta(P_{d- 1})\), then this simulation uses an optimal number (to within a constant) of processors. If \(d\) is not a constant, then the simulation can be done on a \(\biggl( 4d \prod^{d-1}_{i=1} P_ i \times (2d+1)P_ 0+\sum^{d-2}_{i=1} \prod^ i_{j=0}P_ j \biggr)\) \(RM^ 2\). As an intermediate step, we give a two layer layout for a multidimensional mesh. We also show that an \(RM^ 1\) cannot simulate an arbitrary step of an \(RM^ d\) (where, \(d \geq 2)\) in constant time.
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 94C99
zbMATH DE Number: 440384
zbMATH Keywords: parallel computing
zbMATH Keywords: VLSI layout
zbMATH Keywords: reconfigurable mesh
zbMATH Keywords: simulation
MaRDI profile type: Publication
cites work: Optimal bounds for decision problems on the CRCW PRAM
cites work: Q4036559
cites work: Q4002466
cites work: Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
cites work: Bus automata and immediate languages
cites work: Two dimensional processor array with a reconfigurable bus system is at least as powerful as CRCW model
description: scientific article; zbMATH DE number 440384