A Lower-Bound for the Emulation of PRAM Memories on Processor Networks

AbstractWe show a lower bound of Ω(min{log m, √n}) on the slowdown of any deterministic emulation of a PRAM memory with m cells and n I/O ports on an n-processor bounded-degree network. The bound is weak; unlike all previous bounds, however, it does not depend on the unnatural assumption of point-to-point communication which says, roughly, that messages in transit cannot be duplicated by intermediate processors. For m sufficiently large relative to n, the new bound implies the optimality of a simple emulation on a mesh-of-trees network