IA039 Paralelní počítače Paralelní počítače ■ Small-scale multiprocessing ■ 2-16 procesorů ■ převážně SMP (sdílená pamět) ■ Large-scale multiprocessing ■ > 100 (i tisíce) procesorů ■ Zpravidla distribuovaná pamět IA039 2 Paralelní počítače (II) ■ Architektura ■ Single Instruction Multiple Data, SIMD ■ Multiple Instruction Multiple Data, MIMD ■ Programovací modely ■ Single Program Multiple Data, SMPD ■ Multiple programs Multiple Data, MPMD IA039 3 Jaro 2011 Architektura - SIMD ■ Procesory synchronizovány ■ Všechny vykonávají vždy stejnou instrukci ■ Analogie vektorových procesorů ■ Jednoduché procesory ■ Jednodušší programovací model IA039 4 Jaro 2011 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í IA039 5 Jaro 2011 Komunikační modely ■ Sdílená pamět (Shared Memory Architecture) ■ Předávání zpráv (Message passing) IA039 6 Jaro 2011 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í) IA039 7 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 IA039 8 Hybridní systémy ■ Nonuniform memory access architecture (NUMA) ■ Cache-only memory access architecture (COMA) ■ Distributed shared-memory (DSM) IA039 9 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 IA039 10 Cache only memory access ■ N U MA s 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í IA039 11 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 IA039 12 Jaro 2011 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ů IA039 13 Jaro 2011 Řešení problému koherence ■ Vyrovávací paměti musí vědět o změně ■ Metody založené na broadcastu ■ Adresářové metody IA039 14 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 IA039 15 Jaro 2011 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 IA039 16 Jaro 2011 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ší IA039 17 Jaro 2011 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ů IA039 18 Jaro 2011 Zrychlení S{N) = Texec(i) texec(n) TcompiX) ~l~ TcornrniX) (N) Ideální zrychlení vyžaduje Tcomp(N) — Tcornp(\)/N Tcomm {N) = Tcornrn (1) /N IA039 19 Jaro 2011 Zrychlení - komentář ■ Teoretický pojem, realita závisí na aplikaci ■ Různé hodnoty pro různé aplikace ■ Vliv paralelizovatelnosti problému (Amdalův zákon) IA039 20 Jaro 2011 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 n ■ Propustnost rostoucí lineárně s n IA039 21 Jaro 2011 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) IA039 22 Propojovací sítě ■ Rozlišujeme následující základní parametry ■ Velikost sítě - počet uzlů n ■ 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 IA039 23 Jaro 2011 Bisection width ■ Šířka 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í. IA039 24 Jaro 2011 Topologie přepínacích sítí ■ Klasifikace na základě rozměru ■ Jednorozměrné ■ Dvourozměrné ■ Třírozměrné ■ Hyperkrychle IA039 25 Jaro 2011 Jednorozměrné propojovací sítě ■ Linerání pole ■ Jednotlivé prvky navázány na sebe - „Korálky" ■ Nejjednodušší ■ Nejhorší vlastnosti IA039 26 Jaro 2011 Dvourozměrné propojovací sítě ■ Kruh ■ Uzavřené lineární pole ■ Hvězda ■ Strom ■ Snižuje poloměr sítě (2 log ^=^) ■ Stále špatná redundance a bisection (band)width ■ Tlustý strom (fat tree) * Přidává redundantní cesty ve vyšších úrovních IA039 27 Dvourozměrná mřížka ■ Velmi populární ■ Dobré vlastnosti * Poloměr 2{nx'2 - 1) * Bisection AT1/2 * Redundance 2 ■ Avšak vyšší cena a proměnný stupeň uzlu ■ Torus ■ Uzavřená dvourozměrná mřížka * Poloměr n1/2 * Bisection 2AT"1/2 * Redundance 4 IA039 * Vyšší cena - přidá 2AT1/2 hran 28 Třírozměrná sít ■ Vlastnosti ■ Poloměr 3(AT1/3 _ ■ Bisection AT2/3 ■ Redundance 3 ■ Cena akceptovatelná 2(n — AT"2/3) ■ Konstrukčně složitá IA039 29 Hyperkrychle ■ Velmi zajímavá topologie ■ Obecně n-rozměrná krychle ■ Základní parametry ■ Poloměr log n ■ Bisection n/2 ■ Redundance log AT ■ Vyšší cena (n log AT") /2 ■ Mřížky speciálními případy hyperkrychle ■ Snadné nalezení cesty ■ Binární číslování uzlů IA039 30 Plně propojené sítě ■ Teoretická konstrukce ■ Vynikající poloměr (1) ■ Neakceptovatelná cena (N * (N — l)/2) a stupeň uzlu (N — 1) IA039 31 Jaro 2011 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) IA039 32 Jaro 2011 S t o r e-a n d -f o r wa rd ■ 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) IA039 33 Jaro 2011 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 IA039 34 Jaro 2011 Virtuální propojení ■ Zprávu rozdělíme do menších bloků - flow control digits (flits) ■ Posíláme jednotlivé flits kontinuálně ■ Jsou-li buffery dostatečně velké, odpovídá přepínání okruhů ■ Latence ^f- * D + ^ hf je délka flitsu, zpravidla hf « m IA039 35 Jaro 2011 Č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 ■ Podporuje replikace paketů ■ Vhodné pro multicast a broadcast IA039 36 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 IA039 37 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í IA039 38 Fault tolerance propojovacích sítí ■ Kontrola chyb ■ Potvrzování zpráv ■ Opakované zasílání zpráv IA039 39 Jaro 2011 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í) IA039 40 Adresářové přístupy ■ Tři základní schémata ■ Plně mapované adresáře ■ Čá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 IA039 41 Jaro 2011 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 IA039 42 Jaro 2011 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 IA039 43 Jaro 2011 Omezené adresáře II ■ 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 < ■ Informovány jen explicitně uvedené vyrovnávací paměti IA039 44 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) IA039 45 Jaro 2011 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í IA039 46 Jaro 2011 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) IA039 47 Jaro 2011 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ů IA039 48 Jaro 2011 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ížením zpoždění- zrychlení přístupu ■ Ukrytím zpoždění- překryv přístupu a výpočtu IA039 49 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. ■ Řádky paměti se mohou volně přesouvat. ■ Mohou existovat sdílené kopie řádků paměti. IA039 50 Rekapitulace NUMA COMA Communication Small Large Small Large to computation work- work- work- work- ratio ing ing ing ing set set set set Low Good Medium Good Good High Medium Poor Poor Poor IA039 51 Jaro 2011 Ukrytí zpoždění paměti ■ Modely slabé konzistence ■ Prefetch ■ Procesory s vícenásobnými kontexty ■ Komunikace iniciovaná producentem IA039 52 Jaro 2011 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í IA039 53 Jaro 2011 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. IA039 54 Jaro 2011 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 IA039 55 Jaro 2011 Komunikace iniciovaná producentem ■ Analogie invalidace a update při cache koherenci ■ Specifické využití pro message-passing (Cray T3D) 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). IA039 56 Jaro 2011 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) IA039 57 Jaro 2011 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 IA039 Spin waiting protocol 58 Jaro 2i test&set ■ Vlastnosti char *lock; while (exchange(lock, CLOSED) == CLOSED ); ■ Busy waiting ■ Vysoké požadavky na přenos (časté zneplatnění) u multiprocerů IA039 59 Jaro 2011 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í IA039 60 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 IA039 61 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 IA039 62 Použití 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). IA039 63 Jaro 2011