IA039 Paralelní počítače Paralelní ■ Small-scale multiprocessing ■ 2-16 procesorů ■ převážně SMP (sdílená parmět) ■ Large-scale multiprocessing ■ > 100 (i tisíce) procesorů ■ Zpravidla distribuovaná parmět IA039 2 očítače Jaro 2009 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 2009 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 2009 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 2009 Komunikační modely ■ Sdílená pamět (Shared Memory Architecture) ■ Předávání zpráv (Message passing) IA039 6 Jaro 2009 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 Jaro 2009 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 Jaro 2009 Hybridní systémy ■ Nonuniform memory access architecture (NUMA) ■ Cache-only memory access architecture (COMA) ■ Distributed shared-memory (DSM) IA039 9 Jaro 2009 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 Jaro 2009 Cache only memory access ■ N U M A 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 Jaro 2009 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í, progamator program musí explicitně přizpůsobit IA039 12 Jaro 2009 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 2009 Ř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 Jaro 2009 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 2009 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 2009 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 2009 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 2009 Zrychlení S (N) = Texec{1) TEXEC(N) J-compy*-) \ J-comm\±) (N) Ideální zrychlení vyžaduje J-comp\^) — J-comp\J-)/^ J-comrny^ ) = J-commy*-) f™ IA039 19 Jaro 2009 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 2009 Rozšiřitelné propojovací sítě ■ Požadavky na ideální sít: ■ Nízka 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 2009 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 Jaro 2009 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 2009 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 2009 Topologie přepínacích sítí ■ Klasifikace na základě rozměru ■ Jednorozměrné ■ Dvourozměrné ■ Třírozměrné ■ Hyperkrychle IA039 25 Jednorozměrné propojovací sítě ■ Linerání pole ■ Jednotlivé prvky navázány na sebe - „Korálky" ■ Nejjednodušší ■ Nejhorší vlastnosti IA039 26 Jaro 2009 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(iV1/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 AT1/2 * Bisection 2ÍV1/2 * Redundance 4 IA039 * Vyšší cena - přidá 2ÍV1/2 hran 28 Třírozměrná sít ■ Vlastnosti ■ Poloměr 3(N^3 - 1) ■ Bisection AT2/3 ■ Redundance 3 ■ Cena akceptovatelná 2(N - AT2/3) ■ Konstrukčně složitá IA039 29 Jaro 2009 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 N)/2 ■ Mřížky speciálními případy hyperkrychle ■ Snadné nalezení cesty ■ Binární číslování uzlů IA039 30 Jaro 2009 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 2009 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 2009 Sto re-a n d-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) IA039 33 Jaro 2009 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 2009 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 2009 Červí díra ■ Speciální případ virtuálního propojení ■ Buffery mají právě délku flits ■ Latence nezávisí na vzdálenosti ■ Podporuje replikace paketů ■ Vhodné pro multicast a broadcast IA039 36 Jaro 2009 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 Jaro 2009 Fault tolerance propojovacích sítí ■ Kontrola chyb ■ Potvrzování zpráv ■ Opakované zasílání zpráv IA039 39 Jaro 2009 Koherence vyrovnávacích pamětí II ■ Snoopy schema 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 Jaro 2009 Adresářové přístupy ■ Tři základní schemata ■ 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 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 2009 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 2009 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 < j—^-p ■ Informovány jen explicitně uvedené vyrovnávací paměti IA039 44 Jaro 2009 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 2009 Dalsi 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 2009 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 2009 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 pametových bloků sdílených nižší úrovní * Není třeba rychlá pamět ■ V principu hierarchie snoopy protokolů IA039 48 Jaro 2009 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í parmě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 Jaro 2009 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 IA039 51 Jaro 2009 Ukrytí zpoždění paměti ■ Modely slabé konzistence ■ Prefetch ■ Procesory s vícenásobnými kontexty ■ Komunikace iniciovaná producentem IA039 52 Jaro 2009 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 2009 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 2009 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 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 2009 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 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 2009 test-and-test&set ■ Vlastnosti for (;;) while (*lock== CLOSED); if (exchange(lock, CLOSED) != CLOSED) break; ■ Využití vyrovnávacích pamětí ■ první testy nad sdílenou kopií IA039 60 Jaro 2009 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 Jaro 2009 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, napr. Op==Add fetch&add (x, a) int *x, a; { int temp; temp = *x; *x += a; return (temp); } ■ Compare&Swap - seznamy IA039 62 Jaro 2009 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 2009