Back to Search
Start Over
About the efficiency of partial replication to implement Distributed Shared Memory
- Source :
- [Research Report] PI 1727, 2005, pp.20, ICPP
- Publication Year :
- 2005
- Publisher :
- HAL CCSD, 2005.
-
Abstract
- Distributed Shared Memory abstraction (DSM) is traditionally realized through a distributed memory consistency system(MCS) on top of a message passing system. In this paper we analyze the impossibility of efficient partial replication implementation of causally consistent DSM. Efficiency is discussed in terms of control information that processes have to propagate to maintain consistency. We introduce the notions of share graph and hoop to model variable distribution and the concept of dependency chain to characterize processes that have to manage information about a variable even though they do not read or write that variable. Then, we weaken causal consistency to try to define new consistency criteria weaker enough to allow efficient partial replication implementations and strong enough to solve interesting problems. Finally, we prove that PRAM is such a criterion, and illustrate its power with the Bellman-Ford shortest path algorithm. / Les mémoires partagées réparties constituent une abstraction qui est traditionellement concrétisée par un système réparti de mémoire cohérente, au-dessus d'un système de communication par messages. Dans ce rapport, on analyse l'impossibilité d'avoir une implémentation efficace de mémoire partagée répartie à cohérence causale, basée sur la duplication partielle des variables. L'efficacité est envisagée en terme d'information contrôle qui doit être propagée pour assurer la cohérence. On introduit les notions de graphe de partage et d'arceau, qui modélisent la répartition des variables et la notion de chaîne de dépendance pour caractériser les processus qui doivent gérer des informations relatives à une variable dont ils ne possèdent pas de copie locale. Ensuite, on affaiblit le critère de cohérence causale, dans le but de déterminer un nouveau critère de cohérence qui soit suffisament faible pour permettre un implémentation efficace basée sur la duplication partielle, mais suffisament forte pour pouvoir résoudre des problèmes intéressants. Finalement, on prouve que le critère appelé PRAM satisfait ces exigences, et illustrons sa pertinence en montrant une implémentation de l'algorithme de plus court chemin de Bellman-Ford.
- Subjects :
- Theoretical computer science
Distributed shared memory
Computer science
Distributed computing
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
duplication partielle
Causal consistency
algorithme de plus court chemin
0102 computer and information sciences
02 engineering and technology
01 natural sciences
shortest path algorithm
consistency criterion
cohérence causale
0202 electrical engineering, electronic engineering, information engineering
PRAM consistency
partial replication
cohérence PRAM
Mémoire partagée répartie
critères de cohérence
Message passing
Consistency model
020202 computer hardware & architecture
causal consistency
010201 computation theory & mathematics
Graph (abstract data type)
Distributed memory
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- [Research Report] PI 1727, 2005, pp.20, ICPP
- Accession number :
- edsair.doi.dedup.....c34ea04152af8f8398a759b8a6b6b6fd