Efficient Deterministic and Probabilistic Simulations of PRAMs on Linear Arrays with Reconfigurable Pipelined Bus Systems

In this paper, we present deterministic and probabilistic methods for simulating PRAM computations on linear arrays with reconfigurable pipelined bus systems (LARPBS). The following results are established in this paper. (1) Each step of a p-processor PRAM with m=O(p) shared memory cells can be simulated by a p-processors LARPBS in O(log p) time, where the constant in the big-O notation is small. (2) Each step of a p-processor PRAM with m=(p) shared memory cells can be simulated by a p-processors LARPBS in O(log m) time. (3) Each step of a p-processor PRAM can be simulated by a p-processor LARPBS in O(log p) time with probability larger than 1–1/p^c for all c>0. (4) As an interesting byproduct, we show that a p-processor LARPBS can sort p items in O(log p) time, with a small constant hidden in the big-O notation. Our results indicate that an LARPBS can simulate a PRAM very efficiently.