Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-053 | 5th May 2000 00:00

Parallel Read Operations Without Memory Contention



We address the problem of organizing a set $T$ of shared data into
the memory modules of a Distributed Memory Machine (DMM) in order
to minimize memory access conflicts (i.e. memory contention)
during read operations.
Previous solutions for this problem can be found as fundamental
subprocedures of the PRAM simulation methods on DMM presented during
the last years. The efficiency of such solutions relies on the assumption that
the set of shared data is relatively small.
Indeed, each shared data is replicated in at least two copies;
moreover, the number of processors and that of memory modules are
polynomial in the number of the shared data.
This assumption is reasonable to the aim of PRAM simulations
(where the shared data consist only on the shared program
variables) but it is not realistic in the case of parallel systems for large public-accessible
databases where the number of available resources (such as
processors and memory modules) is tipically significantly (say
exponentially) smaller than the size of the database.

ISSN 1433-8092 | Imprint