Simulating the CRCW PRAM on reconfigurable networks

AbstractThis 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 × MN1r 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 N1(r − 1) × N1(r − 1) × … × N1(r − 1) × (MN(r − 2)(r − 1)) reconfigurable network, where r ⩾ 2 and is a constant