################# Procesory: ################################### 1. CISC - Complex Instruction Set PDP11, VAX -- very old vecicky :) -- maximum veci robi hardver -- vsetky zlozitejsie instrukcie sa emuluju pomocou jednodychych. -- postupnost mikroinstruckii = mikroprogram -- relativna vyhoda -> programy sa daju potom lepsie prisposobit na konkretnu architekturu, pretoze sa pouziju len najrychlejsie a nejlepsie instruckie (ach jo :) Idealy su krasna vec :))) -- pridavaju sa instrukcie na vsetko --> je nutna zlozita analyza instrukcie -- musi sa prechadzat niekolko zaznamov so zoznamom instrukcii. -- spatna kompaktibilita vzhladom na komplexnost instrukcii = takmer nemozna 1.2. Pipelining -- nie je mozne neustale zvysovat rychlost hodin -- instrukcie su naukladane v kolone za sebou a procesor ich priebezne vykonava hlavnu, zatail co nasledujuce sa prepravuju na vykonanie. -- toto umoznuje paralelizaciu -- v pripade, ze nie je dobre implementovany skokovy algoritmus, je nutne pri kazdom skoku vyliat celu pipeline a zacat tahat nove udaje. -- CISC proc. mali navrh hlavne v rychlosti spracovavania instrukcii (vsetko sa lialo do pipeliny, kde bezalo spracovanie paralelne) 1.2.1 5 urovnovy pipelining 1. Instruction Fetch -- zachytenie instrukcie -- instrukcia sa nacita z pamate 2. Instructio Decode -- zistenie o aku instrukciu sa jedna a ake potrebuje param. a podobne 3. Operand Fetch -- nacitanie vsetkych potrebnych ciselok z pamate, prip z registrov. 4. Execute -- instrukcia pripravena a spusti sa jej vykonavanie 5. Writeback -- posledne zuctovanie vsetky nutne informacie su zapisane spat do pamate Jednotlive instrukcie su spracovavane paralelne a vzdy sa posunu o jednu fazu v pipeline dalej 1.2.2. Neviditelny pipelining -- kompilator usporiadava pristupy do pamate tak, aby boli data v najlepsom poradi na spracovanie a nebolo nutne ich zakazdym citat 1.2.3. Viditelne pipeline -- je nadefinovane, ako dlho trvaju instrukcie do ich ukoncenia, co umoznuje kompilatoru usporiadat ich do spravneho poradia 2. RISC - Reduced Instruction Set Novinky, ktore RISCova architektura priniesla: 1. cache 2. pokles ceny, vzrast velkosti pamate 3. zlepsenie pipeliningu 4. prekladace kvlitnejsie optimalizujuce kod Dosledky: 1. rychlost pristupu do pamate prestava byt problemom 2. nie je podstatna velkost programu (vzhladom na kapacitu pamate) 3. STALL - zadrzanie instrukcie pri cakani na vysledok (to bol u CISC architektury problem) 4. instrukcie jednoduche => jednoduchy assembler (assembler uz nie je tak citatelny) 2.1. Zakladne rysy -- instrukcie maju rovnaku dlzku v pamati -- vyberaju sa len skutocne najpouzivanejsie instrukcie (v CISCOch sa 90% instrukcii pouzivalo len v 10% programov, co bolo strasne plytvanie;-) -- jednoducha adresacia -- kazdy proces moze mat pocit, ze vidi, cely adresny priestor (az neskorsie modely) -- Load/Store -- dostatok registrov (znamena urychlenie, niektorych operacii) -- delayed branches -- odlozene skoky 2.2. Superskalar -- viacnosobne vyuzitie jednotky aritmetickej a FPU -- spracovavanie viacerych pipeline sucastne -- programovanie sekvencne - paralelizacia zaistena pomocou hardveru 2.3. Superpipeline -- super rura (no to by som na vodovod, radsej nepouzival :) -- zjednodusenie obvodov -- pipeline sa rozlozi na niekolko mensich casti -- v konecnom dosledku rychlejsie vypocty = deep pipelines 2.4. Very Long Instruction Word -- pod kontrolou prekladaca -- instruckia ma zlozity zapis, avsak pri spracovani sa rozpadne na mensie a jednoduche operacie sa spracuvaju v samostatnych pipeline 2. 5. Obchadzanie registrov Pri niektorych operaciach jedna instrukcia uklada data do pamate a dalsia ich cita (jedna sa o tie iste data) - vyhodnejsie je udrzat data v registroch Fetch -> aby nedochodzalo k strate dat z pipeliny Execute supne sa na zaciatok instrukcia NOP Writeback 2.6. Premenovanie registrov -- aby nedochadzalo k zahadzovaniu dat, jednoducho sa register premenuje na iny (hidden) a v pripade, ze je data potreba, vrati register spat -- riesene na urovni hardveru -- ukryte registry (o ktorych vie procesor) mozu byt vyhodnejsie -- kompilatoru umoznuje optimalizovat na maximum -- ked procesor zisti prekryv dat, jednoducho len premenuje registre a ani sa nechumeli :) 2.7. Skoky 2.7.1. Nulovannie informacie -- pri podmienenom skoku sa zacnu data tahat do dalsej pipeline, kde sa nad nimi spusti vypocet -- znizuje sa tak oneskorenie vykonavania instrukcii 2.7.2. Predpoved skoku -- instrukcie sa natahuju podla pravdepodobnosti s ktorou sa skace -- toto moze zadavat kompilator, pripadne procesor si moze dynamicky udrziavat statistiku 2.7.3. Predpokladane ciele -- procesor si udrzuje informaciu o tom, kam moze skakat a podla tychto cielov potom vyvolava instrukcie z pamate 3. specializovane procesory - napr. vektorove pocitace (umoznuju velmy rychlo pocitat vektory, ale pri klasickych skalarnych opraciach je ich vykon slaby -- priklad - superpocitac CRAY, co je v hale) 4. Masivne paralelne pocitace - synchronne prevadzaju jednu instrukciu -- rovnaky typ vypoctov nad jednymi datami 5. Architecture with Non-sequential Dynamic Execution Scheduling ANDES (proc MIPS R10000) -- obsahuje tri fronty pre spracovavanie instrukcii: 1. celociselne instrukcie 2. load/store operacie 3. praca s pohyblivou ciarkou -- kazda fronta ma vlastnu pipeline -- instruckie su vyberane z pipe, podla toho, ako su vhodne na spracovanie, teda aj v inom poradi, ako boli zapisane za sebou -- dokoncovanie instrukcii je vsak zhodne s poradim instrukcii v programe -- pridava sa dalsia faza: Graduate - dospievanie instrukcie -- je prevadzanie sa ukonci az pri Commite (potvrdeni) -- Out of Order Execution -- to neznamena, ze instrukcie su mimo prevadzku :) Ale ze su vykonavane v roznom poradi Fazy spracovania: 1. Fetch -- nacitanie instrukcie 2. Decode -- rozkodovanie 3. Issue (neviem co to je?) 4. Execute -- vykonna cast 5. Complete -- dopocitanie 6. Graduate -- cakanie na potvrdenie (commit) OoOE -- ak Load nacitava z pamate a nedostane okamzite odpoved, inicializuje sa prenos instrukcie do fronty s priznakom a pokracuje sa vo vykonavani dalsich instrukcii 5.1. Spekulativny skok -- mimo ANDES riesene ako synchronizacna bariera (??) Zapisuje si vysledky skokov, ktore sa mu podarili -- toto umoznuje lokalnu predikciu dalsich skokov Uchovava si informaciu o tom, kadial sa k vypoctu dostal -- globalna predikcia Kombinacna logicka jednotka -- zapisuje, ktora z predpovedi ma prednost - ci globalna, ci lokalna IBM riesilo pomocou 2 bitov -> softverova predikcia 1. bit = 1 -> citaj predikciu z instrukcie 2. bit = 1 -> skac 0 -> neskac -- ak dojde k skoku, tak vyrazi vsetko po complete, s instou pravdepodobnostou uz existuju instrukcie v pipeline, ktorymi sa da pokracovat (najma, ak ma pipeline hlbku 200 instrukcii ako u Macov) -- problem s prerusenim -> ak v R10000 doslo k preruseniu, nebolo mozne zistit, kde sa to presne stalo -> nevyhoda zaciatocnej implementacie ANDES 5.2. Neblokujuci Load/Store -- nie je nutne zamykat pamat pri kazdom pristupe a tak su instrukcie odpalene na ulozenie, nacitanie, pricom su opat zaradene do fronty, kde cakaju na svoje dokoncenie a medzicasom sa vykonavaju dalsie instrukcie 5.3. Premenovanie registrov -- detto ako u vyssich -- niektore udaje nie je nutne okamzite odstrelit do pamate a potom ich znova nacitavat, pretoze refresh pamate je pomerne dlhy a preto je lepsie udrzat ich v registroch. Ak procesor register potrebuje, jednoducho ho len premenuje ######################### PAMATE #################################### 1. Page mode -- data ukladane v matici sa rozdelia na riadky a stlpce -- skupina data, ktore lezia za sebou sa dau rychlejsie zapisat do pamate (prip. nacitat) -- preto sa do pamate posle cely blok dat 2. Memory Acces Time -- pristupova doba do pamate -- nacitaj riadok + nacitaj stlpec + nacitaj data 3. Memory Cycle Time -- cyklus pamati -- urcuje, ako casto je mozne ziadat udaje z rovnakeho meista v pamati -- doba pri zapise a nasledovnom nacitani je dlhsia ako len pri klasickom nacitani 4. Virtualna pamat -- zavadza sa Translation Look Aside Buffer, do ktoreho sa ukladaju informacie o pouzitych strankach a ich fyzickych adresach -- jedna sa o specialnu vyrovnavaciu pamat :) 4.1. TLB Misses -- mnozstvo neuspesnych citani z bufferu -- miss -- pokial nie je stranka nacitana v bufferi a je nutne sahnut pre nu do pamate 4.2. TLB hit -- zasah -- bingo -- mame ju -- je dobre, ked prevazuju hit nad miss :))) pretoze inak, cely TLB straca svoj vyznam :) -- definuje sa ako hit ratio -- TLB sa prilis nepouzivaju v superpocitacoch (ciste pragmaticke) 4.3 Parametre -- velkost 4 KB -> 16 MB -- riadky maju pevnu dlzku 16-128 bitov -- zavisle na architekture procesoru a na adresnej oblasti, ktoru dokaze spracovat :))) 4.4. Tipy pamati 4.4.1. Plna adresovatelna pamat -- direct mapped -- vsetky udaje sa odpaluju priamo do pamate bez ziadnych pomocnych mechanizmov 4.4.2. Mnozinovo (ciastocne) asociativna pamat -- set-associative -- asi najvyhodnejsi typ pamate -- kombinacia asociativnej a plne adresovatelnej -- adresovy pristor sa rozpadne do akychsi blokov -> podobne ako stranky v knizke, kazda stranka sa da nast priamo a riadok je treba dohladat -- identifikacnych retazcov je pomerne malo a mechanizmus sa da velmi jednoducho implementovat 4.4.3. Plne asociativna pamat -- kazdy pristup do pamate sposobi vymenu asociativnej tabulky -- nutne osetrit na strane kompilatora -- musia sa prehliadat paralelne vsetky riadky pamate pri dotazu -- logika asociativnej pamate je prilis draha na implementaciu 4.4.4. Harvard Memory Architecture -- oddelenie oblasti pre data a instrukcie -- toto sa deje hlavne na urovni cache 4.4.5. Programovo ovladana cache -- DEC Alfa procesory -- superskalarne 4.5. Urychlenie cez TLB -- pri viacprocesovom operacnom systeme sa mozu TLB pre jednotlive procesy ukladat a pri vrateni procesu spat do popredia sa vrati jeho povodny TLB 4.6. Bandwith -- maximalna priepustnost pamatoveho systemu -- medzi jednotlivymi prvkami - procesor - pamat - hlavna pamat 4.7. Latency -- doba medzi polozenim poziadavky a dostanim odpovede na ziskanie dat :)) -- napriklad taka posta ma latenciu aj niekolko rokov :) 4.8. Interleaved memory -- prekladana pamat -- rozdelenie pamate na bloky -- znizuje sa latencia pri pristupe k rovnakemu bloku pamate -- vyssia latencia je odtienena pipeliningom -- vsetko sa napcha da pipe -- pri pouziti ANDES s graduate je to vyhodnejsie -- preskladanie instruckii bolo pri starich architekturach ponechane na kompilatore 4.9. Write thru -- zapise do vyrovnavacej pamate a zaroven inicializuje prenos do hlavnej pamate -- synchronny zapis ####################### PARAMETRE PROCESOROV ######################## (toto nebudem cele opisovat -- najdete v skriptach) 1. MIPS R8000 -- 64bit -- 4x nasobna superskalarna arch. -- TLB 384 poloziek 2. MIPS R10000 -- ANDES -- 3 fronty 3. Ultra SparcI -- virtual instruction set -- GRU -- jednotka pocitajuca s booleovskymi instrukciami 4. Alpha -- 5 nezavislych jednotiek (dalsie su v skriptach) ##################### PARALELNE POCITACE ############################### 1. Paralelizmus -- small scale -> 2-16 procesorov -- large scale -> >100 procesorov 2. SIMD -- single procesor - multiple data -- synchronne spracovavanie instrukcii -- procesy su striktne sinchronizovane -- kazdy spracuva rovnaku instrukciu -- kazdy ma svoje vlastne data -- kvazi vektorovy vypocet -- implementovane explicitne operacie na rozoslanie a zber dat 3. MIMD -- asynchronna cinnost -- multiple instruction multiple data -- vyssia flexibilita -- nutna synchronizacia, zlozitejsie programove modely 4. System architektury zasielania sprav = distribuovana pamat -- procesor vidi len svoju pamat -- ak potrebuje data ineho procesoru, musi zaslat ziadost -- kazdy procesor musi byt viditelny -- nevyplati sa predavanie malych sprav -- po vyslani poziadavky musi byt stale nieco na pocitanie (ved sa nemozeme nudit :))) -- niekedy je vyhodnejsie vypocitat si vlastne data, ako cakat na data z ineho procu 5. system so zdielanou pamatou -- procy pocuvaju na zbernici -- pamat je oddelena od procesorov -- lacna komunikacia -- zlozite prekladanie vypoctov, v pripade, ze viacero procov potrebuje komunikovat sucastne 6. Hybridne systemy 6.1. Distributed shared memory (DSM) -- iluzia spolocneho pamatoveho priestoru je zabezpecena hardverom a softverom -- prebieha zasielanie sprav 6.2. Nonuniform Memory Accessarchitecture (NUMA) -- bez cache sa vytvara jednoducho -- pamat je adresovana z dalsich procesorov 6.3. Cache-only Memory Accessarchitecture (COMA) -- pamat je jedna velka cache a data migruju po pamate 6.4. NUMA-cc -- v pripade vyrovnavacich pamati -- zlozitejsi navrh -- musi udrzat koherenciu udajov -> Vacsie systemy pouzivaju neuniformny pristup do pamate 6.5. Problemy spojene s koherenciou pamate (spojitostou) -- Compulsory miss. -- 1 pristup k datam -- povinny pristup ?? -- pravdepodobne sucastny pristup k jednej oblasti -- Capacity miss -- nedostatocna kapacita pamate je nutne hladat inu lokalitu -- Conflict miss -- rozne adresy su namapovane na rovnake miesto -- Coherence miss -- rozna data v roznych vyrovnavacich pamatiach 6.6. Snoopy cache -- vsetcia pocuvaju co sa deje na zbernici a udaje si beru len ti, ktorych sa to tika -- procesory, ktore dane udaje udrziavaju v pamati -- da sa pouzit tam, kde je broadcast -- vzhladom na broadcast toto riesenie nie je rozsiritelne ######################## ROZSIRITELNOST ############################ 1. Cena rastie linearne s vykonom -- konstantny pomer cena/vykon -- nie je prilis jednoznacne 2. Vhodne miery pre rozsiritelnost 1. zmena vykonu pri pridani dalsieho procesoru 2. zmena ceny pri pridani dalsieho procesoru 3. rozsah procesorov 3. Zrychlenie S(N) = Vykon(1) / Vykon(N) Idealne zrychlenie Vypocet(N) = Vypocet(1)/N -- pre paralelne ulohy neexistuje jednoznacny ####################### PREPOJOVACIE SIETE ######################## 1. Idealna siet -- vykon rastie linearne s cenou -- minimalna latencia nezavisla na rozsireni -- priepustnost siete rastuca linearne s rozsirenim 2. Bisection bandwith -- kazdy chce mluvit s kazdym -- stejne naroky na komunikaci -- rozdelenie systemu na dve casti -> polovica vsetkej komunikacie je smerovana do druhej casti siete -- poziadavka: bisection bandwith je konstantna pre akekolvek mnzostvo procesorov 3. Prepojovanie sieti 3.1. Zbernica -- pri zbernici klesa prudko priepustnost 3.2. Nepriame siete -- vypocty sa nachadzaju mimo siet -- napr Inet -- vhodne pre prvnocenne rozlozenie zataze 3.3. Priame siete -- vypoctove prvky su priamo v sieti -- vhodne pre lokalitu -- teda zvyhodnovanie najblizsich proc. -- podpora zhlukovania -- vypocty mozu bezat v urcitych uzloch 3.4. prepinane obvody -- posielanie datagramov - packety -- na zaciatku je nutne vytvorit cestu -- vysoka inicialna latencia -- nepouziva sa vo vnutri - iba v pripade pevne otvorenych obvodov 3.5. Store & Forward -- uloz a odosli -- switch -- znizuju sa vyskyt moznej chyby 3.6. Womhole -- odosli okamzite a na nic necakaj -- umoznuje znizit latenciu 3.7. Fixovane -- cesty su pevne nadefinovane -- jednoduche routovacie algoritmy -- jasne, kedy doslo k strate paketu -- su prijimane v rovnakom poradi ako odoslane 3.8. Fault tolerance -- pri zisteni chyby sa zasielaju poziadavky na opatovne zaslanie informacii 4. Priklady prepojovacich sieti 4.1. Full Crosbar -- plny prepinac -- jednosmerny -- podstatne su tie prepinace, kde sa meni smer -- problem pri pretazeni jedneho prepinaca 4.2. Multistage Interconnection Network -- viacurovnova prepojovacia siet 4.3. Omega -- viacurovnova prepinana siet -- pri zvysovani poctu spojeni sa prida nova vrstva -- nakoniec existuje cesta kazdy s kazdym -- nie je optimalizovana na blizkost -- velkost prepinacov je konstantna 4.4. Hypercube -- priama siet -- komunikacne prepojenia -- N kanalov -- pri dobrej reprezentacii sa susende uzly lisia v binarnom strome o jenicku, co umoznuje vytvorit velmi efektivne routovacie algoritmy 1. prepinanie celych paketov 2. sotre&forward -- wormhole 4.5. k-arna kocka -- :))) 4.6. Fat Tree -- :))))) 4.7. Bus and Rings -- ide pesek okolo :) -- spomente si na staudkove prednasky ####################### KOHERENCE ######################################## 1. Cache coherent -- vyuzitie tam, kde v prepojovacej sieti nie je ziadna lokalita -- nezatazuje hlavni pamet -- pri uplatneni lokality -- rastie slozitost -- netrivialni komunikace 2. Riadiaci adresar -- vyrovnavacia pamat s hierarchiou adresarov -- klasicky priklad -- niekam ukladame retazec -- jedine, co nas zaujima su tie, kde su jednicky a predpokladame, ze vsade inde su nuly -- ak dojde k zneplatneniu, prislusny riadok sa zmaze -- nemusi byt linearny zoznam 3. NUMA Proc Proc | | Mem Mem \ / NET -- lokalna pamat pre kazdy procesor -- rozsirenie je limitovane 4. ccNUMA -- prva s napadom prisla SGI -- implementacia plnych adresarovych sytemov s plnou garanciou cache coherent -- system sa diva na pamat, ako na jednu spojitu oblast -- system zdiela pamat -- planovac sa snazi spustit spiace procesy na tom istom stroji 5. COMA -- logicke usporiadanie nemusi zodpovedat fyzickemu -- riadky pamate nemaju nadefinovanu polohu -- pri presune dat na iny stroj/proc sa zachovava logicka adresa (narozdiel od ccNUMA, kde sa musi menit aj logicka adresa) -- rovnaka logicka stranka sa moze vyskytovat viackrat -- COMA je implicitne cache coherent -- musi existovat nekdo, kdo hlida, ze existuje alespon jedna realna stranka s udajmi 6. Koherencia 6.1. Directory based -- pamat je spravovana v tvre adresarov -- bloky a riadky -- polozka adresara si udrzuje informacie: 1. Stav: v pamati, zdielany, spinavy 2. Ukazatel do vyrovnavacej pamate -- jedna sa o bitove pole, kazdy bit zodpoveda jednej vyrovnavacej pamati, oznacuje, kde vsade je udaj pritomny -- pomerne vysoka latencia -- vysoka rezia -- zlozite vyhladavanie v pamati 6.2. Plny adresar -- Full bit Vector -- kazdy blok pamate nesie informaciu o tom, ktore vyrovnavacie pamate ho obsahuju -- bud zdielany -- alebo v jednej kopii (pri zapise) 6.3. Limited pointer scheme -- kazdy blok ma urceny maximalny pocet pointerov ukazujuci na procesory, ktore ho drzia vo vyrovnavacej pamati -- pri prekroceni hranice zdielania dochadza k preteceniu 6.3.1. Zneplatnovanie v pripade pretecenia: 1. Broadcast -- zneplatnenie pamatovej stranky je zaslane vsetkym procesom 2. Bez broadcastu -- zneplatnenie je zaslane pri preteceni a ukazatele sa tym vyprazdnia 3. Coarse-vector -- udava se velikost regionu, kteremu odpovida jeden bit -- jedna sa o odkaz na skupinu procesoru a pri pretecni sa im zasle lokalny broadcast 6.4. Extended Pointer Scheme -- LimitLESS -- programove prerusenie pri preteceni (nutne su specialne procesory) -- Dynamic Pointer -- pointery sa vytvaraju dynamicky, to ale znamena podstatne vacsiu reziu -- Cache based linked list -- zoznam je drzany vo vyrovnavacich pamatiach -- pristup je lepsie skalovatelny -- nie je treba pridavat adresarovu pamat, pretoze novy procesor ju so sebou prinesie -- nevyhody: 1. Zlozity protokol 2. Zvysena komunikacia 3. Dlhsi zapis 6.5. Riedke adresare -- drzia sa informacie len pre vyrovnavacie pamate -- celkova kapacita je nizsia -- charakteristiky: 1. memory size factor -- pocet blokov v pamati = pocet poloziek adr. 2. directory size factor -- pomer poctu poloziek adresara k celkovemu poctublokov vsetkych vyrovnavacich pamati -- ak polozka nie je vo vyrovnavacej pamati => je prazdna -- kazdy riadok adresara zodpoveda jednemu riadku vyrovnavacej pamate (zabranuje falosnemu zdielaniu) -- adresare nesu odkazy na rozne procesy z celeho pocitaca -- vykon je limitovany koliziami v pamati -- rozne pamatove bloky mapuju rovnake riadky v pamati -- pri kolizii dojde k zneplatneniu stavu -- zvysenie vykonu sa dosahuje zdvihnutim directory size factor -- adresarova pamatat musi byt pristupna vsetkym procesorom priamo 6.6. Hierarticke adresare -- adresarova pamat sa rozptyli podla topologie siete -- garantuje vyssiu priepustnost na urovni hierarchie -- procesor moze citat udaje z pamate suseda -- vyuzitelne do 2-3 urovni -- ak sused nevlastni data procesor sahne do pamate :) -- pri vyssom stupni hierartizacie (to je slovo:))) sa zvysuje rozptyl teda doba, ktoru trva ziskanie udajov z pamate je rozna -- je tazsie predpovedatelna doba behu instrukcie 6.7. Oneskorenie -- redukcia znizemin -> nutne zvysit rychlost pristupu do pamate -- redukcia ukrytim -> niektore udaje su dopocitavane namiesto toho, aby sa znova natahovali z pamati -- v dobe cakania na data sa prevadzaju dalsie uzitocne operacie -- inicializuje sa viac komunikacnych operacii -- vykonavaju sa instrukcie ineho procesu -- urychlenie NUMA -> kazda logicka adresa zodpoveda fyzickej -- urychlenie COMA -> hlavna pamat je len attraction memory -- riadky sa mozu po pamati volne presuvat -- mozu existovat zdielane kopie riadkov 6.7.1. Model slabej konzistencie -- procesory vidia instrukcie -- citanie a zapis prevadzaju v inom poradi 6.7.1.1. Sekvencna konzistencia -- prikazy su sekvencne konzistentne -- striktne poziadavky na ukoncenie instrukcie vzhladom na ostatne procesy -- write sposobi invalidaciu vsetkych zdielanych casti -- dochadza k uzamknutiu pamate 6.7.1.2. Slaba konzistencia -- synchronizacia je explicitna -- synch. op + lock + unlock -- nepozaduje sa striktne usporiadanie prikazov, okrem synchronizacnych 6.7.1.3. Release consistency -- acquire & release -- cakaju na odomknutie -- vzhladom na kriticku sekciu sa definuje poradie -- cenu plati len procesor, ktory vydal prikaz na synch. -- nedochadza k zdrzaniu dalsich procesorov -- vsetky nasledujuce operacie musia cakat na dokoncenie 6.7.1.4. Fence -- vynutene dokoncovanie rozpracovanych operacii -- nezamyka oblast -- vyziada si vsak striktnu synchronizaciu 6.7.2. Prefetch -- s predstihom sa spusti operacia citania 6.7.2.1. Binding Prefetch -- spojene s modelom slabej konzistencie -- data su presunute priamo k procesorom -- riziko porusenia konzistencie 6.7.2.2. Nobinding prefetch (neviazuci prefetch) HW -- cache ma dlshiu pamat nez je slovo -- do cache sa nacita viac ako bolo ziadane SW -- prekladac vsuva do kodu potrebne informacie -- specialna instrukcia : prefetch exclusive -> read nasledovany write -- pamatova oblast je uzamknuta okamzite uz pri nacitani -- latencia je skryta vzhladom na skupinu procesov 6.7.3. Procesory s viacnosobnymi kontextami -- bezi niekolko procesov -- kazdy proces ma vlastne registre -- procesor prepina medzi kontextami 6.7.4. Komunikacia iniciovana producentom -- producent dava informacie o tom, kam zapise informacie 7. Synchronizacia 1. vzajomne vylucenie -- zmena prevadzania sa tyka len jedneho procesu 2. dynamicke rozlozenie zataze -- predchadza stretom -- rozklad uloh na urcene miesta 3. informacie o udalostiach -- procesory cakaju na vysledok -- tento vsledok je nutne oznamit 4. globalna serializacia -- vsetky procesy musia prist na jedno miesto Implementacie synchronizacnych prvkov: 1. QOLB -- fronta cakajucich procesov -- nedochadza k starnutiu 2. Fetch & OP -- ziskaj hodnotu a rovnu ju zvys -- ziskavanie poradia zo schedulera -- atomicka instrukcia Compare & Swap -- ziskaj hodnutu a vymen 3. 2 fazy: 1. caka na jednotlive procesy, ktore sa maju zarazit na bariere -- vsetcia citaju informacie z jedneho miesta 2. zobudenie vsetkych procesov ##################### OPTIMALIZACIA KODU ################################################## 1. Propagacia kopirovanim -- zmensenie poctu registrov -- kod sa nakopiruje niekolkokrat za seba -- umoznuje paralelizmus -- rozpad na sekvencny pristup 2. Spracovanie konstant -- operacie nad konstantami sa deju v dobe kompilacie -- pri prevode sucinu s konstantami moze dosjt k rozdielom 3. Odstranovanie mrtveho kodu -- casti kodu, ktore sa nemozu vykonat su odstranene 4. Strench reduction -- operacie vyssej triedy sa prevadzaju na operacie nizsej triedy -- K**2 => K*K 5. Premenovanie premennych -- pouzitie pri priradeniach -- paralelizacia -- odstranuje umele zavislosti (mrk at slides :o) 6. Odstranovanie spolocnych vyrazov -- hodnota vyrazov, ktore sa uz raz vypocitali sa znova pouzije bez toho, aby sa musela pocitat znova 7. Presun z cyklu -- presunie inicializacne casti kodu von z cyklu 8. Aliasing -- volanie funkcii s rovnakymi argumentami -- problem pri poliach oznacovanych rovnakym menom 9. Zarovnanie -- optimalizacia sa snazi zarovnat data v pamati, tak aby boli pristupne co najrychlejsie 10. Odstranovanie smeti 10.1. podprogramy -- pri skoku sa meni kontext a prevadza sa skok -- vyuzitie inline -- rozhodovanie cyklu -- branch prediction -- skocim/neskocim? tot otazka :) -- makro ma pri expanzii vzdy rovnaku podobu -- inline sa moze narozdiel od makra spracovavat rozne 10.2. Podmienene vyrazy -- najpravdepodobnejsie vyrazy sa ukladaju tak, aby boli cim prv vyhodnotene -- niektore kompilatory mozu poradie vyrazov preskladat 10.3. Podmieneny vyraz v cykle -- kazdy if v cykle rozbije pipeline 10.4. Typova konverzia -- odstranenie typovych nezrovnalosti este za kompilacie programu 10.5. Spracovanie pola -- jednoduhsi vyraz je vyhodnejsi pre vypocet indexu pola -- rozbalenie vypoctu do samostatnych krokov 10.6. Flow dependency -- procesor si pamata posledne operacie -- pripadne poslednych n operacii 10.7. Backward dependency -- A(I) = A(I-1) + B(I) ---- ----- -- v pripade, ze sa uvazuju polia ktore su rozne moze to komplikovat paralelizmus -- inak je mozne ukladat si vypocitanu hodnotu de registru a netahat ju neustale z pamate 10.8. Forward dependency -- A(I) = A(I+1) + B(I) ---- ----- -- je mozne pouzit paralelizaciu -- ak je namiesto konkretnej posuvovej konstanty umiestnena premenna nie je mozne urcit, aky typ zavislosti sa ma vyvolat 11. Rozvoj cyklu -- telo cyklu sa zopakuje za sebou (vhodne 4x) -- cykly su zarovnavane, tak, aby boli presne -- silny dopad na vsetky optimalizacie -- expanzia najvnutornejsich cyklov 12. Software pipelining -- prekladac sa pokusi odhadnut vhodny unroll -- pokusi sa predpovedat, ako sa bude spravat pipeline 13. Osetrovanie chyb -- ak dojde vo vnutri cyklu k preruseniu mozu byt vysledky rozne 14. Chyby -- nespravny pocet iteracii -- pri expanzii cyklu -- vypadky vyrovnavacej pamate -- pri prilisnom rozvoji instrukcii 15. Asociativne transformacie -- daxpy -- skalarny sucin -- zla paralelizovatelnost -- problem v poradi instrukcii 16. Blokovanie -- optimalizuju sa mnoziny paralalne spracovatelnych uloh -- pri nepriamej adresacii moze by kompilator agresivnejsi 17. Rucna virtualna pamat -- pri extremnych poziadavkach na pamat je vyhodnejsie spracovat pamat vlastnym emulatrom virtualnej pamate ##################### DISTRIBUOVANE VYPOCTY ##################################### 1. def -- task -- samostatne procesy nad samostatnymi datami -- zdielana pamat -- tam, kde sa pouziva malo komunikacie -- netrivialna cena -- nevhodne pre geolog. vypocty -- zasielanie sprav -- system vyhodnejsi pre optimalizaciu -- vysoka optimalizacia, nezavisla na pouzitom type paralelizmu 2. Linda -- abstraktny model pre pracu so sdielanou pamatou -- vsetka synchronizacia je riesena tabulou -- pri citani sa zadava vzor, ktory chcete nacitat -- teda maska typov, ktore boli zapisane -- system prehlada tabulu a pokial najde zodpovedajucu n-ticu tak ju vrati -- binarky sa zapisu na nastenku -- system spusti binarku a na stare miesto potom zapise exit code -- tabula predstavuje uzke miesto (primarny problem) -- existuju modely s viacerymi tabulami -- niektore modely umoznuju zasielat spravu o tom, ze dojde k ukonceniu procesu. -- retrieve -> proces bude ukonceny a ma sancu vycuvat 3. PVM -- Parallel Virtual Machine -- pvmd deamoni -- staraju sa o celu siet -- knihova funkcii pre pvm -- spolupracujuce ulohy -- vytvara dojem jedneho velkeho virtualneho stroja -- o komunikaciu sa staraju deamoni, ktorym procesy predavaju spravy -- pdm komunikuju pomocou protokolu UDP -- spolahlivost dorucenia garantuju deamoni -- TID -- identifikator vytvara tvorca skupiny -- skupina je odolna voci padom, ale musi prezit tvorca -- posielanie sprav cez buffry (nutne nastavit kodovanie sprav) -- dynamicka skupina -- za behu je mozne menit zlozenie skupiny -- slaba konzistencia -- pri kazdom dotaze je mozne ziskat iny vysledok (hlavne pri otazke z viacerych miest :) - (ono je predsalen rozdiel, ktorymi dverami vleziete na urad :))) -- nie je vhodne v pripade, ze vsetcia maju mat identicke informacie -- umoznovala spustat procesy tam, kde ich treba -- system na zasielanie sprav nie je prilis prijemny -- je nutne definovat presne to, ako budu ukladane typy do bufferov -- model PVM je flat => nie je mozne napisat knihovny 4. MPI -- abstraktnejsi typ -- stara sa len o komunikaciu -- ma omnoho cistejsie nastroje na komunikaciu ako PVM -- problem v tom, ze kazda implementacia sa dohovara inak, teda rozne implementacie sa nevedia dohovorit -- urcuje sa velkost bufferu -- je lepsie poskladat sendy do jedneho velkeho a potom ho odoslat. Komunikacna narocnost je prilis vysoka pri malych blokoch -- sprava je tvorena: 1. adresou 2. citacom datoveho typu 3. datovy prvok -- mnozina kanalov vytvara kontext -- kontexty sda navzajom neovplyvnuju -- toto umoznuje vytvarat knihovny a aplikacie komunikujuce rovnakymi menami -- IPM sa stara o to, ze su samostatne -- procesy sa daju zgrupovat -- komunikator: na jednom kanale je mozne oddelit komunikaciu a posielanie dat. nie je nutne budovat a rusit kanale -- prevedie sa otvorenie kanalu a o ostatne sa stara IPM -> perzistentne kanaly -- kolektivna komunikacia -> broadcast -> scather gather -- niekto ma nejake data a potrebuje ich poslat vsetkym, oni ich upravia a posielaju ich spracovane spat -- velmi efektivne -> all to whole -- vsetcia so vsetkymi si vymienaju data -- virtualne topologie -> je mozne nadefinovat, ako ma vyzerat fyzicka topologia pre vhodne nastavenie siete -- MPI vyzaduje podporu operacneho systemu -- na spustanie aplikacii -- sprava moze niest aj binarku, ktora sa ma spustit -- musi byt explicitne napisana cast osetrujuca vynimky -- riadenie formou hooks -> odbocka, ktora zapisuje, co sa v kanali dialo (chybaju ladiace nastroje) -- send-recieve protokol -- kolko sprav si musia poslat na to, aby sa mohla inicializovat uspesna komunikacia -- je nutna apriorna dohoda o tom, aky protokol pouzit 4.1. Datove typy -- mozne definovat struktury s dierami -- struktura sa prenasa spolu so spravou (rozdiel od PVM) -- MPI prevadza kontrolu na spravnost dat (prip. kontrolu konverzie dat)