Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories

The present paper provides a comprehensive study of the following problem. Consider algorithms which are designed for shared memory models of parallel computation (PRAMs) in which processors are allowed to have fairly unrestricted access patterns to the shared memory. Consider also parallel machines in which the shared memory is organized in modules where only one cell of each module can be accessed at a time. Problem. Give general fast simulations of these algorithms by these parallel machines. Each of our solutions answers two basic questions. (1) How to initially distribute the logical memory addresses of the PRAM, to be simulated, among the physical locations of the simulating machine? (2) How to compute the physical location of a logical address during the simulation? We utilize two main ideas for the first question. (a) Randomization. The logical addresses are randomly distributed among the memory modules. This is done using universal hashing. (b) Copies. We keep copies of each logical address in several memory modules. In a typical time cycle of the PRAM some number of memory requests has to be satisfied. As a primary objective, our simulations minimize the maximum number of memory requests which are assigned to the same module. Our solutions also optimize the following computational resources. They minimize the size of the physical memory, the time for computing the mapping from logical to physical addresses and the space for storing this mapping. We discuss extensions of our solutions to various PRAMs and various shared memory parallel machines. Our solution is also applicable to synchronous distributed machines with no shared memory where the processors can communicate through a bounded degree network. A preliminary version of this paper was presented at the 9th Workshop on Graphtheoretic Concepts in Computer Science (WG-83), Fachbereich Mathematic, Universität Osnabrück, June 198