In this paper we present lower and upper bounds for the deterministic simulation of a Parallel Random Access Machine (PRAM) withn processors andm variables on a Distributed Memory Machine (DMM) withp ≤n processors. The bounds are expressed as a function of the redundancyr of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for anym polynomial in n and r=Θ(1).
The complexity of deterministic PRAM simulation on distributed memory machines
PIETRACAPRINA, ANDREA ALBERTO;PUCCI, GEPPINO
1997
Abstract
In this paper we present lower and upper bounds for the deterministic simulation of a Parallel Random Access Machine (PRAM) withn processors andm variables on a Distributed Memory Machine (DMM) withp ≤n processors. The bounds are expressed as a function of the redundancyr of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for anym polynomial in n and r=Θ(1).File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
