Simulating the CRCW PRAM on reconfigurable networks

[[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 ×MN1/r reconfigurable network can simulate any operation performed on the CRCW PRAM in O(1) time, where r greater than or equal 2 and is a constant. Then, if N [less-than or equal to] 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) ×[midline ellipsis] ×N1/(r-1) ×(M/N(r-2)/(r-1)) reconfigurable network, where r greater than or equal 2 and is a constant.[[fileno]]2030215010013[[department]]資訊工程學