SIMULATING SHARED-MEMORY IN REAL-TIME - ON THE COMPUTATION POWER OF RECONFIGURABLE ARCHITECTURES

We consider randomized simulations of shared memory on a distributed m emory machine (DMM) where the n processors and the n memory modules of the DMM are connected via a reconfigurable architecture. We first pre sent a randomized simulation of a CRCW PRAM on a reconfigurable DMM ha ving a complete reconfigurable interconnection. It guarantees delay O( log n), with high probability. Next we study a reconfigurable mesh DM M (RM-DMM). Here the n processors and n modules are connected via an n xn reconfigurable mesh. It was already known that an n x m reconfigura ble mesh can simulate in constant time an n-processor CRCW PRAM with s hared memory of size m. 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 Omega(n(2)) for the reconfigurable mesh is necessary for real ti me simulations. (C) 1997 Academic Press.