Abstract
This paper addresses the problem of simulating the CRCW PRAM on reconfigurable networks. Let N and M, respectively, be the numbers of processors and memory cells contained in the CRCW PRAM. We firstly show that a two-dimensional N × MN 1/r reconfigurable network can simulate any operation performed on the CRCW PRAM in O(1) time, where r ≥ 2 and is a constant. Then, if N ≤ M, we further show that any operation performed on the CRCW PRAM can be simulated as well as O(1) time on a r-dimensional N 1/(r-1) × N 1/(r-1) × ⋯ × N 1/(r-1) × (M/N(r-2)/(r-1)) reconfigurable network, where r ≥ 2 and is a constant. © 1998 - Elsevier Science B.V. All rights reserved.