Abstract:
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.