hide
Free keywords:
-
Abstract:
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 1983
