In this paper we present lower and upper bounds for the deterministic emulation of a Parallel Random Access Machine (PRAM) with n processors and m variables on a Distributed Memory Machine (DMM) with n processors. The bounds are expressed as a function of the redundancy r of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for any m polynomial in n and r=Θ(1).

Tight bounds on deterministic PRAM emulations with constant redundancy

PIETRACAPRINA, ANDREA ALBERTO;PUCCI, GEPPINO
1994

Abstract

In this paper we present lower and upper bounds for the deterministic emulation of a Parallel Random Access Machine (PRAM) with n processors and m variables on a Distributed Memory Machine (DMM) with n processors. The bounds are expressed as a function of the redundancy r of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for any m polynomial in n and r=Θ(1).
1994
Lecture Notes in Computer Science Algorithms — ESA '94
354058434X
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/2509822
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact