FACULTY
OF INFORMATICS
Masaryk University
IA039: Architektura superpočítačů a náročné výpočty Paralelní počítače
Luděk Matýska
Jaro 2020
Luděk Matýska • Paralelní počítače • Jaro 2020
1/64
FACULTY
OF INFORMATICS
Masaryk University
Paralelní počítače
■ SmaU-scaLe multiprocessing
■ 2-80 procesoru
■ převážně SMP (sdílená pamět)
■ Large-scale multiprocessing
■ stovky, tisíce a více procesorů
■ Zpravidla distribuovaná pamět
Luděk Matýska • Paralelní počítače • Jaro 2020
2/64
FACULTY
OF INFORMATICS
Masaryk University
Paralelní počítače (II)
■ Architektura
■ Single Instruction Multiple Data, SIMD
■ Multiple Instruction Multiple Data, MIMD
■ Programovaci modely
■ Single Program Multiple Data, SPMD
■ Multiple programs Multiple Data, MPMD
Luděk Matýska • Paralelní počítače • Jaro 2020
3/64
FACULTY
OF INFORMATICS
Masaryk University
Architektura - SIMD
■ Procesory synchronizovány
■ Všechny vykonávají vždy stejnou instrukci
■ Analogie vektorových procesorů
■ Jednoduché procesory
■ Jednodušší programovací modeL
■ ale složité vlastní programování zejména skalárních výpočtů
Luděk Matýska • Paralelní počítače • Jaro 2020
4/64
FACULTY
OF INFORMATICS
Masaryk University
Vektorový procesor
■ Procesor schopný pracovat s vektory dat
■ vektor jako datový typ instrukční sady
■ Cray přišel i s vektorem registrů (jinak přímo práce s pamětí)
■ Vektorový Load/Store
■ „skládání" vektory z různých slov v paměti
■ vektor registrů s adresami pamětových buněk se skutečnými daty
■ „lokalizuje" data pro další práci
■ fakticky provádí operace scather/gather nad pamětí
■ Pamětový subsystém
■ standardně nepracuje s vyrovnávací pamětí
■ prokládaná (banked) pamět
■ více souběžně běžídích operací nad pamětí
■ dosahuje vyšší propustnosti než využití vyrovnávací paměti zejména tam, kde jsou data „náhodně" rozptýlena
v paměti(random access)
I  Další info např. http://www.cs.berkeley.edu/~pattrsn/252S98/Lec06-vector.pdf Luděk Matýska • Paralelní počítače • Jaro 2020 5/64
FACULTY
OF INFORMATICS
I   Masaryk University
Architektura - MIMD
■ Plně asynchronní systém
■ Procesory zceLa samostatné
■ Není třeba speciální výroba (off-the-shelf)
■ Výhody
■ Vyšší flexibilita
■ Teoreticky vyšší efektivita
■ Nevýhody
■ Explicitní synchronizace
■ Složité programování
Luděk Matýska • Paralelní počítače • Jaro 2020
6/64
FACULTY
OF INFORMATICS
Masaryk University
Komunikační modely
■ Sdílená pamět (Shared Memory Architecture)
■ Předávání zpráv (Message passing)
Luděk Matýska • Paralelní počítače • Jaro 2020
7/64
FACULTY
OF INFORMATICS
Masaryk University
Sdílená pamět
Pamět oděLená od procesorů Uniformní přístup k paměti Nejsnazší propojení - sběrnice „Levná" komunikace
Složité prokládání výpočtu a komunikace (aktivní čekání)
Luděk Matýska • Paralelní počítače • Jaro 2020
8/64
FACULTY
OF INFORMATICS
Masaryk University
Předávání zpráv
■ Každý procesor „viditelný"
■ Vlastní pamět u každého procesoru
■ Explicitní komunikace - předávání zpráv
■ Vysoká cena komunikace (výměny dat)
■ Možnost prokládání výpočtů a komunikace
Luděk Matýska • Paralelní počítače • Jaro 2020
9/64
FACULTY
OF INFORMATICS
Masaryk University
Hybridní systémy
■ Nonuniform memory access architecture (NUMA)
■ Cache-onLy memory access architecture (COMA)
■ Distributed shared-memory (DSM)
Luděk Matýska • Paralelní počítače • Jaro 2020
10/64
FACULTY
OF INFORMATICS
Masaryk University
Non-uniform memory access
■ Přístup k různým fyzickým adresám trvá různou dobu
■ Umožňuje vyšší škáLovateLnost
■ Potenciálně nižší propostnost
■ Koherence vyrovnávacích pamětí
■ ccNUMA
Luděk Matýska • Paralelní počítače • Jaro 2020
11/64
FACULTY
OF INFORMATICS
Masaryk University
Cache only memory access
■ NUMAs charakterem vyrovnávací paměti
■ Data putují k procesorům, které je používají
■ Pouze zdánlivá hierarchie
■ Systém musí hlídat, že má jedinou kopii
■ Experimentální
Luděk Matýska • Paralelní počítače • Jaro 2020
12/64
FACULTY
OF INFORMATICS
Masaryk University
Distributed shared-memory
■ Distribuovaný systém - cluster
■ Lokální pamět každého uzlu
■ Vzdálená pamět ostatních uzlů
„Fikce" jedné rozsáhlé paměti
■ Hardwarové řešení
■ Zpravidla využívá principů virtuální paměti
■ Transparentní
■ Softwarové řešení
■ Knihovna
Netransparentní, progamátor program musí explicitně přizpůsobit
Luděk Matýska • Paralelní počítače • Jaro 2020
13/64
FACULTY
OF INFORMATICS
Masaryk University
Koherence vyrovnávacích pamětí
■ Příčiny výpadku vyrovnávací paměti:
■ Compulsory miss: 1. přístup k datům
■ Capacity miss: nedostatečná kapacita
■ Conflict miss: různé adresy mapovány do stejného místa
■ Coherence miss: různá data v různých vyrovnávacích pamětích
■ Poslední případ se týká muLtiprocesorů
Luděk Matýska • Paralelní počítače • Jaro 2020
14/64
FACULTY
OF INFORMATICS
Masaryk University
Řešení problému koherence
■ Vyrovávací paměti musí vědět o změně
■ Metody založené na broadcastu
■ Adresářové metody
Luděk Matýska • Paralelní počítače • Jaro 2020
15/64
FACULTY
OF INFORMATICS
Masaryk University
Snoopy cache
■ Broadcastový přístup
■ Propojovací sítě s „přirozeným" brodcastem - sběrnice
■ Každý procesor sleduje všechny přístupy k paměti
Luděk Matýska • Paralelní počítače • Jaro 2020
16/64
FACULTY
OF INFORMATICS
Masaryk University
Zneplatnění
■ Reakce na změnu dat ve vzdálené (vyrovnávací) paměti
■ Řádka v aktuální (naslouchající) vyrovnávací paměti je zneplatněna
■ V případě opětného přístupu je přehrána ze vzdálené paměti
Luděk Matýska • Paralelní počítače • Jaro 2020
17/64
FACULTY
OF INFORMATICS
Masaryk University
Update
■ Řádka je okamžitě obnovena
■ Při opětovném přístupu je již k dispozici
■ Nevýhody
■ Falešné sdílení (nepracují na stejných datech)
■ Přílišné zatížení sběrnice
■ Nelze rozhodnout, zda update nebo zneplatnění je obecně Lepší
Luděk Matýska • Paralelní počítače • Jaro 2020
18/64
FACULTY
OF INFORMATICS
Masaryk University
Koherence vyrovnávacích pamětí II
■ Snoopy schéma založené na broadcastu
■ Nepoužitelné u složitějších propojovacích sítí
■ Není rozšiřitelné (scalable)
■ Redukce „oslovených" vyrovnávacích pamětí - Adresáře
■ Položka u každého bloku paměti
■ Odkazy na vyrovnávací paměti s kopií tohoto bloku
■ Označení exkluzivity (právo pro čtení)
Luděk Matýska • Paralelní počítače • Jaro 2020
19/64
FACULTY
OF INFORMATICS
Masaryk University
Adresářové přístupy
■ Tři základní schémata
■ Plně mapované adresáře
v
■ Částečně (Limited) mapované adresáře
■ Provázané (chained) adresáře
■ Zhodnocení vlastností
■ Na základě velikosti potřebné paměti
■ Na základě složitosti (počtu příkazů) protokolu
Luděk Matýska • Paralelní počítače • Jaro 2020
20/64
FACULTY
OF INFORMATICS
Masaryk University
Plně mapované adresáře
■ Každá adresářová položka má tolik údajů, kolik je vyrovnávacích pamětí (procesorů)
■ Bitový vektor „přítomnosti"
■ Nastavený bit znamená, že příslušná vyrovnávací data má kopii bloku paměti
■ Příznak exkluzivity
■ Stačí jeden na blok
■ Jen jedna vyrovnávací pamět
■ Příznaky v každé vyrovnávací paměti (každý blok)
■ Příznak platnosti
■ Příznak exkluzivity
Luděk Matýska • Paralelní počítače • Jaro 2020
21/64
FACULTY
OF INFORMATICS
Masaryk University
Omezené adresáře
PLné adresáře velmi pamětově náročné
■ Velikost paměti: P2M/B
■ P je počet vyrovnávacích pamětí
■ M velikost hlavní paměti
■ B velikost bloku
Data nejsou zpravidla široce sdílena
■ Většina adresářových bitů má hodnotu nula Použití přímých odkazů
■ Nebude již stačit jeden bit
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
Masaryk University
Omezené adresáře
■ Množina ukazatelů na vyrovnávací paměti
■ Dynamická alokace dle potřeby
■ Vlastnosti
■ Počet bitů ukazatele: log2 P
■ Počet položek v poolu ukazatelů: k
■ Výhodnější než přímo mapovaná: pokud k < j^-p
■ Informovány jen explicitně uvedené vyrovnávací paměti
Luděk Matýska • Paralelní počítače • Jaro 2020
23/64
FACULTY
OF INFORMATICS
Masaryk University
Přetečení
■ Pokud přestanou stačit položky
■ Příliš mnoho sdílených bloků
■ Možné reakce
■ Zneplatnění všech sdílených (brodcast, Dir/B)
■ Výběr jedné položky (i náhodně) a její zneplatnění (bez broadcastu, Dir/NB)
Luděk Matýska • Paralelní počítače • Jaro 2020
24/64
FACULTY
OF INFORMATICS
Masaryk University
Další schemata
■ Coarse-vector (Dir/CVr)
■ r je velikost regionu (více procesorů), kterému odpovídá jeden bit (tedy více procesorů)
■ Přepnutí interpretace při přetečení
■ Omezený broadcast všem procesorům v oblasti.
■ LimitLESS: programové přerušení při přetečení
Luděk Matýska • Paralelní počítače • Jaro 2020
25/64
FACULTY
OF INFORMATICS
I   Masaryk University
Provázaná schemata
■ Cache-Based Linked-List
■ Centrálně pouze jediný ukazatel
■ Ostatní ukazatele svázány s vyrovnávací pamětí
■ Vyrovnávací paměti „provázaný" ukazateli
■ Výhody
■ Minimalizace pamětových nároků
■ Nevýhody:
■ Složitý protokol.
■ Zvýšená komunikace (více zpráv než nutno)
■ Zápis je delší (sekvenční procházení seznamu)
Luděk Matýska • Paralelní počítače • Jaro 2020
26/64
FACULTY
OF INFORMATICS
Masaryk University
Hierarchické adresáře
■ Použité v systémech s vícenásobnými sběrnicemi
■ Hierarchie vyrovnávacích pamětí
■ Vyšší úroveň na každém propojení sběrnic
■ Vyšší pamětové nároky
■ Vyšší úroveň musí držet kopie pamětových bloků sdílených nižší úrovní
■ Není třeba rychlá pamět
■ V principu hierarchie snoopy protokolů
Luděk Matýska • Paralelní počítače • Jaro 2020
27/64
FACULTY
OF INFORMATICS
Masaryk University
Rozšiřitelnost (Scalability)
■ Není jednotná definice
■ Používané základní formulace - rozšiřitelný je takový systénm, pro nějž platí:
■ Výkon roste lineárně s cenou
■ Je zachován konstantní poměr Cena/Výkon
■ Alternativní parametr - Míra rozšiřitelnosti
■ Změna výkonu přidáním procesoru
■ Změna ceny přidáním procesoru
■ Smysluplný rozsah počtu procesorů
Luděk Matýska • Paralelní počítače • Jaro 2020
28/64
FACULTY
OF INFORMATICS
Masaryk University
Zrychlení
S(N)  = W1)
Texec(n)
Tcomp(X) H" T com m (i)
Tcomm
(W)
Ideální zrychlení vyžaduje
Tcomp (N)   = Tcomp(l)/N
Tcomm
(N)
— Tcomm
(1)/N
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
Masaryk University
Zrychlení - komentář
■ Teoretický pojem, realita závisí na aplikaci
■ Různé hodnoty pro různé aplikace
■ Vliv paralelizovatelnosti problému (Amdalův zákon)
Luděk Matýska • Paralelní počítače • Jaro 2020
30/64
FACULTY
OF INFORMATICS
Masaryk University
Rozšiřitelné propojovací sítě
■ Požadavky na ideální sít:
■ Nízká cena rostoucí lineárně s počtem procesorů (N)
■ Minimální latence nezávislá na Ař
■ Propustnost rostoucí lineárně s Ař
Luděk Matýska • Paralelní počítače • Jaro 2020
31/64
FACULTY
OF INFORMATICS
Masaryk University
Vlastnosti sítí
■ Tři základní komponenty
■ Topologie
■ Přepínání dat (jak se data pohybují mezi uzly)
■ Směrování dat (jak se hledá cesta mezi uzly)
Luděk Matýska • Paralelní počítače • Jaro 2020
32/64
FACULTY
OF INFORMATICS
Masaryk University
Propojovací sítě
■ Rozlišujeme následující základní parametry
■ Velikost sítě - počet uzlů Ar
■ Stupeň uzlu d
■ Poloměr sítě D
■ Nejdelší nejkratší cesta
Bisection width B
■ Redundance sítě A
■ Minimální počet hran, které je třeba odstranit, aby se sít rozpadla na dvě
■ Cena C
■ Počet komunikačních linek v síti
Luděk Matýska • Paralelní počítače • Jaro 2020
33/64
FACULTY
OF INFORMATICS
Masaryk University
Bisection width
V
■ Sirka rozpůlení
■ Minimální počet linek, které je třeba odstranit, aby se systém rozpadl na dvě stejné části
■ Bisection bandwidth - propustnost při rozpůlení
■ Celková kapacita (propustnost) výše odstraněných linek
■ Ideální vlastnost:
■ Bisection badnwidth vztažená na procesor je v daném systému konstantní.
Luděk Matýska • Paralelní počítače • Jaro 2020
34/64
FACULTY
OF INFORMATICS
Masaryk University
Topologie přepínacích sítí
■ Klasifikace na základě rozměru
■ Jednorozměrné
■ Dvourozměrné
■ Třírozměrné
■ Hyperkrychle
Luděk Matýska • Paralelní počítače • Jaro 2020
35/64
FACULTY
OF INFORMATICS
Masaryk University
Jednorozměrné propojovací sítě
■ Linerání pole
■ Jednotlivé prvky navázány na sebe
■ „Korálky"
■ Nejjednodušší
■ Nejhorší vlastnosti
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
Masaryk University
Dvourozměrné propojovací sítě
■ Kruh
■ Uzavřené lineární pole
■ Hvězda
■ Strom
■ Snižuje poloměr sítě (2 log ^y^)
■ Stále špatná redundance a bisection (band)width
■ Tlustý strom (fat tree)
■ Přidává redundantní cesty ve vyšších úrovních
Luděk Matýska • Paralelní počítače • Jaro 2020
37/64
FACULTY
OF INFORMATICS
I   Masaryk University
Dvourozměrná mřížka
■ VeLmi populární
■ Dobré vlastnosti
■ Poloměr 2(N1/2 - 1)
■ Bisection N1/2
■ Redundance 2
■ Avšak vyšší cena a proměnný stupeň uzlu
■ Torus
■ Uzavřená dvourozměrná mřížka
■ Poloměr N1/2
■ Bisection 2N1/2
■ Redundance 4
■ Vyšší cena - přidá 2N1/2 hran
Luděk Matýska • Paralelní počítače • Jaro 2020
38/64
FACULTY
OF INFORMATICS
Masaryk University
Třírozměrná sít
■ Vlastnosti
■ Poloměr 3(^/3 _ i)
■ Bisection Ař2/3
■ Redundance 3
■ Cena akceptovatelná 2(Ař — Ař2/3)
■ Konstrukčně složitá
Luděk Matýska • Paralelní počítače • Jaro 2020
39/64
FACULTY
OF INFORMATICS
Masaryk University
Hyperkrychle
■ VeLmi zajímavá topologie
■ Obecně n-rozměrná krychle
■ Základní parametry
■ Poloměr log Ař
■ Bisection Ař/2
■ Redundance log Ař
■ Vyšší cena (AřlogAř)/2
■ Mřížky speciálními případy hyperkrychle
■ Snadné nalezení cesty
■ Binární číslování uzlů
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
Masaryk University
Plně propojené sítě
■ Teoretická konstrukce
■ Vynikající poloměr (1)
■ Neakceptovatelná cena (N * (N — l)/2) a stupeň uzlu (N — 1)
Luděk Matýska • Paralelní počítače • Jaro 2020
41/64
FACULTY
OF INFORMATICS
Masaryk University
Přepínání
■ Konkrétní mechanismus, jak se paket dostane ze vstupu na výstup
■ Základní přístupy
■ Přepínání paketů, store-and-forward
■ Přepínaní obvodů
■ Virtuální propojení (cut-through)
■ Směrování červí dírou (wormhole routing)
Luděk Matýska • Paralelní počítače • Jaro 2020
42/64
FACULTY
OF INFORMATICS
Masaryk University
Store-and-forward
■ CeLý paket se uloží
■ A následně přepošLe
■ Jednoduché (první generace paralelních počítačů)
■ Vysoká Latence | * D
■ P je délka paketu, B je propustnost a D je počet „hopů" (vzdálenost)
Luděk Matýska • Paralelní počítače • Jaro 2020
43/64
FACULTY
OF INFORMATICS
Masaryk University
Přepínání okruhů
■ Tři fáze
■ Ustavení spojení - zahájeno vzorkem (probe)
■ Vlastní přenos
■ Zrušení spojení
■ Výrazně nižší Latence | * D + ^
■ P je v tomto případě délka vzorku a M je délka zprávy (nejsou nutné pakety)
■ Pro P « M latence není závislá na délce cesty
Luděk Matýska • Paralelní počítače • Jaro 2020
44/64
FACULTY
OF INFORMATICS
Masaryk University
Virtuální propojení
■ Zprávu rozdělíme do menších bloků - flow control digits/units (flits)
■ První flits obsahuje informace o cestě (především cílovu ardresu)
■ Další flits-y obsahují vlastní data
■ Poslední flits ruší cestu
■ Posíláme jednotlivé flits-y kontinuálně
■ Jsou-li buffery dostatečně velké, odpovídá přepínání okruhů
■ Latence ^ * D + f
■ HF je délka flitsu, zpravidla HF << M
Luděk Matýska • Paralelní počítače • Jaro 2020
45/64
FACULTY
OF INFORMATICS
I   Masaryk University
Červí díra
■ Speciální případ virtuálního propojení
■ Buffery mají právě délku flits
■ Latence nezávisí na vzdálenosti
■ Analogie pipeline
■ Paket je rozložen v bufferech několika uzlů - odtud červľdľra
■ Uvažována latence přenosu celého paketu, ne jednotlivých flitsů; počet flitsů tvořících celý paket (zprávu) je mnohem větší než počet hopů po cestě
■ doba přenosu je dána součtem délky cesty a počtu přenesených flitsů
■ zatímco u store and forward je dána součinem těchto veličin
■ Podporuje replikace paketů
■ Vhodné pro multicast a broadcast
Luděk Matýska • Paralelní počítače • Jaro 2020
46/64
FACULTY
OF INFORMATICS
Masaryk University
Virtuální kanály
■ Sdílení fyzických kanálů
■ Několik bufferů nad stejným kanálem
■ Flits uložen v příslušném bufferu
■ Využití
■ Přetížená spojení
■ Zábrana deadlocku
■ Mapování logické na fyzickou topologii
■ Garance propustnosti systémovým datům
Luděk Matýska • Paralelní počítače • Jaro 2020
47/64
FACULTY
OF INFORMATICS
Masaryk University
Směrování v propojovacích sítích
■ Hledání cesty
■ Vlastnosti
■ Statické směrování
■ Zdrojové
■ Distribuované
■ Adaptivní směrování (vždy distribuované)
■ Minimální a ne-minimální
Luděk Matýska • Paralelní počítače • Jaro 2020
48/64
FACULTY
OF INFORMATICS
Masaryk University
Fault tolerance propojovacích sítí
■ Kontrola chyb
■ Potvrzování zpráv
■ Opakované zasílání zpráv
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
Masaryk University
Zpoždění paměti
■ Pamět výrazně pomalejší než procesor
■ Čekání na pamět podstatně snižuje výkon systému
■ Možná řešení:
■ Snľzenľm zpoždění- zrychlení přístupu
■ Ukrytím zpoždění- překryv přístupu a výpočtu
Luděk Matýska • Paralelní počítače • Jaro 2020
50/64
FACULTY
OF INFORMATICS
Masaryk University
Snížení zpoždění paměti
■ NUMA: Nonuniform Memory Access
■ Každé logické adrese odpovídá konkrétní fyzická adresa
■ COMA: Cache-Only Memory Architecture
■ Hlavní pamět je chápána jako attraction memory, m Řádky paměti se mohou volně přesouvat.
■ Mohou existovat sdílené kopie řádků paměti.
Luděk Matýska • Paralelní počítače • Jaro 2020
51/64
FACULTY
OF INFORMATICS
Masaryk University
Rekapitulace
Communication to computation ratio	NUMA		COMA	
	Small working set	Large working set	Small working set	Large working set
Low	Good	Medium	Good	Good
High	Medium	Poor	Poor	Poor
Luděk Matýska • Paralelní počítače • Jaro 2020
52/64
FACULTY
OF INFORMATICS
Masaryk University
Ukrytí zpoždění paměti
■ Modely slabé konzistence
■ Prefetch
■ Procesory s vícenásobnými kontexty
■ Komunikace iniciovaná producentem
Luděk Matýska • Paralelní počítače • Jaro 2020
53/64
FACULTY
OF INFORMATICS
Masaryk University
Slabá konzistence
■ Nepožaduje striktní uspořádání přístupů ke sdíleným proměným vyjma synchronizačních.
■ Release consistency:
■ Zavedení operací acquire a release
■ Fence operace
■ Vynucené dokončení rozpracovaných operací
Luděk Matýska • Paralelní počítače • Jaro 2020
54/64
FACULTY
OF INFORMATICS
Masaryk University
Prefetch
■ Přesun dat k procesoru s předstihem.
■ Binding prefetch
■ Data přesunuta až k procesoru
■ Možné porušení konzistence
■ Nonbinding prefetch
■ Data přesunuta pouze do vyrovnávací paměti
■ HW Prefetch
■ SW Prefetch
■ Speciální instrukce prefetch-exclusive: read následovaný příkazem write.
Luděk Matýska • Paralelní počítače • Jaro 2020
55/64
FACULTY
OF INFORMATICS
Masaryk University
Procesory s vícenásobnými kontexty
■ Podpora muLtitherading
■ Vyžaduje
■ Velmi rychlé přepnutí kontextu
■ Vysoký počet registrů
■ Řada experimentálních systémů
■ HEP(70. léta)
■ Tera
■ *T
Luděk Matýska • Paralelní počítače • Jaro 2020
56/64
FACULTY
OF INFORMATICS
Masaryk University
Komunikace iniciovaná producentem
■ Analogie invaLidace a update při cache koherenci
■ Špecifické využití pro message-passing (CrayT3D) nebo bLock-copy (počítače se sdílenou pamětí).
■ Vhodné např. pro přesun velkých bloků dat či pro synchronizaci zámky (Locks).
Luděk Matýska • Paralelní počítače • Jaro 2020
57/64
FACULTY
OF INFORMATICS
Masaryk University
Podpora synchronizace
■ Synchronizace tvoří „horká místa"
■ Základní synchronizační primitivy
■ Vzájemné vyloučení
■ Dynamické rozložení zátěže
■ Informace o událostech
■ Globální serializace (bariéry)
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
Masaryk University
Vzájemné vyloučení
■ K dané proměnné má v daném okamžiku přístup nejvýše jeden proces
■ Univerzální, ovšem zpravidla zbytečně drahé
■ Synchronizační konstrukce vyšších jazyků
■ Semafory
■ Monitory
■ Kritické oblasti
■ Základem - hardwarová podpora
■ test&set instrukce
■ test-and-test&set instrukce
Spin waiting protocol
Luděk Matýska • Paralelní počítače • Jaro 2020
59/64
FACULTY
OF INFORMATICS
Masaryk University
test & set
■ Vlastnosti char *Lock;
while (exchange(Lock, CLOSED) == CLOSED );
■ Busy waiting
■ Vysoké požadavky na přenos (časté znepLatnění) u muLtiprocerů
Luděk Matýska • Paralelní počítače • Jaro 2020
60/64
FACULTY
OF INFORMATICS
Masaryk University
test-and-test&set
■ Vlastnosti for (;;)
while flock == CLOSED);
if (exchange(Lock, CLOSED) != CLOSED)
break;
■ Využití vyrovnávacích pamětí
■ první testy nad sdílenou kopií
Luděk Matýska • Paralelní počítače • Jaro 2020
61/64
FACULTY
OF INFORMATICS
I   Masaryk University
Použití front
■ Výhodnější Collision avoidance schemata
■ Queue on Lock bit (QOLB) protokol
■ Nejefektivnější implementace
■ Procesy řazeny do fronty
■ Po uvolnění zámku aktivován proces v čele fronty
■ Není třeba žádný sdílený přenos dat
Luděk Matýska • Paralelní počítače • Jaro 2020
FACULTY
OF INFORMATICS
I   Masaryk University
Zámky v multiprocesorech
■ Souvisí i s možností dynamického rozložení zátěže
■ Využití čitače s atomickou operací
■ Fetch&Op - čitače, např. Op==Add
fetch&add (x, a) int *x, a; { int temp;
temp = *x;
*x += a;
return (temp);
}
■ Compare&Swap - seznamy
Luděk Matýska • Paralelní počítače • Jaro 2020
63/64
FACULTY
OF INFORMATICS
Masaryk University
Informace o (globálních) událostech používána především producentem jako prostředek, kterým jsou konzumenti informováni o nově dostupných datech, a dále při informaci o globální změně ve skupině ekvivalentních procesů (změna určitého stavu, která musí být oznámena všem procesům).
Luděk Matýska • Paralelní počítače • Jaro 2020
64/64