-
PRAM
- Parallel Random-Access Machine
- synchronní model paralelního výpočtu ve kterém procesory komunikují sdílenou pamětí
- výpočet probíhá po krocích: čtení sdílené paměti; lokální operace; zápis do sdílené paměti
- přístupy do paměti: EREW(, ERCW), CREW, CRCW
- řešení zápisových konfliktů
- broadcast
-
Řešení zápisových konfliktů PRAM
- COMMON: všechny zapisované hodnoty musí být shodné
- ARBITRARY: zapisované hodnoty mohou být různé, zapíše se libovolná
- PRORITY: procesory mají prioritu
-
Broadcast v PRAM
- Hodnota uložená v paměti má být rozšířena mezi N procesory:
- pro CREW a CRCW řešení v konstantním čase
- pro EREW je třeba simulovat současné čtení (P1 přečte D a zpřístupní jej P2, P1 a P2 jej zpřístupní P3 a P4...)
-
Distribuovaný broadcast
- komunikace: známe horní mez zpoždění zprávy; lokální hodiny pro každý proces
- m = zpráva z množiny možných zpráv
- Každá zpráva obsahuje:
- (a) totožnost odesilatele sender(m)
- (b) pořadové číslo (kolikátou zprávu odesilatel poslal) seq(m)
-
Základní vlastnosti distr. broadcastu
- Validity: Pokud korektní proces odešle broadcast, pak všechny korektní procesy tento broadcast obdrží (dříve či později)
- Agreement: Pokud korektní proces obdržel broadcast, potom všechny korektní procesy obdrží broadcast také (dříve či později)
- Integrity: Každý korektní procs obdrží broadcast maximálně jednou (nedojde k zacyklení)
-
Další vlastnosti broadcastu
- FIFO Order: pokud nějaký proces broadcastuje zprávu m před zprávou n, potom žádný korektní proces nepřijmne zprávu n, aniž by nejdříve přijal zprávu m (tj. zprávy jsou doručovány ve stejném pořadí jak byly odeslány)
- Causal Order: FIFO Order, ale v rámci všech procesů v systému (tj. Pokud máme 2 procesy a každý vysílá 2 broadcasty A (m,n), B(o,p) pak žádný proces nepřijme v pořadí (m,n,p,o) nebo (o,p,n,m) nebo (p,n,m,o)... Jediné správné je (m,n,o,p) nebo (o,p,m,n) nebo (m,o,p,n) nebo (m,o,n,p))
- Total Order: doručování přesně ve stejném pořadí, jak byly broadcasty odeslány
-
Spolehlivý broadcast
validita, agreement, integrita
-
Klasifikace broadcastů
- Reliable (RBCAST): Validity + Agreement + Integrity
- FIFO (FBCAST): reliable + FIFO Order
- Causal (CBCAST): reliable + Causal Order
- Atomic (ABCAST): reliable + Total Order
-
Suma prefixů
- jeden ze základních kamenů stavby paralelních systémů
- operace, jejímž vstupem je binární asociativní operátor ⊕ a uspořádaná posloupnost n prvků ?0, ?1 , ..., ??−1, jejímž výstupem je vektor (?0, ?0⊕?1, ..., ?0⊕?1⊕...⊕??−1)
-
Synchronizace v distr. systémech
- absence globálních a synchronizačních hodin
- řešení vzájemného vyloučení:
- (a) centralizované řešení
- (b) distribuované (Lamportův alg., Raymondův alg.)
-
Lamportův algoritmus
- předpokládá oboustranné FIFO kanály mezi procesy
- každý proces udržuje vlastní frontu požadavků
- používá časových značek k uspořádání požadavků
- vyžaduje 3(n-1) zpráv
- fáze: požadavek (request), potvrzení (reply), uvolnění (release)
- algoritmus:
- (a) proces P pošle všem ostatním procesům request
- (b) všechny ostatní procesy musí odpovědět reply
- (c) po dokončení proces P pošle release
- (d) požadavky se vyřizují dle FIFO front
-
Raymondů algoritmus
- procesy uspořádány do stromu
- pracuje na bázi předávání pověření
- udržuje frontu požadavků na pověření od procesů nižších úrovní
|
|