Deterministic P-RAM simulation with constant redundancy
Scot W. Hornick, F. P. Preparata · 1989
In this paper, we show that distributing the memory of a parallel computer and, thereby, decreasing its granularity allows a reduction in the redundancy required to achieve polylog simulation time for each P-RAM step.Previously, realistic models of parallel computation assigned one memory module to each processor and, as a result, insisted on relatively coarse-grain memory.We propose, on the other hand, a more flexible, but equally valid model of computation, the distributed-memory, bounded-degree network (DMBDN) model.This model allows the use of fine-grain memory while maintaining the realism of a bounded-degree interconnection network.We describe a P-RAM simulation scheme, which is admitted under the DMBDN model, that exploits the increased memory bandwidth provided by a two-dimensional mesh of trees (2DMOT) network to achieve an overhead in memory redundancy lower than that required by other fast, deterministic P-RAM simulations.Specifically, for a deterministic simulation of an n-processor P-RAM on a bounded-degree network, we are able to reduce the number of copies of each variable from O(logn/loglogn) to ®(1) and still simulate each P-RAM step in polylog time.