Skripta

í sítětoeoretická konstrukcevynikající poloměr (1)každý je propojen s každýmneakceptovatelná cena (N * (N – 1)/2) a stupeň uzlu (N -1)PřepínáníKonkrétní mechanismus, jak se paket dostane ze vstupu na výstupZákladní přístupymůžeme si dovolit základní vlastnostipřepínání paketů, store-and-forward (celý paket se uloží, a následně přepošle, jednoduché (uměla první generace paralelních počítačů), vysoká latence P/B * D, P – délka paketu, B je propustnost, D je počet hopů (vzdálenost))přepínání okruhů3 fáze – můžeme nekteré fáze odstranit, pokud už dopředu známe cestu a máme připraveny prvky na přenos dat, ustavení spojení – zahájeno vzorkem (probe – jen při navazování spojení)Vlastní přenoszrušení spojenívýrazně nižší latence – pokud je délka posílaného vzorku je výrazně menší než délka zprávy, pak latence nezávisí na délce cestyvirtuální propojení (cut-through)komplikuje vytvořit kopii posílaných datZprá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 HF/B * D + M/BHF je délka flitsu, zpravidla HF převažují nuly místo jedničekkaždá adresářová položka má tolik údajů, kolik je vyrovnávacích pamětí (procesorů) - každý bit odpovídá procesoru bit exkluzivity a platonostiserializují se procesy tak, aby nedošlo k blokaci (2 procesy chtějí zapsat na stejné místo)při zápisu se posílá zpráva invalid (jen tem, kteří mají stejná data)-> nepoužívá se update, minimaluzuje se provozčástečně (limited) mapované adresářePlné adresáře velmi paměťově náročnévelikost paměti P*P*M/BP je počet vyrovnávacích pamětíM velikost hlavní pamětiB velikost blokuData nejsou zpravidla široce sdílenávětšina adresářových bitů má hodnotu nulaPoužití přímých odkazů (nestačí již jeden bit)Množina ukazatelů na vyrovnávací paměti (dynamická alokace dle potřeby)Vlastnostipočet bitů ukazatele je logaritmický (log P)počet položek v poolu je konstantní (k)výhodnější než přímo mapovaná pokud k < p/ log PInformovány jen explicitně uvedené vyrovnávací pamětifungují velice omezenětím, že držíme pool malý může dojít k přetečení – nemáme volný ukazatelzneplatnit všechna data příslušného paměťového bloku (broadcast)výběr oběti (i náhodně) a její zneplatnění (bez broadcastu, uložení do další paměti)provázané (chained) adresářeCoarce-vectorr je velikost regionu (více procesorů), kterému odpovídá jeden bit (tedy víceprocesorů)ke každému bloku vyrovnávací paměti přidáme jeden ukazatel. přepnutí interpretace při přetečeníOmezený broadcast včem procesorům v oblastinemůžeme poslat paralelně, latence při dosažení posledního i zneplatňování dat, nový se přidává na začátek. Vhodné při zacházení s pamětí (minimalizace paměťových nároků)ostatní ukazatele svázány s vyrovnávací pamětí (provázaný)nevýhody – složitý protokol, zvýšená komunikace, zápis je delší (sekvenční procházení seznamu – požadavek na exkluzivitu)Hierarchické adresáře (sběrnic)dobře funguje snoopy protokol – hierarchie sběrnic broadcast není drahý na sběrniciomezení broadcastu na určitou větev stromu sběrnic použitelné v systémech s vícenásobnými sběrnicemihierarchie vyrovnávacích pamětivyšší úroveň na každém propojení sběrnicemivyšší paměťové nárokyVyšší úroveň musí držet kopie paměťových bloků sdílených nižší úrovníNení třeba rychlá paměť Zpoždění pamětípaměť výrazně pomalejší než procesor (čekání snižuje výkon systému)řešenísnížení zpoždění – zrychlení přístupuUkrytí zpoždění – překryv přístupu a výpočtuSnížení zpožděníNUMAkaždé logické adrese odpovídá konkrétní fyzická adresasnaží se minimalizovat latenci přístup do paměti přiblížením k procesoru (sdílená paměť)COMAhlavní paměť je chápána jako attraction memoryřádky paměti se mohou volně přesouvatmohou existovat sdílené kopie řádků pamětihierarchie vyrovnávacích pamětí – iluze dostatku volné pamětivždy bude zpoždění pamětiUkrytí zpožděníZaměstnat procesor, když se čeká na paměť. ANDES realizuje ukrytí, přeposklládání instrukcí tak, aby byl procesor zaměstnán.Modely slabé konzistenceNepožaduje striktní uspořádání přístupům ke sdíleným proměnným vyjma synchronizačních.Release consistencyzavedení operací acquire a release – synchronizace, kritická sekceFence operace – vynucené dokončení rozpracovaných operacíodpovídala v ANDES instrukci tomu, aby se vyprázdnil pool s instrukcemi. Doběhnete co máte a nezačínejte znova. V ANDES to nemá smysl jen příklad na přiblížení. Vyčištění procesoru.Nemůžeme pokračovat dál ve výpočtu dokud není celek dokončen.prefetch – stav, kdy sáhneme do paměti s dostatečným předstihem než budou potřebapřesun dat k procesoru s předstihembinding prefetch – data k procesoru, možné porušení konzistenceload do registru a očekáváme, že v registru data jsou. Nepočítáme s tím, že někdo jiný nám data přepíše. Může snížit efektivitu výpočtu nebo se poruší konzistence. nonbinding prefetch – data přesunuta pouze do vyrovnávací pamětis klady i zápory vyrovnávací pamětiHW (vyrovnávací paměť, nebo ANDES styl) vs. SW prefetch (podpora kompilátorů)Speciální instrukce prefetch-exclusive: read následovaný příkazem write.Procesory s vícenásobnými kontexty podpora multithreading – virtualizace jednoho procesoru do dvou procesorůvzniká s NUMA architekturou.vyžadujevelmi rychlé přepnutí kontextuvysoký počet registrůřada experimentálních systémůHEP (70.let)TeraKomunikace iniciovaná producentemAnalogie invalidace a update při cache koherenciMáme 2 procesory P producent a K konzument a NUMA architekturu. Standardní přístup, producent data vytvoří a zapíše je do své paměti, konzument o ně požádá a pak jsou data přenesena nebo na ně bude sahat do vzdálené paměti. Pokud si představíme, že jsme v plně distribuovaném systému bez NUMA architektury, P a K komunikují pomocí zpráv. Probíhá celá řada operací, které jsou zbytečné. Lepší, obejití složitého protokolu - Konzument řekne producentovi kam má uložit data až je vytvoří, HW podpora, tak je přesune a vyhne se tak tomu druhému procesoru. Existuje přímá komunikace se vzdálenou pamětí (RDMA),občas je lepší něco spočítat znovu než číst z paměti.Specifické využití pro message-passing (Cray T3D) nebo block-copy (počítače se sdílenou pamětí)Konzument řekne producentovi kam má data zapsatVhodné např. Pro přesun velkých bloků dat či pro synchronizaci zámky (locks)Podpora synchronizaceSynchronizace tvoří „horká místa“ - mnoho čeká na událostzákladní synchronizační primitivyvzájemné vyloučeníDynamické rozložení zátěžeInformace o událostech – informuji, že už jsem ve stavu.Globální serializace (bariéry) – všichni se zastaví a pak na signál mohou pokračovatVzájemné vyloučeníK dané proměnné má v daném okamžiku přístup nejvýše jeden procesuniversální, ovšem zpravidla zbytečně drahéSynchronizační konstrukce vyšších jazykůsemaforymonitorykritické sekceHW podporatest&set instrukce – HW podpora kvůli atomicitě, nesmí být přerušenapodívá se na aktuální hodnotu zámku, vrátí tuto hodnotu a zároveň nastaví hodnotu zámku pro ostatnímusí být atomickou organizací (while (exchange(lock, CLOSED)==CLOSED))busy waitingvysoké požadavky na přenos (časté zneplatnění ) u multiprocesorůtest-and-test&set instrukce prvně se dotáži jestli můžu a pak provedu jestli můžuprvní test dělám na lokální vyrovnávací pamětipři uvolnění se řekne jednomu procesoru, který může do KS – vhodné použití frontvýhodnější Collision avoidance schemaQueue on lock bit (QOLB) protokolnejefektivnějšíprocesy do frontSpin waiting protokolZámky v multiprocesorechsouvisí i s možností dynamického rozložení zátěževyužití čítače s atomickou operacízvyšování čítače a vrací se jeho hodnota – musí se provést jako atomická operacePouž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)Překlad a překladačeOptimalizující překladačezákladní principy práce překladačemezijazyk – překládá se do kódu, kterému rozumí procesorčtveřice (obecně n-tice)Instrukce: operátor, dva operandy, výsledekpaměť: přes dočasné proměnnéskoky: podmínka počítána samostatněskoky: na absolutní adresypracuje na principu základního blokuprogram je pak reprezentován grafem toku (flow graph)blok – část programu bez skokůjeden vstupní a jeden výstupní bodBlok jako DAG (Direct Acyclic Graph)Optimalizace uvnitř blokůodstranění opakovaných (pod) výrazůodstranění přebytečných proměnnýchproměnné – definice a místa použitícyklyproces generování cílového kóduklasické optimalizacepropagace kopírovánízpracování konstantodstranění mrtvého kódunahrazování mocnin násobenímpřejmenování proměnnýchodstraňování společných podvýrazů (podstatné zejména pro výpočet adres prvků polí)přesun invariantního kódu z cyklůzjednodušení indukčních proměnných přiřazení registrů proměnnýmpřenositelnost a efektivitaAliasingdva různé formální argumenty vs. stejné aktuální argumentyTypy formálních a konkrétních argumentůpřevody z typu do jiného typu vede k přetypování a zpomalenípaměťekvivalencezarovnáníodstraňování smetípodprogramy, makra – inlining – může ovlivnit výsledek, jindy a jinak se zaokrouhlujepodmíněné výrazy – reorganizace složitých výrazů, nadbytečné testy (if vs. Case)podmíněné výrazu uprostřed cyklů – děláme jump uvnitř cyklu, musíme vyčistit pipeline uvnitř cyklu -> nevyužijeme potenciálu PC na plný výkonnezávislé cykly – nemění se v cyklu, může přijít před cykluszávislé cykly – jak závislé na iterační konstantěnezávislé na iteracizávislé mezi iteracemiredukce min max – existují speciální instrukce, kód musí být napsaný tak, aby to kompilátor byl schopen poznatskoky – snažíme se minimalizovatkonverze typů – dost drahá operace. Int -> float naopakruční optimalizace – společné podvýrazy, přesun kódu, zpracování polí (problém s ukazateli)optimalizace cyklůredukce režie zlepšení přístupu k paměti (cache)zvýšení paralelismudatové závislosti – backward dependeciesanti-dependenciesstandardně přejmenování proměnnýchoutput dependenciesv cyklu je vypočteno několik hodnot konkrétní proměnné, zapsat však stačí pouze tu „poslední“rozvoj cyklůtělo cyklu se několikrát zkopíruje (změna velikosti iteračního kroku)snížíme režii cyklu – počet průchoduzvýšíme paralelizace – SW pipelingpre- a postconditioning loops – adaptace na skutečný počet průchodůnevhodné cyklymalý počet iterací -> úplný rozvoj cyklůtlusté (=velké) cykly: samy obsahují dostatek příležitostí k paralelizacicykly s voláním procedur: souvislost s rozvojem procedur (inlining)cykly s podmíněnými výrazy: spíše starší typy procesůrekurzivní cykly: cykly s vnitřními závislostmi (a[i]=a[i]+a[i-1]*b)problém s rozvojem cyklůrozvoj špatným počtem iteracízahlcení registrů – i když je malý cyklus, budeme potřebovat tolik registrů, a tolik LOAD a STORE instrukcí.Výpadky vyrovnávací paměti instrukcí (příliš velký cyklus)HW problémy – především na multiprocesorech se sdílenou pamětí (cache koherence, přetížené sběrnice)speciální případ: rozvoj vnějších cyklůMessage Passing Interface, MPIUmožňuje paralelní programováníParalelní programovánídata paralelismusstejné instrukce na různých procesorech zpracovávají různá datav podstatě odpovídá SIMD modelu (Single instruction multiple data) – pralelizace cyklutask paralelismusMIMD model (multiple instruction multiple data)paralelně prováděné nezávislé bloky (funkce, procedury, program)SPMD není synchronizován na úrovni jednotlivých instrukcímekvivalentní MIMDMessage passing určeno pro SPMD/MIMDProstředí/systémyPVMjak vytvořit virtuální paralelní stroj – určený pro distribuované prostředíMPILindakoordinační jazyk, explicitní task paralelismus, komunikace přes sdílenou plochuMPIKomunikační rozhraní pro paralelní programyrozděleno do uzlů, který má pod sebou pár procesorů ty spolu posílajíobsahují tetovací skriptydefinováno APIstandardizovánořada nezávislých implementacímožnost optimalizace pro konkrétní HWurčité problémy se skutečnou interportabilitouvývojverze 1.0 – nebyla implementována, Vazby na C a Fortranverze 1.1 – byla implementována, oprava největších nedostatkůverze 1.2 – přechodná verze (přes MPI-2) rozšíření standardu MPI-1 aktuální stav MPI-2.0 – aktuální verzeexperimentální implementace plného standardurozšíření – paralelní I/O, jednosměrné operace (put, get), Manipulace s procesyvazba na C++ i Fortran 90cíle návrhu – výkon až na prvním místěpřenositelnostdefinice standardu (API)vazba na různé programovací jazykynezávislé implementacevýkon nezávislá optimalizace pro konkrétní HWknihovny, možnost výměny algoritmů – např nové verze kolektivních algoritmůfunkcionalitasnaha pokrýt všechny aspekty meziprocesorové komunikacespecifikace knihovny pro podporu předávání zprávurčena pro paralelní počítače, clustery i gridyzpřístupnění paralelního HW pro – uživatele, autory knihoven, vývojáře nástrojů a aplikacíinicializace MPIvytvoření prostředídefinuje, že program bude používat MPI knihovnynemanipuluje explicitně s procesyIdentifikace prostředíparalelní (distribuovaný) program potřebuje znátkolik procesů se účastní výpočtujaká je „moje“ pozicePráce se zprávami (klasický přístup)data posíláme jako proud bitů – úkolem přijímajícího a posílajícího data správně nastavit a rozpoznatkaždý proces má jedinečný identifikátor – musíme znát identifikátor příjemce/vysílajícího, broadcastmůžeme specifikovat příznak (tag) zprávy pro snazší rozpoznání (např. Pořadové číslo zprávy)synchronizace – explicitní spolupráce vysílajícího a přijímajícího, definuje pořadí zprávzpráva jako bity, potřebujeme adresu kam poslat zprávu, velikost zprávy, jak on ví, že ta zpráva je pro něj, jak vhodně popsat data, jak poznáme, že adresát je spokojený, posílat zprávu více procesůmsend(buffer, len, destination, tag)recv(buffer,maxlen, source, tag, actlen)actlen – skutečná délka přijaté zprávy actlen