Simulating Shared Memory in Real Time: On the Computation Power of Reconfigurable Architectures

AbstractWe consider randomized simulations of shared memory on a distributed memory machine (DMM) where thenprocessors and thenmemory modules of the DMM are connected via a reconfigurable architecture. We first present a randomized simulation of a CRCW PRAM on a reconfigurable DMM having a complete reconfigurable interconnection. It guarantees delay O(log*n), with high probability. Next we study a reconfigurable mesh DMM (RM-DMM). Here thenprocessors andnmodules are connected via ann×nreconfigurable mesh. It was already known that ann×mreconfigurable mesh can simulate in constant time ann-processor CRCW PRAM with shared memory of sizem. In this paper we present a randomized step by step simulation of a CRCW PRAM with arbitrarily large shared memory on an RM-DMM. It guarantees constant delay with high probability, i.e., it simulates in real time. Finally we prove a lower bound showing that sizeΩ(n2) for the reconfigurable mesh is necessary for real time simulations