Skripta

cí paměťřízeni u superskalárních procesorůŠířka toku datBandwith – maximální propustnost paměťového systémubity za sekundu (Gbps ...)teoretická rychlost Propustnost není stejná mezi všemi komponentamicesta procesor -> vyrovnávací paměť -> hlavní paměť -> externí paměť – snižuje se rychlostprocesor si myslí, že má konstantní rychlost nejbližšího prvku a kapacitu externích diskůLatenceDoba mezi časem požadavku a časem přístupu datZvlášť významná pro přesun malých objemů datpři zpracování desítek MB dat nám nejde o ms. Prokládaná paměťrozdělení na menší blokyurychlení – umožňuje okamžitý přístupnásledující adresy mapovány do různých blokůčtení jednoho bloku neovlivňuje čtení jiných blokůBěžné dvou až osminásobné prokládané paměťové subsystémysuperpočítače mají vícenásobné prokládaní (banky)Příklad: Convex C3 256 násobným prokládánímOpakovaný přístup k témuž banku: 300ns (téměř 20 násobné zrychlení)Vyšší latence - nevýhodouodstíněná pomocí pipelinepřibude nám logika , že musíme do správného banku.Předchůdce ANDES (instrukce – snažil se přeházet pořadí tak, aby minimalizoval zpoždění)Motorola (přehazuje pouze instrukce LOAD a STORE – přeházet jejich pořadí tak, aby minimalizoval impact čtení z hlavní paměti. Maximalizuje vícecestnou paměť)Procesor MIPS R80001993čtyřnásobná superskalární architektura, max 6 operací/cyklusZdvojená ALU, zdvojená FPU a dvě LOAD/STORE jednotkyFPU a ALU nejsou sychronizoványkdyž došlo k přerušení nebyla schopna vypsat ladící informacevelice rychle zpracovat pohyblivou řádovou čárkupřepnout i do možnosti přesného přerušení – více než stonásobně zpomaleníFPU s IEEE-754 standardní aritmetikou s nepřesným přerušením32 registrů (64bit) pro celočíselné a 32 registrů (64bit) pro float operandypodmíněné move instrukce (pro IF příkazy)cesta pro vypořádaní se se skokyPlně 64bitová architektura128-bit datová sběrnice40 bitová adresná sběrnice (max 1TB fyzické paměti) (dnes nestačí)TLB dvoucestný, s 384 položkamiuměli jsme mapovat dynamickystránka až 4MB velkáPracuje se s různým počtem bitů a záleží, kdy se zaokrouhluje – chyba zaokrouhlovánízáleží jak procesor pracuje interně a jak ukládá mezivýsledkyna různých procesorech jiné výsledkyna stejném procesoru jiným překladem jiný výsledek na stejném programuVyrovnávací paměťbrach prediction cacheřešíme problém, že máme v pipeline a vyrovnávací cache instrukce, ale kvůli skokům, budeme muset spekulativně odhadnout, které instrukce budou volány pokid nastane skok – spekulativní výpočet umí až ANDESstreaming cache – data na procesor umí posílat rychlostí FPU jako dva proudy, a umí přijímat třetí proud. Schopen do semi-vektorového režimu. Veliká pst, že data jsou v paměti a FPU nebude muset čekat na data.I-cache – instrukcepřímo adresovatelná1024 položek 128 bitůAdresovatelná i označena virtuální adresou – obchází TLBtag RAM – 512 položek (pro každý řádek)D-cache – cache (dvoucestná, pouze pro celočíselná data)přímo adresovanádva paralelní přístupyzvládá (2 load nebo load a store) – nezávisle a současněwrite-through protokoladresována virtuální, označena fyzickou adresouv RISCových procesorech lze dosáhnout velice dobrých výsledkůceločíselné dělení velice drahéProcesor MIPS R100001996pokus překonat problém velice rychlé FPU a pomalé celočíselné jednotkyANDES architektura – první z architekturysuperskalární, 4 instrukce současně2 ALU, 2 FPU (neekvivalentní)FPU s IEEE-754 standardní aritmetikou a přesným přerušenímANDES musí zjistit kde je program counter pro danou instrukciodkládá se přerušení až na tu graduation fáziANDES musí umět skrýt přerušení 32 (64 fyzických) registrů (64 bit) pro celočíselné operandy32 (64 fyzických) registrů pro float operandypřejmenování registrůplně 64 bitová architektura128 bit datová sběrnice, 40 bitová adresní sběrniceTLB plně asociativní, 64 položek (zdvojených) velikost stránky 4KB-16MBvyrovnávací paměti32KB I-cache (2-set assosiative)32KB D-cache (dvoucestná, 2-set assosiative)přepdpověď skoků (4 urovně)místo brach prediction cache1 MB L2 cachemísto streaming cacheneblokující instrukce load a storeVýpočet jednotek2 ALUspolečněsoučet rozdíl a log operacerozdílnéALU 1: skoky a operace posunuALU 2: násobení a dělení (iteračně)2 FPU (Další dvě jednotky (bez pipeline) pro dělení a odmocninu (iteračně))FPU 1: sčítačkaFPU 2: násobičkyumíme je propojit krátce pro multiply add instrukce (A*B + C)Celočíselná16 položekaž 4 instrukce současně zapsányFloat 16 položekaž 4 instrukce současně zapsánynelze současně zahájit DIVIDE a Square root instrukceMADD instrukce projde oběma FPUAdresní 16 položek (FIFO – sekvenční přístup)instrukce spustitelné v libovolném pořadízápis a vyjmutí musí být sekvenční (zajištěno FIFO bufferem)znovu spuštění instrukce při neúspěchu (cache miss, konflikt, závislost)UltraSPARC-1první zavedl grafickou unitu – GRU (Grafika)zaveden 1987Visual instraction setspeciální instrukce na zacházení s grafikoučtyřnásobná superskalární architektura2 ALU, FPU (2 instrukce), GRU (Grafika)32 FPU (64 bit) registrů64 bitová architektura, možnost volby little a big endianu128 bitová datová sběrnice, 41 bitů fyzická adresa, 44 virtální adresa64 položek v TLB, stránky s 8 K, 64 K 512 K nebo 4 MBVyrovnávací paměť16KB neblokující D-Cachebuď se dozvíme, že data nejsou a nechová se to, že zablokujeme pipeline a čekáme na data, procesor musí obsahovat logiku jak se zachovat16KB I-cache (s predikcí skoku)0,5-4MB L2 cache(propustnost 3,2GBps)Blokující Load/StoreFPUDělení a odmocnina samostatného (mimo FPU pipeline)12 (22) cyklů pro jednoduchou (dvoujnásobnou) přesnostneblokující pipelenované FPU instrukcepřesná přerušeníGRU16 a 32 bitové shlukované sčítání a boolovské instrukce 8 a 16 bitové násobení (4 násobné zrychlení renderingu)skládání a rozbor datpřímý přístup k (grafické) paměti obcházející D-cache (část hlavní paměti vyhrazena jako grafická, streaming přímo na procesor)přímá podpora „motion compensation“první pokus od SUNuParalelní počítačePostupně se zvyšoval výkon jednoprocesorových počítačů, poměrně brzy se zavedl vnitřní paralelismus (jednotlivé instrukce se mohou vykonávat paralelně).2 typy multiprocesingusmall-scale multiprocesing2-16 procesorů (běžné dostupné systémy)převážně SMP (sdílená paměť)Share memory procesingSymetric multiprocesinglarge-scale multiprocesinguzly s několika procesory> 100 (i tisíce) procesorůZpravidla distribuovaná paměťArchitekturaSIMD – single instructin multiple data, silně synchronizované jednotky, přibližuje vektorové počítače – mají stejné výhody a nevýhody, jednodušší, princip metod z vektorových počítačů, technologicky snadněji implementovatelné (proto velký rozvoj v 80 letech), dnes již jen na úrovni jednoho procesoru. Procesory jednodušší než u MIMDMIMD – multiple instruction multiple data – každý procesor může zpracovávat data nezávisle na všech ostatních procesorech, architektura dnešních superpočítačů, nejtěžší na programování (jak zaměstnat každý procesor), musíme se potkat ve výpočtu (ověřit výpočet, procesory nejsou synchronizovány – jak docílit společného „zastavení“), vyšší flexibilita, teoreticky vyšší flexibilitaSMPD – single program multiple data – jeden program využívá více procesorů (například paralelizace cyklů, z pohledu procesu je to jedno vlákno), běžně využíván v MIMD architektuřeMPMD – problém rozdělíme do pod úloh a ty pak necháme řešit, (například prohledávání stavového prostoru), jedna paralelní úloha poskládána z jednodušších úloh. Na MIMD zcela vhodné, na SIMD teoreticky možné.Komunikační modelySdílená paměťJestliže procesor A vyprodukoval data a B je potřebuje, tak A zapíše do paměti a B je přečte, ani jeden procesor nedělá nic zvláštního, ale musí se synchronizovat (aby B nedostal smetí, četl dřív než A stihlo zapsat data). Složité oddělení výpočtu a čekání na data. Chování je takové, že nepotřebujeme vědět, kdo zapsal data do paměti, důležité je, že data v paměti jsoubloky paměti oddělené od procesorůuniformní přístup k pamětiUMA – Uniform memory accessNejsnazší propojení – sběrniceLevná komunikaceSložité prokládání výpočtu a komunikace (aktivní čekání)procesor se zablokuje a čeká na data, napsat programy tak, aby nedošlo k blokaci, je velice složitoté. Předávání zpráv (Message passing)distribuovaná paměťprocesory komunikují pomocí zpráv - Procesor potřebuje data a potřebuje je od jednoho jediného procesoru z množiny procesorů, explicitní komunikace – předáním zprávyvysoká cena komunikace (výměna dat) – posílá se přes síť, mnoho a mnoho instrukcí, pomalejšíkaždý procesor je viditelnýmožnost prokládání výpočtu a komunikacemůžeme použít v modelu sdílené paměti – ale efektivita je menšíHybridní systémyNonuniform memory access architecture (NUMA)Přístup k různým fyzickým adresám trvá různou dobu (máme minimálně 2 úrovně – moji – rychlejší, malá - a cizí – pomalý přístup, velká)sdílená paměťpřímá HW podpora, každý procesor vidí celou paměť umožňuje vyšší škálovatelnostpotenciálně nižší propustnostKoherence vyrovnávacích pamětíccNUMA cachce koherentní NUMAmají vyrovnávací paměť, chová se navenek stejně jako symetrický multiprocesorový systém se sdílenou pamětí, programátor se nestará o to, že procesor přečte stará dataneříká nic o tom jestli používáte cache u procesoruCache-only memory access architecture (COMA)speciální systémykoncepčně zajímavéNUMA se speciální architekturou paměti (řeší problém s rychlou a pomalou pamětí)dívá se na paměť jako na veliký pool vyrovnávacích pamětí, funguje stejně jako normální vyrovnávací paměti. HW se stará o to, aby se stránka neztratila. (systém si pamatuje kolik je kopií stejných informací – nemůže se přehrát poslední kopie dat), složitost hlídání kopií ve všech pamětech není triviálníDistributed shared-memory (DSM)systém, ve kterém je základem distribuovaná paměť, programátorovi předložíme iluzi, že má kapacitu celé distribuované paměti – virtuální paměť – realizuje se pomocí clusterů, který má speciální protokol, který umožňuje sáhnout přímo do paměti (Direct Memory Access – uložíme nebo přečteme – HW řešení, transparentní) , možno i SW podpora (knihovny, netransparentní, programátor musí explicitně přizpůsobit). Výhodou je levnost než plně NUMA architekturaexistují knihovnyDistribuovaný systém – clusterlokální paměť každého uzluVzdálená paměť ostatních uzlůFikce jedné rozsáhlé pamětiKoherence vyrovnávacích pamětípříčiny výpadku vyrovnávací pamětiCompulsory miss – 1. přístup k datům – načíst z jiné paměticonflict miss – různé adresy mapovány do stejného místa vyrovnávací paměticapacity miss – nedostatečná kapacita – něco se musí odstranitcoherence miss – různá data v různých vyrovnávacích pamětech – přibyl díky distributivitě – musí se sdělit ostatním procesorům o změněřešení pomocí broadcastu (procesory, které nemají data dostanou broadcast - zbytečné)vyrovnávací paměti musí vědět o změněadresářové metody (minimalizujeme záplavu)Snoopy cachebroadcastový přístup – propojovaci sitě s „přirozeným“ broadcastem – sběrnicekaždý procesor sleduje všechny přístupy k paměti, zjišťuje se jestli nějaký procesor nezměnil jejich data ve vyrovnávací paměti. 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ětovného přístupu je přehrána ze vzdálené paměti, Nevýhody – nové čtení z hlavní pamětiUpdate – řá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ší, Aby fungoval dobře, potřebuje protokol Write-Through. Rozšiřitelnostnení jednotná definicePoužívané základní formulace – rozšířitelný je takový systém, pro nějž platívýkon roste lineárně s cenouje zachován konstantní poměr cena/výkonAlternativní parametr – míra rozšiřitelnosti - co se stane, když rozšířímezměna výkonu přidáním procesoruzměna ceny přidáním procesorusmysluplný rozsah počtu procesorů zrychleníteoretický pojem, realita závisí na aplikacirůzné hodnoty pro různé aplikacevliv paralelizovatelnosti problému (Amdalův zákon)Rožšiřitlené propojovací sítěPožadavky na ideální síťnízká cena rostoucí lineárně s počtem procesorůminimální latence nezávislá na počtu procesorůpropustnost rostoucí lineárně s počtem procesorů Vlastnosti sítítopologie – jak je propojenapřepínání dat – jak se data pohybují mezi uzlysměrování – cesta Rozšiřujeme následující základní parametryvelikost sítě – počet uzlůstupeň uzlu dpoloměr sítě Dnejdelší nejkratší cestabisection width Bpočet hran, které musíme odstranit, abychom dostali dvě stejné podsítěbisection bandwidthpropustnost při rozpůlenícelková kapacita výše odstraněných linektest jestli komunikace mezi sítí je dobráideální vlastnostbisection bandwidth vztažená na procesor je v daném systému konstantníredundance sítě Aminimální počet hran, které je třeba odtranit, aby se síť rozpadla na dvěCena Cpočet komunikačních linek v sítiTopologie přepínacích sítíklasifikace na základě rozměrujednorozměrná – řetěz, má všechny špatné vlastnosti, veliký poloměr, bisection width, masivní síťdvourozměrná – například kruh, má lepší vlastnosti, hvězda – centrální vypadne, vše jde přes střed, strom - binární má příjemné vlastnostni (vnitřní uzly maji stupěň 3), malý poloměr sítě, stále špatná redundance a bisekce, tlustý strom přidává redundatní cesty ve vyšších úrovníchdvourozměrná mřížkadobré vlatsnosti – poloměr, bisection, redundancešpatná – vyšší cena a proměný stupeň uzluTorusuzavřená dvourozměrná mřížkavyšší cena – přidá mnoho hrantřírozměrná – postavit ji je poměrně složitélepší poloměrbisection – ještě lepšíredundance 3akceptovatelná cenakonstrukčně složitáhyperkostkan-rozměrná krychlevelmi zajímavá topologievýhodou je malý poloměr – dobře se posílají datamřížky jsou speciálním případem hyperkrychlesnadné nalezení cestybinární číslování uzlůPlné propojen