Principy počítačů I – Taxonomie, organizace s vysokým výkonem ___________________________________
snímek 1
___________________________________ ___________________________________
Principy počítačů
___________________________________
Část IX Taxonomie, organizace s vysokým výkonem
___________________________________ ___________________________________
1
© VJJ
___________________________________
snímek 2
___________________________________
Flynnova taxonomie
___________________________________
ÅSISD - Single Instruction Single Data
___________________________________
ÅSIMD - Single Instruction Multiple Data
___________________________________
ÅMISD - Multiple Instruction Single Data ÅMIMD - Multiple Instruction Multiple Data
___________________________________ 2
© VJJ
___________________________________ ___________________________________
snímek 3
___________________________________
Stroje SISD P
M
___________________________________
PMS diagram stroje SISD
___________________________________
• klasické stroje von Neumannova typu
___________________________________
• problém se zařazením vektorových strojů
___________________________________
• dynamický pohled - stroje SISD • statický pohled - stroje SIMD © VJJ
3
___________________________________ ___________________________________
snímek 4
___________________________________
Stroje SIMD M
K
P
Md
P
Md
P
Md
___________________________________
PMS diagram stroje SIMD Lokální paměť
___________________________________
Procesorový element (aktivní nebo nečinný)
___________________________________
Řadič - zodpovídá za vyzdvižení, dekódování a přidělení instrukce
___________________________________
vektorové zpracování - distribuce elementů vektoru do lokálních pamětí 4
© VJJ
___________________________________ ___________________________________
snímek 5
___________________________________
Stroje MISD
___________________________________
PMS diagram stroje MISD
___________________________________
Md Mi
P
Mi
P
Mi
P
• velmi málo strojů systolické pole
___________________________________
• proudová linka - nevyzvedává instrukce a operandy z lokální paměti
___________________________________ 5
© VJJ
___________________________________ ___________________________________
snímek 6
___________________________________
Stroje MIMD
___________________________________
PMS diagram stroje MIMD M
P M
© VJJ
___________________________________
M P
P
• široká škála zařízení -multiprocesorové stroje
___________________________________
• většinou použity pro paralelizaci úloh
P M
___________________________________
• počítačové sítě
6
___________________________________ ___________________________________
snímek 7
___________________________________
Další taxonomie
___________________________________
Ånejvětším problémem je začlenění vektorových procesorů Åpokusy o velmi složité taxonomie selhaly Årozšíření Flynnovy taxonomie o stroj SPMD Single Program Multiple Data synchonizovaný stroj MIMD, kde všechny procesory pracují pod řízením stejného programu.
___________________________________ ___________________________________ ___________________________________ 7
© VJJ
___________________________________ ___________________________________
snímek 8
___________________________________
Počítačové systémy s vysokým výkonem Implementace
___________________________________
Architektura Organizace
text
text
text
text
___________________________________ ___________________________________
Technologické postupy
___________________________________ 8
© VJJ
___________________________________ ___________________________________
snímek 9
___________________________________
Paralelizace
___________________________________
Åna úrovni úlohy Åna úrovni programu
___________________________________
Ånezávislost sekcí Ånezávislost iterací
___________________________________
Åna úrovni instrukcí Åna úrovni aritmetiky
___________________________________
Koncepce paralelního zpracování závisí na granularitě úlohy © VJJ
9
___________________________________ ___________________________________
snímek 10
___________________________________
Organizace s vysokým výkonem
___________________________________
Å multiprocesory MIMD se sdílenou pamětí
___________________________________
Å multiprocesorové vektorové stroje Å systémy MIMD s distribuovanými pamětmi
___________________________________
Å stroje SIMD
___________________________________
Å distribuované paměti
10
© VJJ
___________________________________ ___________________________________
snímek 11
___________________________________
Stroj MIMD se sdílenou pamětí
___________________________________
Stroj c.mmp - název odvozen od PMS diagramu
___________________________________ P
M
P
M
P
Základní element
M
P
M
P
M
P
M
___________________________________
Skupina
• původní verze s křížovým přepínačem, později strom • propojeny počítače PDP-11 • lineární adresový prostor • postupné vyřizování žádosti o přístup do paměti (NUMA)
___________________________________ 11
© VJJ
___________________________________ ___________________________________
snímek 12
___________________________________
KSR-1- sdílená virtuální paměť
___________________________________
P Mc
___________________________________
Druhá úroveň hierarchie, spojuje max. 34 kruhů první hierarchie
P Mc
P Mc
___________________________________ První úroveň hierarchie, spojuje max. 32 procesorů, rychlost 1GB/s
P Mc P
___________________________________
Vyrovnávací paměť 32 MB
Mc P Mc © VJJ
12
___________________________________ ___________________________________
snímek 13
___________________________________
Multiprocesorové vektorové stroje
___________________________________
Åvětšinou obsahují malé množství výkonných vektorových procesorů
___________________________________
Ånapř. CRAY C - 90 max. 16 procesorů Åvyladění paměťových modulů šířce pásma procesoru Åvíce paměťových modulů propojených sítí (víceúrovňové křížové přepínače) k procesorům
___________________________________ ___________________________________
Åvýjimka Fujitsu VPP500, 222 procesorů
13
© VJJ
___________________________________ ___________________________________
snímek 14
___________________________________
MIMD s distribuovanými pamětmi
___________________________________
Åprvní stroje s procesory Intel 8086 v síti hyperkrychle 16 až 128 procesorů (Cosmic Cube) Årůzné strategie výměny zpráv (jednoduché protokoly, „Worm Hole“) Åna bázi Cosmic Cube postaveny komerční počítače s procesory RISC i860 apod.
___________________________________ ___________________________________ ___________________________________ 14
© VJJ
___________________________________ ___________________________________
snímek 15
___________________________________
CM-5 (Thinking Machines) (1)
___________________________________
Topologie stroje používá „fat-tree“
___________________________________
4n 2n n
___________________________________
20 Mbit/s
___________________________________
Procesor SPARC, 32 MB paměti, vektorový koprocesor © VJJ
15
___________________________________ ___________________________________
snímek 16
___________________________________
CM-5 (Thinking Machines) (2)
___________________________________
Oddělená datová a řídící síť Pv
M
Pv
M
Pv
M
Pv
M Pv
P
M
Knet Datová síť
___________________________________
Kio
___________________________________
Knet Řídící síť
Datová síť
a) Datový uzel stroje CM-5
Řídící síť
___________________________________
b) Řídící uzel stroje CM-5
16
© VJJ
___________________________________ ___________________________________
snímek 17
___________________________________
SIMD - stroj CM-2
___________________________________
Jednobitový procesor stroje SIMD - CM-2 4 096 procesorů ve dvanáctirozměrné krychli řízen počítačem VAX
___________________________________
Vstup A
Paměť 4 kB
Vstup B
ALU
___________________________________
Vstup A
Adresy
Paměť podmínek
Podmínky
___________________________________
Řízení ALU
Výrazné zrychlení pro prohledávání databází, řazení záznamů 17
© VJJ
___________________________________ ___________________________________
snímek 18
___________________________________
SIMD - maticové stroje (1)
___________________________________
Řídící počítač Datová sběrnice
___________________________________
Řadič Řídící sběrnice P0
P1
P2
P3
Pn
M0
M1
M2
M3
Mn
___________________________________ ___________________________________
Propo jo vací síť
Maticový stroj s lokálními pamětmi © VJJ
18
___________________________________ ___________________________________
snímek 19
___________________________________
SIMD - maticové stroje (2)
___________________________________
Řídící počítač Datová sběrnice Řadič
Řízení propojova cího pole
___________________________________
Řídící sběrnice P0
P1
P2
P3
Pk
___________________________________
Propojovací síť
M0
M1
M2
M3
___________________________________
Mn
Maticový stroj se sdílenou pamětí 19
© VJJ
___________________________________ ___________________________________
snímek 20
___________________________________
Použití maticových strojů
___________________________________
Åmatematické modely založené na práci s maticemi (operace typu násobení, rozklad, inverze a výpočet vlastní hodnoty) Ålineární a celočíselné programování Åmodelování v meteorologii Åsignálové procesory (filtrace, FFT) Åzpracování map v geodézii a kartografii Åzpracování obrazů a analýza scény v reálném čase
___________________________________ ___________________________________ ___________________________________ 20
© VJJ
___________________________________ ___________________________________
snímek 21
___________________________________
Distribuované paměti (1)
___________________________________ Åuniversální procesor spojený s lokální pamětí (multipočítačové systémy)
___________________________________
Åvýkon je určen výkonem komunikačního systému
___________________________________
Åprogramovací techniky (synchronizace procesů)
___________________________________
© VJJ
21
___________________________________ ___________________________________
snímek 22
___________________________________
Distribuované paměti (2)
___________________________________ P M K0
Kn
P
M K0
PE0
Kn
___________________________________
PE1
___________________________________ P M K0
Kn
P
M K0
PE2
___________________________________
Kn PE3
22
© VJJ
___________________________________ ___________________________________
snímek 23
___________________________________
Porovnání SIMD a MIMD SIMD Åstejný program pro celý systém Åcentralizované řízení Åsynchronizace je vlastí již návrhu Åspeciální použití
___________________________________
MIMD Åkaždý procesor vlastní program Ådistribuované řízení Åobtížná synchronizace
___________________________________
Åobecnější návrh, větší segment aplikací
___________________________________
___________________________________
23
© VJJ
___________________________________ ___________________________________
snímek 24
___________________________________
Paralelní systémy podmínky omezující paralelní výpočet
___________________________________
Åzávislost toku dat - instrukce s1 produkuje vstupní data pro instrukci s2 Åzávislost výstupu - instrukce s1 a instrukce s2 zapisují do téže proměnné Åzávislost vstupu - instrukce s1 přepisuje vstupní data instrukce s2 Åvstupně/výstupní závislost - instrukce s1 a instrukce s2 zapisují do téhož souboru © VJJ
___________________________________ ___________________________________ ___________________________________ 24
___________________________________ ___________________________________
snímek 25
___________________________________
Latentní závislosti
___________________________________
Åzávislost indexů (např. indexované indexy) Åindexy, které neobsahují řídící proměnnou cyklu
___________________________________
Åproměnné, které se vyskytují pokaždé s jinými indexy
___________________________________
Ånelineární indexy
___________________________________ 25
© VJJ
___________________________________ ___________________________________
snímek 26
___________________________________
Granularita
___________________________________
Åúlohy Åprogramu Åpodprogramu Åcyklu Åstrojové instrukce Åmikroinstrukce
___________________________________ ___________________________________ ___________________________________ 26
© VJJ
___________________________________ ___________________________________
snímek 27
___________________________________
Paralelismus řízení
___________________________________
Åparalelní zpracování procedur nebo příkazů doplněných o paralelní konstrukty Åparalelní konstrukty založené na synchronizačních primitivech Åmodel stroje - propojení několika běžných procesorů, kde každý z nich vykonává instrukce podle stavu svého vlastního programového čítače © VJJ
___________________________________ ___________________________________ ___________________________________ 27
___________________________________ ___________________________________
snímek 28
___________________________________
Paralelismus datových toků
___________________________________ c0
input d,e,f; c[0]=0; for(i=1;i<=4;i++) { a[i]=d[i]+e[i]; b[i]=a[i]*f[i]; c[i]=b[i]+c[i]; }
d1
e1 f1 d2 +
e2 f2 d3 +
a1
+ a2
* c1
b2
c2
___________________________________
+ a4
*
+
e4 f4
a3
* b1
+
e3 f3 d4
* b3
+
c3
b4 +
___________________________________
c4
___________________________________
Datové položky poukazují na exekutibilní kód, který se začne vykonávat teprve tehdy, až všechna potřebná data budou k dispozici - vykonávání fragmentů kódu odspoda 28
© VJJ
___________________________________ ___________________________________
snímek 29
___________________________________
Redukční paralelismus
___________________________________
a=(b+1)*c-d/e
/
* c
+ b
d
1
e
Åsnaha po odstranění nízké efektivnosti stroje řízeného tokem dat Åodstartování fragmentu kódu vyvolá potřeba výsledku zpracování Åvede ke stromovému rozvoji operací
___________________________________ ___________________________________ ___________________________________ 29
© VJJ
___________________________________ ___________________________________
snímek 30
___________________________________
Parametry paralelního systému (1)
___________________________________
Nechť existuje program P, který vykonává Pt paralelních instrukcí během dostatečně malého časového intervalu t. Parametr Pt nazýváme profilem nebo paralelním profilem programu.
___________________________________ ___________________________________
Celkový počet operací E v čase t = t1 - t0 t1
E = µ ∫ Pt dt Idealizovaný výpočetní výkon jednoho procesoru © VJJ
___________________________________
t0
30
___________________________________ ___________________________________
snímek 31
___________________________________
Parametry paralelního systému (2)
___________________________________
Průměrný paralelizmus úlohy
φ=
µ t1 − t 0
t1
___________________________________
∫ P dt t
t0
___________________________________
Celkový čas běhu úlohy sekvenční běh
T1 =
plně paralelní běh ∞ i ∞ t =1
T =∑
E
µ
E i. µ
___________________________________ 31
© VJJ
___________________________________ ___________________________________
snímek 32
___________________________________
Parametry paralelního systému (3)
___________________________________
Asymptotické zrychlení
___________________________________
T (1) S∞ = = T (∞ )
E ∞ Ei ∑ i =1 i
___________________________________ ___________________________________ 32
© VJJ
___________________________________ ___________________________________
snímek 33
___________________________________
Průměrný výkon Aritmetický průměr
1 Wa = k
∑W i =1
___________________________________
Geometrický průměr
k
Wg = k
i
Harmonický průměr
Wh =
k
∏W
___________________________________
i
i =1
___________________________________
k k
1 ∑ i =1 Wi
___________________________________
Platí Cauchyho věta Wa > Wg > Wh © VJJ
33
___________________________________ ___________________________________
snímek 34
___________________________________
Průměrné harmonické zrychlení
___________________________________
Pro sekvenční běh programu
1 =1 W1
T1 =
Průměrné harmonické zrychlení výpočtu na stroji s i procesory
Pro paralelní běh programu
Ti =
S=
1 1 = Wi i
1 wi
∑n⋅W i
___________________________________ ___________________________________
i
34
© VJJ
___________________________________
___________________________________ ___________________________________
snímek 35
___________________________________
Okrajové stavy systému
___________________________________
1. n-procesorový stroj může používat libovolný stupeň paralelizace ke zpracování 1/n úlohy 2. i procesorů zpracovává paralelně části úlohy, které jsou úměrné i 3. i procesorů zpracovává paralelně části úlohy, které jsou úměrné převrácené hodnotě i 4. úloha má dvě části, jedna se zpracovává pouze sekvenčně, druhá pouze paralelně na n procesorech
___________________________________ ___________________________________ ___________________________________ 35
© VJJ
___________________________________ ___________________________________
snímek 36
___________________________________ Případ 1.
___________________________________
Použité váhy jsou stejné
1 w1 = w2 = K = n
___________________________________
Průměrné harmonické zrychlení
Sn =
1 n
1
∑i⋅n i =1
=
n Ψ ( n) + C
Eulerova konstanta
___________________________________ ___________________________________
Gamma funkce
Některé hodnoty S2=1,33 S32=7,88 S1024=136,36 © VJJ
36
___________________________________ ___________________________________
snímek 37
___________________________________ Případ 2.
___________________________________
Použité váhy odpovídají předpisu n
1 2 3 n w1 = , w2 = , w3 = , L , wn = , q q q q
q=∑i = i =1
n(n + 1) 2
___________________________________
Průměrné harmonické zrychlení
Sn =
1 n
i ∑ i =1 i ⋅ q
=
___________________________________
q n +1 = 2 n
___________________________________
Asymptotické zrychlení 50% 37
© VJJ
___________________________________ ___________________________________
snímek 38
___________________________________ Případ 3.
___________________________________
Použité váhy odpovídají předpisu
n n −1 n−2 1 w1 = , w2 = , w3 = , L , wn = q q q q
___________________________________
Průměrné harmonické zrychlení
Sn =
n
∑ i =1
___________________________________
1 1 n(n + 1) = ⋅ n + 1 − i 2 2 − n + Ψ (n) ⋅ (n + 1) + C (n + 1) i⋅q
___________________________________
Některé typické hodnoty S2=1,2 S32=5,18 S1024=78,64 38
© VJJ
___________________________________ ___________________________________
snímek 39
___________________________________ Případ 4 - Amdahlův zákon
___________________________________
Použité váhy odpovídají předpisu
w1 = s , w2 = w3 = L wn−1 = 0, wn =1 − s
___________________________________
Průměrné harmonické zrychlení
1 n n Sn = = = 1 − s n ⋅ s + 1 − s s ( n − 1) + 1 s+ n
___________________________________ ___________________________________
V limitním případě n
© VJJ
lim∞ S n =
1 s 39
___________________________________ ___________________________________
snímek 40
___________________________________
Amdahlovův zákon (2)
___________________________________
140
120
___________________________________
128 proces orů
Zrychlení výpočtu
100
80
___________________________________
64 proces orů
60
32 proces orů
40
16 proces orů
___________________________________
8 proces orů
20
2 procesory
0 0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
0,8
0,9
1
S tupe ň parale lno s ti úlo hy
40
© VJJ
___________________________________ ___________________________________
snímek 41
___________________________________
Účinnost paralelního zpracování
___________________________________
On počet operací na n-procesorovém systému Tn poměrná doba zpracování programu v nprocesorovém systému Zrychlení
Sn =
T1 Tn
Účinnost
ηn =
___________________________________ ___________________________________
; 1 ≤ Sn ≤ n
___________________________________
1 ≤η ≤1 n
Sn T = 1 n n ⋅ Tn
41
© VJJ
___________________________________ ___________________________________
snímek 42
___________________________________
Redundance a využití prostředků Redundance
Koeficient využití prostředků
Kvalita paralelizace
© VJJ
Qn =
Rn =
___________________________________
On O1
___________________________________
O U n = Rn ⋅ ηn = n n ⋅ Tn S nηn T12 = Rn n ⋅ Tn2 ⋅ On
;
___________________________________ ___________________________________
Qn < S n 42
___________________________________ ___________________________________
snímek 43
___________________________________
Účinnost paralelních algoritmů
___________________________________
Ågranularita Åprofil paralelního zpracování Åzpůsob komunikace jednotlivých částí stroje Åzvolený způsob synchronizace procesů Åspolečné prvky návrhu Åpožadavky na paměť a její organizace
___________________________________ ___________________________________ ___________________________________ 43
© VJJ
___________________________________ ___________________________________
snímek 44
___________________________________
Účinnost paralelizace
___________________________________
Účinnost paralelizace
E=
w( s ) w( s ) + h( s, n)
___________________________________ ___________________________________
Funkce rovnoměrné účinnosti
w( s ) = © VJJ
E ⋅ h( s, n, ) 1− E
___________________________________ 44
___________________________________ ___________________________________
