IA039: Architektura superpoˇc´ıtaˇc˚ u a n´aroˇcn´e v´ypoˇcty Paraleln´ı poˇc´ıtaˇce Ludˇek Matyska Fakulta informatiky MU
Jaro 2014
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
1 / 63
Paraleln´ı poˇc´ıtaˇce
Small-scale multiprocessing 2–16 procesor˚ u pˇrev´aˇznˇe SMP (sd´ılen´a pamˇeˇt)
Large-scale multiprocessing > 100 (i tis´ıce) procesor˚ u Zpravidla distribuovan´a pamˇeˇt
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
2 / 63
Paraleln´ı poˇc´ıtaˇce (II)
Architektura Single Instruction Multiple Data, SIMD Multiple Instruction Multiple Data, MIMD
Programovac´ı modely Single Program Multiple Data, SMPD Multiple programs Multiple Data, MPMD
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
3 / 63
Architektura – SIMD
Procesory synchronizov´any Vˇsechny vykon´avaj´ı vˇzdy stejnou instrukci Analogie vektorov´ych procesor˚ u
Jednoduch´e procesory Jednoduˇsˇs´ı programovac´ı model
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
4 / 63
Architektura – MIMD
Plnˇe asynchronn´ı syst´em Procesory zcela samostatn´e Nen´ı tˇreba speci´aln´ı v´yroba (off-the-shelf)
V´yhody Vyˇsˇs´ı flexibilita Teoreticky vyˇsˇs´ı efektivita
Nev´yhody Explicitn´ı synchronizace Sloˇzit´e programov´an´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
5 / 63
Komunikaˇcn´ı modely
Sd´ılen´a pamˇeˇt (Shared Memory Architecture) Pˇred´av´an´ı zpr´av (Message passing)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
6 / 63
Sd´ılen´a pamˇeˇt
Pamˇeˇt odˇelen´a od procesor˚ u Uniformn´ı pˇr´ıstup k pamˇeti Nejsnazˇs´ı propojen´ı – sbˇernice ,,Levn´a‘‘ komunikace Sloˇzit´e prokl´ad´an´ı v´ypoˇctu a komunikace (aktivn´ı ˇcek´an´ı)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
7 / 63
Pˇred´av´an´ı zpr´av
Kaˇzd´y procesor ,,viditeln´y‘‘ Vlastn´ı pamˇeˇt u kaˇzd´eho procesoru Explicitn´ı komunikace – pˇred´av´an´ı zpr´av Vysok´a cena komunikace (v´ymˇeny dat) Moˇznost prokl´ad´an´ı v´ypoˇct˚ u a komunikace
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
8 / 63
Hybridn´ı syst´emy
Nonuniform memory access architecture (NUMA) Cache-only memory access architecture (COMA) Distributed shared-memory (DSM)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
9 / 63
Non-uniform memory access
Pˇr´ıstup k ruzn´ym fyzick´ym adres´am trv´a r˚ uznou dobu Umoˇzn ˇuje vyˇsˇs´ı ˇsk´alovatelnost Potenci´alnˇe niˇzˇs´ı propostnost Koherence vyrovn´avac´ıch pamˇet´ı ccNUMA
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
10 / 63
Cache only memory access
NUMA s charakterem vyrovn´avac´ı pamˇeti Data putuj´ı k procesor˚ um, kter´e je pouˇz´ıvaj´ı Pouze zd´anliv´a hierarchie Syst´em mus´ı hl´ıdat, ˇze m´a jedinou kopii
Experiment´aln´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
11 / 63
Distributed shared-memory
Distribuovan´y syst´em – cluster Lok´aln´ı pamˇeˇt kaˇzd´eho uzlu Vzd´alen´a pamˇeˇt ostatn´ıch uzl˚ u
,,Fikce‘‘ jedn´e rozs´ahl´e pamˇeti Hardwarov´e ˇreˇsen´ı Zpravidla vyuˇz´ıv´a princip˚ u virtu´aln´ı pamˇeti Transparentn´ı
Softwarov´e ˇreˇsen´ı Knihovna Netransparentn´ı, progam´ator program mus´ı explicitnˇe pˇrizp˚ usobit
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
12 / 63
Koherence vyrovn´avac´ıch pamˇet´ı
Pˇr´ıˇciny v´ypadku vyrovn´avac´ı pamˇeti: Compulsory miss: 1. pˇr´ıstup k dat˚ um Capacity miss: nedostateˇcn´a kapacita Conflict miss: r˚ uzn´e adresy mapov´any do stejn´eho m´ısta Coherence miss: r˚ uzn´a data v r˚ uzn´ych vyrovn´avac´ıch pamˇet´ıch
Posledn´ı pˇr´ıpad se t´yk´a multiprocesor˚ u
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
13 / 63
ˇ sen´ı probl´emu koherence Reˇ
Vyrov´avac´ı pamˇeti mus´ı vˇedˇet o zmˇenˇe Metody zaloˇzen´e na broadcastu Adres´aˇrov´e metody
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
14 / 63
Snoopy cache
Broadcastov´y pˇr´ıstup Propojovac´ı s´ıtˇe s ,,pˇrirozen´ym‘‘ brodcastem – sbˇernice
Kaˇzd´y procesor sleduje vˇsechny pˇr´ıstupy k pamˇeti
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
15 / 63
Zneplatnˇen´ı
Reakce na zmˇenu dat ve vzd´alen´e (vyrovn´avac´ı) pamˇeti ˇ adka v aktu´aln´ı (naslouchaj´ıc´ı) vyrovn´avac´ı pamˇeti je zneplatnˇena R´ V pˇr´ıpadˇe opˇetn´eho pˇr´ıstupu je pˇrehr´ana ze vzd´alen´e pamˇeti
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
16 / 63
Update
ˇ adka je okamˇzitˇe obnovena R´ Pˇri opˇetovn´em pˇr´ıstupu je jiˇz k dispozici Nev´yhody Faleˇsn´e sd´ılen´ı (nepracuj´ı na stejn´ych datech) Pˇr´ıliˇsn´e zat´ıˇzen´ı sbˇernice
Nelze rozhodnout, zda update nebo zneplatnˇen´ı je obecnˇe lepˇs´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
17 / 63
Koherence vyrovn´avac´ıch pamˇet´ı II
Snoopy schema zaloˇzen´e na broadcastu Nepouˇziteln´e u sloˇzitˇejˇs´ıch propojovac´ıch s´ıt´ı Nen´ı rozˇsiˇriteln´e (scalable)
Redukce ,,osloven´ych‘‘ vyrovn´avac´ıch pamˇet´ı – Adres´aˇre Poloˇzka u kaˇzd´eho bloku pamˇeti Odkazy na vyrovn´avac´ı pamˇeti s kopi´ı tohoto bloku Oznaˇcen´ı exkluzivity (pr´avo pro ˇcten´ı)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
18 / 63
Adres´aˇrov´e pˇr´ıstupy
Tˇri z´akladn´ı schemata Plnˇe mapovan´e adres´aˇre ˇ asteˇcnˇe (Limited) mapovan´e adres´aˇre C´ Prov´azan´e (chained) adres´aˇre
Zhodnocen´ı vlastnost´ı Na z´akladˇe velikosti potˇrebn´e pamˇeti Na z´akladˇe sloˇzitosti (poˇctu pˇr´ıkaz˚ u) protokolu
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
19 / 63
Plnˇe mapovan´e adres´aˇre
Kaˇzd´a adres´aˇrov´a poloˇzka m´a tolik u ´daj˚ u, kolik je vyrovn´avac´ıch pamˇet´ı (procesor˚ u) Bitov´y vektor ,,pˇr´ıtomnosti‘‘ Nastaven´y bit znamen´a, ˇze pˇr´ısluˇsn´a vyrovn´avac´ı data m´a kopii bloku pamˇeti
Pˇr´ıznak exkluzivity Staˇc´ı jeden na blok Jen jedna vyrovn´avac´ı pamˇeˇt
Pˇr´ıznaky v kaˇzd´e vyrovn´avac´ı pamˇeti (kaˇzd´y blok) Pˇr´ıznak platnosti Pˇr´ıznak exkluzivity
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
20 / 63
Omezen´e adres´aˇre
Pln´e adres´aˇre velmi pamˇeˇtovˇe n´aroˇcn´e Velikost pamˇeti: P2 M/B P je poˇcet vyrovn´ avac´ıch pamˇet´ı M velikost hlavn´ı pamˇeti B velikost bloku
Data nejsou zpravidla ˇsiroce sd´ılena Vˇetˇsina adres´aˇrov´ych bit˚ u m´a hodnotu nula
Pouˇzit´ı pˇr´ım´ych odkaz˚ u Nebude jiˇz staˇcit jeden bit
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
21 / 63
Omezen´e adres´aˇre II
Mnoˇzina ukazatel˚ u na vyrovn´avac´ı pamˇeti Dynamick´a alokace dle potˇreby
Vlastnosti Poˇcet bit˚ u ukazatele: log2 P Poˇcet poloˇzek v poolu ukazatel˚ u: k V´yhodnˇejˇs´ı neˇz pˇr´ımo mapovan´a: pokud k <
P log2 P
Informov´any jen explicitnˇe uveden´e vyrovn´avac´ı pamˇeti
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
22 / 63
Pˇreteˇcen´ı
Pokud pˇrestanou staˇcit poloˇzky Pˇr´ıliˇs mnoho sd´ılen´ych blok˚ u
Moˇzn´e reakce Zneplatnˇen´ı vˇsech sd´ılen´ych (brodcast, Diri B) V´ybˇer jedn´e poloˇzky (i n´ahodnˇe) a jej´ı zneplatnˇen´ı (bez broadcastu, Diri NB)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
23 / 63
Dalˇs´ı schemata
Coarse-vector (Diri CVr ) r je velikost regionu (v´ıce procesor˚ u), kter´emu odpov´ıd´a jeden bit (tedy v´ıce procesor˚ u) Pˇrepnut´ı interpretace pˇri pˇreteˇcen´ı Omezen´y broadcast vˇsem procesor˚ um v oblasti.
LimitLESS: programov´e pˇreruˇsen´ı pˇri pˇreteˇcen´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
24 / 63
Prov´azan´a schemata
Cache-Based linked-list Centr´alnˇe pouze jedin´y ukazatel Ostatn´ı ukazatele sv´az´any s vyrovn´avac´ı pamˇet´ı Vyrovn´avac´ı pamˇeti ,,prov´azany‘‘ ukazateli
V´yhody Minimalizace pamˇeˇtov´ych n´arok˚ u
Nev´yhody: Sloˇzit´y protokol. Zv´yˇsen´a komunikace (v´ıce zpr´av neˇz nutno) Z´apis je delˇs´ı (sekvenˇcn´ı proch´azen´ı seznamu)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
25 / 63
Hierarchick´e adres´aˇre
Pouˇzit´e v syst´emech s v´ıcen´asobn´ymi sbˇernicemi Hierarchie vyrovn´avac´ıch pamˇet´ı Vyˇsˇs´ı u ´roveˇ n na kaˇzd´em propojen´ı sbˇernic Vyˇsˇs´ı pamˇeˇtov´e n´aroky Vyˇsˇs´ı u ´roveˇ n mus´ı drˇzet kopie pamˇeˇtov´ych blok˚ u sd´ılen´ych niˇzˇs´ı u ´rovn´ı Nen´ı tˇreba rychl´ a pamˇeˇt
V principu hierarchie snoopy protokol˚ u
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
26 / 63
Rozˇsiˇritelnost (Scalability)
Nen´ı jednotn´a definice Pouˇz´ıvan´e z´akladn´ı formulace – rozˇsiˇriteln´y je takov´y syst´enm, pro nˇejˇz plat´ı: V´ykon roste line´arnˇe s cenou Je zachov´an konstantn´ı pomˇer Cena/V´ykon
Alternativn´ı parametr – M´ıra rozˇsiˇritelnosti Zmˇena v´ykonu pˇrid´an´ım procesoru Zmˇena ceny pˇrid´an´ım procesoru Smyslupln´y rozsah poˇctu procesor˚ u
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
27 / 63
Zrychlen´ı
S(N) = =
TEXEC (1) TEXEC(N) Tcomp (1) + Tcomm (1) Tcomp (N) + Tcomm (N)
Ide´aln´ı zrychlen´ı vyˇzaduje Tcomp (N) = Tcomp (1)/N Tcomm (N) = Tcomm (1)/N
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
28 / 63
Zrychlen´ı – koment´aˇr
Teoretick´y pojem, realita z´avis´ı na aplikaci R˚ uzn´e hodnoty pro r˚ uzn´e aplikace Vliv paralelizovatelnosti probl´emu (Amdal˚ uv z´akon)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
29 / 63
Rozˇsiˇriteln´e propojovac´ı s´ıtˇe
Poˇzadavky na ide´aln´ı s´ıˇt: N´ızka cena rostouc´ı line´arnˇe s poˇctem procesor˚ u (N) Minim´aln´ı latence nez´avisl´a na N Propustnost rostouc´ı line´arnˇe s N
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
30 / 63
Vlastnosti s´ıt´ı
Tˇri z´akladn´ı komponenty Topologie Pˇrep´ın´an´ı dat (jak se data pohybuj´ı mezi uzly) Smˇerov´an´ı dat (jak se hled´a cesta mezi uzly)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
31 / 63
Propojovac´ı s´ıtˇe
Rozliˇsujeme n´asleduj´ıc´ı z´akladn´ı parametry Velikost s´ıtˇe – poˇcet uzl˚ uN Stupeˇ n uzlu d Polomˇer s´ıtˇe D Nejdelˇs´ı nejkratˇs´ı cesta
Bisection width B Redundance s´ıtˇe A Minim´ aln´ı poˇcet hran, kter´e je tˇreba odstranit, aby se s´ıˇt rozpadla na dvˇe
Cena C Poˇcet komunikaˇcn´ıch linek v s´ıti
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
32 / 63
Bisection width
ˇıˇrka rozp˚ S´ ulen´ı Minim´aln´ı poˇcet linek, kter´e je tˇreba odstranit, aby se syst´em rozpadl na dvˇe stejn´e ˇc´asti
Bisection bandwidth – propustnost pˇri rozp˚ ulen´ı Celkov´a kapacita (propustnost) v´yˇse odstranˇen´ych linek
Ide´aln´ı vlastnost: Bisection badnwidth vztaˇzen´a na procesor je v dan´em syst´emu konstantn´ı.
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
33 / 63
Topologie pˇrep´ınac´ıch s´ıt´ı
Klasifikace na z´akladˇe rozmˇeru Jednorozmˇern´e Dvourozmˇern´e Tˇr´ırozmˇern´e Hyperkrychle
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
34 / 63
Jednorozmˇern´e propojovac´ı s´ıtˇe
Liner´an´ı pole Jednotliv´e prvky nav´az´any na sebe ,,Kor´alky‘‘
Nejjednoduˇsˇs´ı Nejhorˇs´ı vlastnosti
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
35 / 63
Dvourozmˇern´e propojovac´ı s´ıtˇe
Kruh Uzavˇren´e line´arn´ı pole
Hvˇezda Strom Sniˇzuje polomˇer s´ıtˇe (2 log N+1 ) 2 St´ale ˇspatn´a redundance a bisection (band)width Tlust´y strom (fat tree) Pˇrid´ av´ a redundantn´ı cesty ve vyˇsˇs´ıch u ´rovn´ıch
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
36 / 63
Dvourozmˇern´a mˇr´ıˇzka
Velmi popul´arn´ı Dobr´e vlastnosti Polomˇer 2(N1/2 − 1) Bisection N1/2 Redundance 2
Avˇsak vyˇsˇs´ı cena a promˇenn´y stupeˇ n uzlu
Torus Uzavˇren´a dvourozmˇern´a mˇr´ıˇzka Polomˇer N1/2 Bisection 2N1/2 Redundance 4 Vyˇsˇs´ı cena – pˇrid´ a 2N1/2 hran
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
37 / 63
Tˇr´ırozmˇern´a s´ıˇt
Vlastnosti Polomˇer 3(N1/3 − 1) Bisection N2/3 Redundance 3 Cena akceptovateln´a 2(N − N2/3 )
Konstrukˇcnˇe sloˇzit´a
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
38 / 63
Hyperkrychle
Velmi zaj´ımav´a topologie Obecnˇe n-rozmˇern´a krychle Z´akladn´ı parametry Polomˇer log N Bisection N/2 Redundance log N Vyˇsˇs´ı cena (N log N)/2
Mˇr´ıˇzky speci´aln´ımi pˇr´ıpady hyperkrychle Snadn´e nalezen´ı cesty Bin´arn´ı ˇc´ıslov´an´ı uzl˚ u
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
39 / 63
Plnˇe propojen´e s´ıtˇe
Teoretick´a konstrukce Vynikaj´ıc´ı polomˇer (1) Neakceptovateln´a cena (N ∗ (N − 1)/2) a stupeˇ n uzlu (N − 1)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
40 / 63
Pˇrep´ın´an´ı
Konkr´etn´ı mechanismus, jak se paket dostane ze vstupu na v´ystup Z´akladn´ı pˇr´ıstupy Pˇrep´ın´an´ı paket˚ u, store-and-forward Pˇrep´ınan´ı obvod˚ u Virtu´aln´ı propojen´ı (cut-through) Smˇerov´an´ı ˇcerv´ı d´ırou (wormhole routing)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
41 / 63
Store-and-forward
Cel´y paket se uloˇz´ı A n´aslednˇe pˇrepoˇsle Jednoduch´e (prvn´ı generace paraleln´ıch poˇc´ıtaˇc˚ u) Vysok´a latence
P B
∗D
P je d´elka paketu, B je propustnost a D je poˇcet ,,hop˚ u‘‘ (vzd´alenost)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
42 / 63
Pˇrep´ın´an´ı okruh˚ u
Tˇri f´aze Ustaven´ı spojen´ı – zah´ajeno vzorkem (probe) Vlastn´ı pˇrenos Zruˇsen´ı spojen´ı
V´yraznˇe niˇzˇs´ı latence
P B
∗D+
M B
P je v tomto pˇr´ıpadˇe d´elka vzorku a M je d´elka zpr´avy (nejsou nutn´e pakety) Pro P << M latence nen´ı z´avisl´a na d´elce cesty
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
43 / 63
Virtu´aln´ı propojen´ı
Zpr´avu rozdˇel´ıme do menˇs´ıch blok˚ u – flow control digits (flits) Prvn´ı flits obsahuje informace o cestˇe (pˇredevˇs´ım c´ılovu ardresu) Dalˇs´ı flits-y obsahuj´ı vlastn´ı data Posledn´ı flits ruˇs´ı cestu
Pos´ıl´ame jednotliv´e flits-y kontinu´alnˇe Jsou-li buffery dostateˇcnˇe velk´e, odpov´ıd´a pˇrep´ın´an´ı okruh˚ u
Latence
HF B
∗D+
M B
HF je d´elka flitsu, zpravidla HF << M
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
44 / 63
ˇ ı d´ıra Cerv´
Speci´aln´ı pˇr´ıpad virtu´aln´ıho propojen´ı Buffery maj´ı pr´avˇe d´elku flits Latence nez´avis´ı na vzd´alenosti Analogie pipeline Paket je rozloˇzen v bufferech nˇekolika uzl˚ u – odtud ˇcerv´ı d´ıra
Podporuje replikace paket˚ u Vhodn´e pro multicast a broadcast
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
45 / 63
Virtu´aln´ı kan´aly
Sd´ılen´ı fyzick´ych kan´al˚ u Nˇekolik buffer˚ u nad stejn´ym kan´alem Flits uloˇzen v pˇr´ısluˇsn´em bufferu
Vyuˇzit´ı Pˇret´ıˇzen´a spojen´ı Z´abrana deadlocku Mapov´an´ı logick´e na fyzickou topologii Garance propustnosti syst´emov´ym dat˚ um
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
46 / 63
Smˇerov´an´ı v propojovac´ıch s´ıt´ıch
Hled´an´ı cesty Vlastnosti Statick´e smˇerov´an´ı Zdrojov´e Distribuovan´e
Adaptivn´ı smˇerov´an´ı (vˇzdy distribuovan´e)
Minim´aln´ı a ne-minim´aln´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
47 / 63
Fault tolerance propojovac´ıch s´ıt´ı
Kontrola chyb Potvrzov´an´ı zpr´av Opakovan´e zas´ıl´an´ı zpr´av
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
48 / 63
Zpoˇzdˇen´ı pamˇeti
Pamˇeˇt v´yraznˇe pomalejˇs´ı neˇz procesor ˇ an´ı na pamˇeˇt podstatnˇe sniˇzuje v´ykon syst´emu Cek´
Moˇzn´a ˇreˇsen´ı: Sn´ıˇzen´ım zpoˇzdˇen´ı – zrychlen´ı pˇr´ıstupu Ukryt´ım zpoˇzdˇen´ı – pˇrekryv pˇr´ıstupu a v´ypoˇctu
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
49 / 63
Sn´ıˇzen´ı zpoˇzdˇen´ı pamˇeti
NUMA: NonUniform Memory Access Kaˇzd´e logick´e adrese odpov´ıd´a konkr´etn´ı fyzick´a adresa
COMA: Cache-Only Memory Architecture Hlavn´ı pamˇeˇt je ch´ap´ana jako attraction memory. ˇ adky pamˇeti se mohou volnˇe pˇresouvat. R´ Mohou existovat sd´ılen´e kopie ˇr´adk˚ u pamˇeti.
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
50 / 63
Rekapitulace
Communication to computation ratio
NUMA Small Large working working set set
COMA Small Large working working set set
Low
Good
Medium
Good
Good
High
Medium
Poor
Poor
Poor
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
51 / 63
Ukryt´ı zpoˇzdˇen´ı pamˇeti
Modely slab´e konzistence Prefetch Procesory s v´ıcen´asobn´ymi kontexty Komunikace iniciovan´a producentem
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
52 / 63
Slab´a konzistence
Nepoˇzaduje striktn´ı uspoˇr´ad´an´ı pˇr´ıstup˚ u ke sd´ılen´ym promˇen´ym vyjma synchronizaˇcn´ıch. Release consistency: Zaveden´ı operac´ı acquire a release
Fence operace Vynucen´e dokonˇcen´ı rozpracovan´ych operac´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
53 / 63
Prefetch
Pˇresun dat k procesoru s pˇredstihem. Binding prefetch Data pˇresunuta aˇz k procesoru Moˇzn´e poruˇsen´ı konzistence
Nonbinding prefetch Data pˇresunuta pouze do vyrovn´ avac´ı pamˇeti
HW Prefetch SW Prefetch Speci´aln´ı instrukce prefetch-exclusive: read n´asledovan´y pˇr´ıkazem write.
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
54 / 63
Procesory s v´ıcen´asobn´ymi kontexty
Podpora multitherading Vyˇzaduje Velmi rychl´e pˇrepnut´ı kontextu Vysok´y poˇcet registr˚ u
ˇ Rada experiment´aln´ıch syst´em˚ u HEP (70. l´eta) Tera *T
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
55 / 63
Komunikace iniciovan´a producentem
Analogie invalidace a update pˇri cache koherenci Specifick´e vyuˇzit´ı pro message-passing (Cray T3D) nebo block-copy (poˇc´ıtaˇce se sd´ılenou pamˇet´ı). Vhodn´e napˇr. pro pˇresun velk´ych blok˚ u dat ˇci pro synchronizaci z´amky (locks).
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
56 / 63
Podpora synchronizace
Synchronizace tvoˇr´ı ,,hork´a m´ısta‘‘ Z´akladn´ı synchronizaˇcn´ı primitivy: Vz´ajemn´e vylouˇcen´ı Dynamick´e rozloˇzen´ı z´atˇeˇze Informace o ud´alostech Glob´aln´ı serializace (bari´ery)
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
57 / 63
Vz´ajemn´e vylouˇcen´ı
K dan´e promˇenn´e m´a v dan´em okamˇziku pˇr´ıstup nejv´yˇse jeden proces Univerz´aln´ı, ovˇsem zpravidla zbyteˇcnˇe drah´e Synchronizaˇcn´ı konstrukce vyˇsˇs´ıch jazyk˚ u Semafory Monitory Kritick´e oblasti
Z´akladem – hardwarov´a podpora test&set instrukce test-and-test&set instrukce
Spin waiting protocol
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
58 / 63
test&set
Vlastnosti char *lock; while (exchange(lock, CLOSED) == CLOSED ); Busy waiting Vysok´e poˇzadavky na pˇrenos (ˇcast´e zneplatnˇen´ı) u multiprocer˚ u
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
59 / 63
test-and-test&set
Vlastnosti for (;;) while (*lock == CLOSED); if (exchange(lock, CLOSED) != CLOSED) break; Vyuˇzit´ı vyrovn´avac´ıch pamˇet´ı prvn´ı testy nad sd´ılenou kopi´ı
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
60 / 63
Pouˇzit´ı front
V´yhodnˇejˇs´ı Collision avoidance schemata Queue on lock bit (QOLB) protokol Nejefektivnˇejˇs´ı implementace Procesy ˇrazeny do fronty Po uvolnˇen´ı z´amku aktivov´an proces v ˇcele fronty Nen´ı tˇreba ˇz´adn´y sd´ılen´y pˇrenos dat
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
61 / 63
Z´amky v multiprocesorech
Souvis´ı i s moˇznost´ı dynamick´eho rozloˇzen´ı z´atˇeˇze Vyuˇzit´ı ˇcitaˇce s atomickou operac´ı Fetch&Op – ˇcitaˇce, napˇr. Op==Add fetch&add ( x, a) int *x, a; { int temp; temp = *x; *x += a; return (temp); } Compare&Swap – seznamy
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
62 / 63
Pouˇzit´ı
Informace o (glob´aln´ıch) ud´alostech pouˇz´ıv´ana pˇredevˇs´ım producentem jako prostˇredek, kter´ym jsou konzumenti informov´ani o novˇe dostupn´ych datech, a d´ale pˇri informaci o glob´aln´ı zmˇenˇe ve skupinˇe ekvivalentn´ıch proces˚ u (zmˇena urˇcit´eho stavu, kter´a mus´ı b´yt ozn´amena vˇsem proces˚ um).
Ludˇ ek Matyska (FI MU)
Paraleln´ı poˇ c´ıtaˇ ce
Jaro 2014
63 / 63
