Optimal simulation of multidimensional reconfigurable meshes by two- dimensional reconfigurable meshes (Q688237)

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.