In this paper we deal with the granularity problem, that is, the problem of implementing a shared memory in a distributed system where n processors are connected to n memory modules through a complete network (Module Parallel Computer). We present a memory organization scheme where m=O(n^2) variables, each replicated into a 2c — 1 copies (for constant c), are evenly distributed among the n modules, so that a suitable access protocol allows any set of at most n distinct read/write operations to be performed by the processors in O(sqrt(n)) parallel steps in the worst case. The well known strategy based on multiple copies is needed to avoid the worst-case O(n)-time, since only a majority of the copies of each variable need be accessed for any operation. The memory organization scheme can be extended to deal with m=O(n^3) variables attaining an O(n^(2/3))-time complexity in the worst case.

An O(√n)-worst-case-time solution to the granularity problem

PIETRACAPRINA, ANDREA ALBERTO;
1993

Abstract

In this paper we deal with the granularity problem, that is, the problem of implementing a shared memory in a distributed system where n processors are connected to n memory modules through a complete network (Module Parallel Computer). We present a memory organization scheme where m=O(n^2) variables, each replicated into a 2c — 1 copies (for constant c), are evenly distributed among the n modules, so that a suitable access protocol allows any set of at most n distinct read/write operations to be performed by the processors in O(sqrt(n)) parallel steps in the worst case. The well known strategy based on multiple copies is needed to avoid the worst-case O(n)-time, since only a majority of the copies of each variable need be accessed for any operation. The memory organization scheme can be extended to deal with m=O(n^3) variables attaining an O(n^(2/3))-time complexity in the worst case.
1993
Lecture Notes in Computer ScienceSTACS 93
9783540475743
9783540565031
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/2509741
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact