SIMULATING THE CRCW PRAM ON RECONFIGURABLE NETWORKS

This paper addresses the problem of simulating the CRCW PRAM on reconf igurable networks. Let N and M, respectively, be the numbers of proces sors and memory cells contained in the CRCW PRAM. We firstly show that a two-dimensional Nx MN1/r reconfigurable network can simulate any op eration performed on the CRCW PRAM in O(1) time, where r greater than or equal to 2 and is a constant. Then, if N less than or equal to M, w e further show that any operation performed on the CRCW PRAM can be si mulated as well as O(1) time on a r-dimensional N1/(r-1) x N1/(r-1) x ... x N1/(r-1) x (M/N(r-2/(r-1))) reconfigurable network, where r grea ter than or equal to 2 and is a constant. (C) 1998-Elsevier Science B. V. All rights reserved.