IAO39 Paralelní počítače Paralelní počítače ■ Small-scale multiprocessing ■ 2-16 procesoru ■ převažne SMP (sdílena pamet) ■ Large-scale multiprocessing ■ > 100 (i tisíce) procesoru ■ Zpravidla distribuovana pameit IA039 2 Jaro 2010 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 IAG39 3 Jaro 2G1G Architektura - SIMD ■ Procesory synchronizovány ■ VSechny vykonávají vZdy stejnou instrukci ■ Analogie vektorovych procesoru ■ Jednoduche procesory ■ Jednodussí programovací model IA039 4 Járo 2010 Architektura - MIMD ■ Plne asynchronní systém ■ Procesory zcela samostatné ■ Není treba speciainí vyroba (off-the-shélf) ■ Vyhody ■ Vyssí flexibilita ■ Teoreticky vyssí efektivita ■ Nevyhody ■ Explicitní synchronizace ■ SloZite programovaní IA039 5 Jaro 2010 Komunikační modely ■ Sdílená pamět (Shared Memory Architecture) ■ Předávání zpráv (Message passing) IA039 6 Jaro 2010 Sdílená pamět ■ Pamět odelena od procesorů ■ Uniformní prístůp k paměti ■ NejsnazSí propojení - sběrnice ■ „Levná" komunikace ■ SloZite prokladaní výpoCtů a komunikace (aktivní Cekaní) IA039 7 Jaro 2010 Předávání zpráv ■ Každý procesor „viditelný" ■ Vlastní pameř u každého procesoru ■ Explicitní komunikace - předavaní žprav ■ Výsoka cena komunikace (výmený dat) ■ Možnost prokiadaní výpoctU a komunikace IA039 8 Jaro 2010 Hybridní systémy ■ Nonuniform memory access architecture (NUMA) ■ Cache-only memory access architecture (COMA) ■ Distributed shared-memory (DSM) IA039 9 Jaro 2010 Non-uniform memory access ■ Přístup k různým fyzickým adresám trvá různou dobu ■ UmoZnuje vySSí Skálovatelnost ■ Potenciálne niZSí propostnost ■ Koherence vyrovnávacích pametí ■ ccNUMA IA039 10 Jaro 2010 Cache only memory access ■ NUMA s charakterem vyrovnávací paměti ■ Data putují k procesorům, kterě je používají ■ Použe ždanliva hierarchie ■ System musí hlídat, že ma jedinou kopii ■ Experimentalní IA039 11 Jaro 2010 Distributed shared-memory ■ Distribuovaný systém - cluster ■ Lokainí pamét každého uzlu ■ Vzdálena pamét ostatních uzlU „Fikce" jedné rozsahlé paméti ■ Hardwarové řéséní ■ Zpravidla vyuzíva principu virtualní paméti ■ Transparéntní ■ Softwarové řéséní ■ Knihovna ■ Nétransparéntní, progamator program musí éxplicitné prizpusobit IA039 12 Jaro 2010 Koherence vyrovnávacích pamětí ■ Příčiny výpadku vyrovnávací paměti: ■ Compulsory miss: 1. prístup kdatUm ■ Capacity miss: nědostatěčna kapacita ■ Conflict miss: rUzně adresy mapovaný do stějněho místa ■ Coherence miss: rUzna data v rUzných vyrovnávacích pamětích ■ Poslědní případ sě tyka multiprocěsorU IA039 13 Jaro 2010 Řešení problému koherence ■ Vyrovávací paměti musí vedet o změně ■ Metody zaloZeně na broadcastu ■ Adresařové metody IA039 14 Jaro 2010 Snoopy cache ■ Broadcastový přístup ■ Propojovací sítě s „přirozeným" brodcastem - sběrnice ■ KaZdý procesor sleduje všechny prístupy k paměti IA039 15 Jaro 2010 Zneplatnení ■ Reakce na zmenu dat ve vzdálene (vyrovnávací) pameti ■ Rádka v aktuální (naslouchající) vyrovnávací pameti je zneplatneřna ■ V prípade opetneho přístupu je přehrána ze vzdálene pameti IA039 16 Jaro 2010 Updáte ■ Radka je okamžite obnovena ■ Při opetovnem prístupu je již k dispožici ■ Nevýhodý ■ Falesne sdílení (nepracují na stejných datech) ■ Prílisne žatížení sbernice ■ Nelže rožhodnout, žda update nebo žneplatnení je obecne lepsí IA039 17 Jaro 2010 Rozšiřitelnost (Scalability) ■ Není jednotna definice ■ PoůZívane zakladní formulace - rozsiritelný je takový sýstenm, pro nejZ platí: ■ Výkon roste linearne s cenoů ■ Je zachovan konstantní pomer Cena/Výkon ■ Alternativní parametr - Míra rozšiřitelnosti ■ Zmena výkonů pridaním procesorů ■ Zmena cený pridaním procesorů ■ Smýslůplný rozsah poctů procesorů IA039 18 Jaro 2010 Zrychlení S (N) = TEXEC (1) TEXEC (N) Tcomp(1) + Tcomm(1) Tcomp(N) + Tcomm (N) Idealní žrýchlení výžřaduje Tcomp(N) — Tcomp(1)/N Tcomm(N) — Tcomm(1)/N IA039 19 Jaro 2010 Zrychleni - komentár Teoretický pojem, realita závisí na aplikaci ■ Různe hodnoty pro různe aplikace ■ Vliv paralelizovatelnosti probiemů (Amdalův zakon) IA039 20 Jaro 2010 Rozšiřitelné propojovací site ■ PoZadavký na ideainí sílí: ■ Nízka cena rostoucí linearne s poctem procesoru (N) ■ Minimální latence nezávisia na N ■ Propustnost rostoucí linearne s N IA039 21 Jaro 2010 Vlastnosti sítí ■ Tři základní komponenty ■ Topologie ■ Přepínání dat (jak se data pohybují mezi uzly) ■ Smerovaní dat (jak se hleda cesta mezi uzly) IA039 22 Jaro 2010 Propojovací sítě ■ Rozlisujémé naslédující zakladní paramétry ■ Vélikost síté - pocét uzlu N ■ Stupén uzlu d ■ Polomér sítéé D * Néjdélsí néjkratsí césta ■ Biséction width B ■ Rédundancé síté A * Minimalní pocét hran, ktéré jé tréba odstranit, aby sé sít rozpadla na dvé ■ Céna C * Pocét komunikacních linék v síti IA039 23 Jaro 2010 Bisection width ■ Sírka rožpulení ■ Minimalní pocet linek, ktere je třeba odstranit, aby se systém rožpadl na dve stejne casti ■ Bisection bandwidth - propustnost pri rožpulení ■ Celkova kapacita (propustnost) vyse odstranenych linek ■ Idealní vlastnost: ■ Bisection badnwidth vžtažena na procesor je v danem systemu konstantní. IA039 24 Jaro 2010 Topologie přepínacích sítí ■ Klasifikace na základě rozměru ■ Jednorozměrně ■ Dvourozměrně ■ Třírozměrně ■ Hypěrkrychlě IA039 25 Jaro 2010 Jednorozměrné propojovací sítě ■ Lineraní pole ■ Jednotlive prvky navazany na sebe ■ „Koralky" ■ Nejjednodussí ■ Nejhorsí vlastnosti IA039 26 Jaro 2010 Dvourozměrné propojovací sítě ■ Kruh ■ Uzavřené lineární pole ■ Hvézda ■ Strom ■ SniZuje polomer síté (2 log ^2+1) ■ Stále Spatná redundance a bisection (band)width ■ Tlustý strom (fat tree) * Pridava redundantní cestý ve výssích Úrovních IA039 27 Jaro 2010 Dvourozmerná mřížka ■ Vělmi popUlarní ■ Dobrě vlastnosti * Poloměr 2(N1/2 - 1) * Bisěction N1/2 * RědUndancě 2 ■ Avsak vyssí cěna a proměnny stUpěn uzIu ■ Torus ■ Uzavrěna dvourozměrna mrízka * Poloměr N1/2 * Bisěction 2N1/2 * Rědundancě 4 iao39 * Vyssí cěna - přida 2N1/2 hran 28 jaro 2010 Třírozměrná sít ■ Vlastnosti ■ Poloměr 3(N1/3 - 1) ■ Bisěction N2/3 ■ Redundance 3 ■ Cena akceptovatelná 2(N - N2/3) ■ KonstrukCne slozita IA039 29 Jaro 2010 Hyperkrychle ■ Velmi zajlmava topologie ■ Obecne n-rozmeerna krychle ■ Zakladnl parametry ■ Polomeer log N ■ Bisection N/2 ■ Redundance logN ■ VySSI cena (N log N) /2 ■ MriZky specialnimi pripady hyperkrychle ■ Snadne nalezeni cesty ■ Binarni cislovani uzlU IA039 30 Jaro2010 Plne propojené síte ■ Teoretická konstrukce ■ Vynikající polomer (1) ■ Neakceptovatelná cena (N * (N — l)/2) a stupen uzlu (N — 1) IA039 31 Jaro 2010 Přepínaní ■ Konkretní mechanismus, jak se paket dostane že vstupu na vystup ■ Zakladní prístupy ■ Přepínaní paketu, store-and-forward ■ Prepínaní obvodu ■ Virtualní propojení (cut-through) ■ Smerovaní cerví dírou (wormhole routing) IA039 32 Jaro 2010 Store-and-f orward Celý paket se uloží A nasledne přepoSle Jednoduché (první generace paralelních počítačU) Výsoka latence p * D ■ P je delka paketu, B je propustnost a D je pocet „hopU" (vždalenost) IA039 33 Jaro 2010 Prepínaní okruhu ■ Tři faze ■ Ustavení spojení - zahajeno vzorkem (probe) ■ Vlastní přenos ■ Zrusení spojení ■ Výrazne nizsí latence p * D + M P je v tomto případe delka vzorku a M je delka zpravý (nejsou nutne paketý) ■ Pro P << M latence není zavisla na delce cestý IA039 34 Jaro 2010 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 dostáteCne velke, odpovídá přepínání okruhů ■ Látence HF * D + M ■ HF je delká flitsu, zprávidlá HF << M IA039 35 Járo 2010 Cěrví díra Specialní prípad virtualního propojení Bufferý mají prave delku flits Latence nezavisí na vzdalenosti Podporuje replikace paketu ■ Vhodne pro multicast a broadcast IA039 36 Jaro 2010 Virtuální kanály ■ Sdílení fyzickych kanálu ■ Nekolik bufferu nad stejnym kanálem ■ Flits ulozen v príslusnem bufferu ■ Vyuzití ■ Přetízená spojení ■ Zábrana deadlocku ■ Mapování logicke na fyzickou topologii ■ Garance propustnosti systemovym datum IA039 37 Jaro 2010 Směrování v propojovacích sítích ■ Hledání cesty ■ Vlastnosti ■ Státicke směrování * Zdrojově * Distribuováně ■ Adaptivní směrování (vždy distribuováně) ■ Minimální á ně-minimální IA039 38 Járo 2010 Fault tolerance propojovacích sítí ■ Kontrola chyb ■ Potvrzovaní zprav ■ Opakované zasílaní zprav IA039 39 Jaro 2010 Koherence vyrovnávacích pamětí II ■ Snoopy schema založené na broadcastu ■ Nepoužitelné u složitéjSích propojovacích sítí ■ Není rozsiritelne (scalable) ■ Redukce „oslovených" vyrovnavacích pametí - Adresare ■ Položka u každeho bloku pameti ■ Odkažy na vyrovnavací pameti s kopií tohoto bloku ■ Ožnacení exkluživity (pravo pro ctení) IA039 40 Jaro 2010 Adresářové přístupy ■ Tři základní schémata ■ Plné mapované adresáře ■ ČasteCné (Limited) mapované adresaře ■ Provazané (chained) adresaře ■ Zhodnocení vlastností ■ Na zaklade velikosti potřebné paméti ■ Na zaklade sloZitosti (poCtu příkazů) protokolu IA039 41 Jaro 2010 Plně mapované adresáře ■ Každá adresářová položka má tolik údajů, kolik je vyrovnávacích pamětí (procesorů) ■ Bitovy vektor „přítomnosti" ■ Nastaveny bit znamená, že príslůSná vyrovnávací data má kopii bloků pameti ■ Prížnak exkluzivity ■ Stací jeden na blok ■ Jen jedna vyrovnávací pamet ■ Příznaky v každe vyrovnávací pameti (každy blok) ■ Prížnak platnosti Prížnak exklúživity IA039 42 Jaro 2010 Omězěně adrěsarě ■ Plné adrésařé vélmi paméřové narocné ■ Vélikost paméti: P2M/B * P jé pocét vyrovnavacích pamétí * M vélikost hlavní paméti * B vélikost bloku ■ Data néjsou zpravidla sirocé sdíléna ■ Vétsina adrésařovych bitu ma hodnotu nula ■ Pouzití prímych odkazu ■ Nébudé jiz stacit jédén bit IA039 43 Jaro 2010 Omezené adresáře II Množina ukazatelů na vyrovnávací paměti ■ Dynamicka alokace dle potřeby Vlastnosti ■ PoCet bitů ukazatele: log2 P ■ PoCet položek v poolu ukazatelů: k ■ VyhodnejSí než přímo mapovana: pokud k < p log2 P Informovaný jen explicitnee uvedene výrovnavací pameti IA039 44 Jaro 2010 Přetečení ■ Pokud přestanou stačit položky ■ PříliS mnoho sdílených blokU ■ Možne reakce ■ Zneplatnení vSech sdílených (brodcast, Dir.B) ■ Vyber jedne položky (i nahodne) a její žneplatnení (bež broadcastu, Dir.NB) IA039 45 Jaro 2010 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řetecení * Omezeny broadcast vSem procesorům v oblasti. LimitLESS: programová přerusení pri přetecení IA039 46 Jaro 2010 Provázaná schemata ■ Cache-Based linked-list ■ Centraine pouze jediný ukazatel ■ Ostatní ukazatele svazaný s výrovnavací pametí ■ Výrovnavací pameti „provazaný" ukazateli ■ Výhodý ■ Minimalizace pametových narokU ■ Nevýhodý: ■ Slozitý protokol. ■ Zvýsena komunikace (více zprav nez nutno) ■ Zapis je delsí (sekvencní prochazení seznamu) IA039 47 Jaro 2010 Hierarchické adresáře ■ Pouzité v systémech s vícenásobnými sbérnicemi ■ Hierarchie vyrovnávacích pamétí ■ Vyssí ůroven na kazdém propojení sbérnic ■ Vyssí paméfové naroky * Vyssí ůroven musí drzet kopie pamétovych bloků sdílenych nizsí ůrovní * Není třeba rychla pamét ■ V principů hierarchie snoopy protokolů IA039 48 Jaro 2010 ZpoZdení pameti ■ Pamet výrazne pomalejší než procesor ■ Čekaní na pamet podstatne snižuje výkon sýstemu ■ Možna řesení: ■ Snížením zpoždění - zrýchlení prístupu ■ Ukrytím zpoZdení- překrýv prístupu a výpoctu IA039 49 Jaro 2010 Snížení zpoždění paměti ■ NUMA: Nonuniform Memory Access ■ Kazde logicke adrese odpovída konkretní fýzicka adresa ■ COMA: Cache-Onlý Memorý Architecture ■ Hlavní pamet je chapana jako attraction memory. ■ Radký pameti se mohou volne presouvat. ■ Mohou existovat sdílene kopie řadku pameti. IA039 50 Jaro 2010 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 2010 Ukryti zpožděni paměti Modély slabé konzisténcé Préfétch Procésory s vícénasobnymi kontéxty Komunikacé iniciovana producéntém IA039 52 Jaro 2010 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 ■ Vynucene dokoncení rozpracovaných operací IA039 53 Jaro 2010 Prefetch ■ Přesun dat k procesoru s predstihem. ■ Binding prefetch * Data přesunuta až k procesoru * Možne porusení konžistence ■ Nonbinding prefetch * Data presunuta použe do vyrovnavací pameti ■ HW Prefetch ■ SW Prefetch ■ Specialní instrukce prefetch-exclusive: read nasledovany príkažem write. IA039 54 Jaro 2010 Procesory s vícenásobnými kontexty ■ Podpora můltitherading ■ Vyzadůje ■ Velmi rychlé prepnůtí kontextů ■ Vysoky pocet registrů ■ Rada experimentalních systémů ■ HEP (70. léta) ■ Tera ■ *T IA039 55 Jaro 2010 Komunikace iniciovaná producentem Analogie invalidace a update pri cache koherenci Specifické využití pro message-passing (Cray T3D) nebo block-copy (pocítace se sdílenou pametí). Vhodne např. pro přesun velkých blokU dat ci pro synchronizaci žaamky (locks). IA039 56 Jaro 2010 Podpora synchronizace ■ Synchronizace tvoří „horká místa" ■ Základní synchronizační primitivy: ■ Vzájemné vyloučení ■ Dynamické rozloZení zátéZe ■ Informace o udalostech ■ Globalní serializace (bariery) IA039 57 Jaro 2010 Vzájemně vyloučení ■ K dane promenne má v danem okamžiků prístúp nejvyse jeden proces ■ Univeržální, ovsem žpravidla žbytecne drahe ■ Synchronižacní konstrůkce vyssích jažyků ■ Semafory ■ Monitory ■ Kriticke oblasti ■ Základem - hardwarová podpora ■ test&set instrůkce ■ test-and-test&set instrůkce IA039 Spin waiting protocol 58 Jaro 2010 test&set ■ Vlastnosti char *lock; while (exchange(lock, CLOSED) == CLOSED ); ■ Busy waiting ■ Vysoke pozadavky na prenos (caste zneplatnení) u multiproceru IA039 59 Jaro 2010 test-and-test&set ■ Vlastnosti for (;;) while (*lock == CLOSED); if (exchange(lock, CLOSED) != CLOSED) break; ■ Využití vyrovnávacích pametí ■ první testy nad sdílenou kopií IA039 60 Jaro 2010 Použití front ■ Výhodnější Collision avoidance schemata ■ Queuě on lock bit (QOLB) protokol ■ Nějěfěktivnější implementace ■ Procěšý razený do frontý ■ Po uvolnení zamku aktivován proces v Cele frontý ■ Není třeba zadný sdílený prenos dat IA039 61 Jaro 2010 Zámky v multiprocesorech Souvisí i s možností dynamického rozložení zátěže Využití CitaCe s atomickou operací ■ Fetch&Op - CitaCe, např. Op==Add fetch&add (x, a) int *x, a; { int temp; temp = *x; *x += a; return (temp); } ■ Compare&Swap - seznamy IA039 62 Jaro 2010 PouZití Informace o (globalních) udaalostech používana předevsím producentem jako prostředek, kterým jsou konzumenti informovani o nove dostupných datech, a dale při informaci o globalní zmene ve skupine ekvivalentních procesu (zmena urciteho stavu, ktera musí být oznamena vsem procesum). IA039 63 Jaro 2010