期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
