2016 David Bednárek

Vývoj vysoce výkonného software

NPRG054 Vývoj vysoce výkonného software - 2015/2016 David Bednárek

1

O čem to bude


2

O čem to bude



Maximální využití výkonu procesoru a paměti



Moderní programování vs. výkon Relevantní vlastnosti moderních procesorů





  

ILP, SIMD

Nástroje pro ladění výkonu Co dokáže a co nedokáže překladač Paměťová hierarchie 

Cache-Aware a Cache-Oblivious algoritmy


3

O čem to nebude


4

O čem to nebude 

Programování v asembleru  



Paralelní programování  



Viz NPRG042 Programování v paralelním prostředí Poučení z minulých let: Pečlivá implementace jednovláknové verze přináší stejné zrychlení jako paralelizace

Optimalizace programů překladačem  



Překladače jsou většinou lepší než lidé Ale naučíme se využívat SIMD instrukce z C++

Viz NSWI109 Konstrukce překladačů Ale dozvíte se, co můžete od překladače očekávat

Programovací prostředky pro clustery, gridy, cloudy, ... 

K tomu je zapotřebí zkušenost s paralelismem a spolehlivostí


5


6

Proč?


7

DÚ ZS 2012/2013 – výsledky studentů bez motivace k optimalizaci 100

10

1

0.1

0.01

0.001


8

DÚ ZS 2012/2013 - výsledky studentů s motivací k optimalizaci 1 128 zeros

128 128 ones 256 zeros 256 256 ones 512 zeros 512 512 ones random random random

1024 zeros

1024 1024 ones random

2048 zeros

2048 2048 ones random

0.1

0.01

0.001 NPRG054 Vývoj vysoce výkonného software - 2015/2016 David Bednárek

9

Motivační příklad


10

Motivační příklad 

Hromada jablek a pomerančů, spočítejte zrníčka

class Apple ... { ... ... int seeds() { return ...; } };

class Orange ... { ... ... int seeds() { return ...; } }; vector< Apple + Orange> data;


11

Motivační příklad class Fruit {



Klasické objektové řešení

...



virtual int seeds() = 0;



};

Abstraktní třída s virtuální funkcí Konkrétní třídy  

class Apple : public class Fruit {



virtual int seeds() { return ...; }

Kontejner 

... };

Různá data Různé implementace virtuální funkce Obsahuje ukazatele na abstraktní třídu

virtual int seeds() { return ...; }

Toto řešení existuje ve všech objektových jazycích

...



class Orange : public class Fruit {

}; vector< Fruit *> data;




V jazyzích s referenční semantikou jsou ukazatele skryté

List< Fruit> data;

12

Motivační příklad class Fruit {



Jak je to rychlé?



Testovací data

virtual int seeds() = 0; }; class Apple : public class Fruit { virtual int seeds() { return d2; }



int d1, d2, d3;



};

5 konkrétních tříd lišících se počtem datových položek Implementace virtuální funkce čtou některou z položek

class Orange : public class Fruit { virtual int seeds() { return d3; } int d1, d2, d3, d4, d5;



Kontejner naplněn náhodnou směsí konkrétních tříd

}; vector< Fruit *> data;

int s = 0; for_each( data.begin(), data.end(), [&]( Fruit * p) { s += p->seeds(); }); NPRG054 Vývoj vysoce výkonného software - 2015/2016 David Bednárek

13

Motivační příklad void test() {



Testovací prostředí 

int s = 0;



for_each( data.begin(), data.end(), [&]( Fruit * p) { s += p->seeds(); });

Test je opakován N-krát N je voleno tak, aby celkový čas byl přiměřený 

V našem testu sekundy

}

 generate_data();

Program si měří čas sám 

test(); // cold run 

time_before = now(); for ( int i = 0; i < N; ++ i) test(); time_after = now(); cout << (time_after - time_before) / N;





Ty lepší jsou pouze pro privilegované

V našem testu měříme "wall clock"   


Ve standardu C++ vhodná funkce now() není Plaformy nabízejí různé možnosti

Je to to, co uživatele zajímá? Zatíženo paralelně běžícími procesy Granularita 1-10 ms

14

Výsledky 

Výsledky testu 



Celkem 10,4 ms 10,4 ns na objekt







Intel Core2Quad Q6700 2,66 GHz 4 GB RAM

1 000 objektů  



Hardware

1 000 000 objektů 





Celkem 9,0 µs 9,0 ns na objekt





Spolehlivost výsledků? 

 

Při opakování se výsledky liší o 5-10% Pro orientaci dostatečné Statisticky správné měření je věda 

NSWI131 Vyhodnocování výkonnosti počítačových systémů

Operační systém



64-bitový kód



Překladače    


Windows 7 64-bit

MS Visual C++ 2010 MS Visual C++ 2012 Intel Composer XE 2013 Rozdíly menší než 5% 15

Výsledky - porovnání architektur na témže HW 

64-bitový kód (Intel-64) 

1 000 000 objektů 












1 000 000 objektů 






1 000 objektů  


Ukazatele jsou delší 



32-bitový kód (IA-32)


1 000 objektů 



Procesor vykonává více práce

Přesto běží rychleji!   

Architektura ma víc registrů Procesor je optimalizován pro tento mód Nebo je to jinak...


16

Výsledky - závislost na distribuci dat 

64-bitový kód (Intel-64) 

1 000 000 objektů náhodně 















2,8 ns na objekt


2,2 ns na objekt

1 000 000 objektů skupinově 



5,9 ns na objekt

1 000 objektů round-robin 



10,0 ns na objekt

1 000 000 objektů round-robin 



10,7 ns na objekt

1 000 objektů náhodně 

7,6 ns na objekt

1 000 objektů skupinově 



2,6 ns na objekt

1 000 000 objektů skupinově

1 000 000 objektů náhodně 

8,0 ns na objekt

1 000 objektů round-robin 



9,0 ns na objekt

1 000 000 objektů round-robin 

32-bitový kód (IA-32)

10,4 ns na objekt

1 000 objektů náhodně 



5,3 ns na objekt

1 000 objektů skupinově 

2,6 ns na objekt

17

Příčiny 

Predikce skoků   

Volání virtuální funkce je nepřímý skok Dokud není znám cíl skoku, dekódování instrukcí nemůže pokračovat Procesory předvídají cíle 

Z předchozích průchodů tímtéž kódem  





Asociativní paměť adresa skokové instrukce - adresa cíle Heuristické metody predikce

Call-return páry

Když predikce nevyjde 

 

Dekódované a částečně provedené instrukce se zahazují Čeká se na dekódování těch správných Zdržení v řádu jednotek až desítek cyklů procesoru


18

Příčiny 

Predikce skoků   

Volání virtuální funkce je nepřímý skok Dokud není znám cíl skoku, dekódování instrukcí nemůže pokračovat Procesory předvídají cíle 

Z předchozích průchodů tímtéž kódem  





Asociativní paměť adresa skokové instrukce - adresa cíle Heuristické metody predikce

Call-return páry

Když predikce nevyjde 

 

Dekódované a částečně provedené instrukce se zahazují Čeká se na dekódování těch správných Zdržení v řádu jednotek až desítek cyklů procesoru


19

Vývoj procesorů


20

Bill Dally, nVidia at HiPEAC 2015

21


22


23


24


25


26


27


28


29

Typické mikroarchitektury procesorů (2000-2012)


30


31

Intel Netburst Microarchitecture [2000]


32

Intel NetBurst Microarchitecture [2000]


33

Intel Core Microarchitecture Pipeline [2006]


34

Intel Core Microarchitecture 

Procesor (teoreticky) zvládá v jediném cyklu najednou:     



Fetch: 16 B (cca. 4 instrukce) z instrukční cache Decode: 1 až 5 instrukcí ALU: 3 jednodušší operace (add/mul) Memory load: 1 čtení (až 128 bitů) z L1 cache Memory store: 1 zápis (až 128 bitů) z L1 cache

Doba trvání operací (latence)      

integer add, mul: 1 FP add: 3, FP mul: 4-5 div: podle dat integer load: 3, FP load: 4 (L1 cache) store address: 3 store data: 2 (retirement, in-order)


35

Intel Core Microarchitecture 

Branch prediction  



Dekodér instrukcí   



loop cache (jednoduché cykly do 18 instrukcí) převod na mikrooperace 1:1, 1:N, 2:1 simulátor ukazatele zásobníku

Renamer 



podmínky, nepřímé skoky, call/return páry spekulativní provádění

16 logických registrů mapováno do 144 fyzických (podobně FP registry)

Out-of-order execution  

 

32 rozpracovaných mikrooperací (RS) z okna délky 96 (ROB) retirement: zápisy do paměti/registrů běží in-order opožděně na pozadí store forwarding: čekající čtení dostávají hodnotu přímo ze zápisu spekulativní čtení: nečeká se na předchozí store


36

Intel Nehalem Pipeline [2008]


37

Intel Sandy Bridge Pipeline [2011]


38

Intel vs. AMD architectures (realworldtech.com)


39

Intel Haswell Microarchitecture


40

Pohled překladače na procesor


41



Scheduling - volba uspořádání instrukcí 

Nejpodstatnější fáze překladače z hlediska výkonu kódu 



Platilo do nedávna, narušeno out-of-order execution v CPU

Hledá se takové pořadí které je 

Ekvivalentní z hlediska efektu/pravidel jazyka 



Vyhovuje dependencím

Nejrychlejší 

Model časování procesoru


42

Závislosti Závislost (dependence)  



Datová závislost (dependence) 



Povinnost provést jednu operaci/instrukci po jiné Částečné uspořádání operací/instrukcí v jednom BB Závislost producent-konzument v toku dat

Antidependence   

Read-Write: Čtení se musí stihnout před zápisem Write-Write: Pořadí zápisů se nesmí změnit Jiné důvody, obvykle nízkoúrovňového původu


43

Scheduling Scheduling pouze odhaduje 

Skutečné časování je ovlivněno nepředvídatelnými jevy 

Zbytky rozpracovaných instrukcí z předchozího kódu 



 



Řešení: Trace-scheduling, řízení profilem

Paměťová hierarchie 

Doba přístupu k paměti závisí na přítomnosti v cache Obvykle se předpokládá nejlepší možný průběh Speciální problém: Multithreaded aplikace na multiprocesorech

Fetch bandwidth   



skutečné časování

Instrukce nemusí být načteny a dekódovány včas Zdržují skoky a soupeření o přístup do paměti Přesné simulování fetch jednotky by neúměrně komplikovalo scheduler

Scheduler nezná skutečné závislosti přístupů do paměti  

Musí postupovat opatrně a zohledňuje i nejisté závislosti Procesor zná skutečné adresy přístupů a detekuje pouze skutečné závislosti 

Agresivně optimalizující procesor může zvolit zcela jiné pořadí instrukcí


44

Scheduling Model procesoru 

Latence – časování závislých dvojic instrukcí   

Počet cyklů procesoru, který musí proběhnout mezi referenčními body závislých instrukcí U antidependencí a ve speciálních případech může být nulová U procesorů se sekvenčními body může být záporná


45

Scheduling Model procesoru 

Rezervační tabulky – schopnosti paralelního zpracování   

Procesor je rozdělen na funkční jednotky různých druhů Je určen počet jednotek každého druhu Pro každou instrukci definována rezervační tabulka 



Počet jednotek daného druhu, který instrukce potřebuje v daném čase (měřeno od referenčního bodu)

Rezervační tabulky jsou nutné i pro procesory, které nejsou super-skalární


46

Scheduling - pokročilé techniky Loop

unrolling

V cyklech s malým počtem instrukcí

někdy není co paralelizovat Současné zpracování dvou nebo více iterací pomůže Modulo

scheduling, software pipelining


47

Příklad – Intel compiler – x64 char chksum( char * p, int i) { char s = 0; while ( i > 0 ) { s ^= *p++; --i; } return s; }

/*...*/

k = i >> 1; j = 0;

do {

..B1.4: movsbq movsbq xorl xorl addq addl cmpl jb

(%rdi), %r8 1(%rdi), %r9 %r8d, %eax %r9d, %eax $2, %rdi $1, %ecx %edx, %ecx ..B1.4


r8 = *p; r9 = *(p+1); s ^= r8;

s ^= r9; p += 2; j += 1; } while ( j < k );

/* ... */

48

Průchod polymorfní datové struktury - pohled procesoru


49

Kritický kód - Intel C++ 64-bit 

Zdrojový kód

std::for_each( b, e, [&](Fruit * p){ s += p->seeds(); });



Smyčka po inline expanzi

for(; b != e; ++ b) s += (*b)->seeds();



Generovaný strojový kód

.lp:

Registry     

mov

rcx, QWORD PTR [r14]



mov

rax, QWORD PTR [rcx]



call

QWORD PTR [8+rax]

add

r14, 8

add

DWORD PTR [88+rbp], eax

cmp

r14, r13

jne

.lp

 mov

r14 = b r13 = e rcx = * b rax = VTable eax = hodnota f() rbp = stackframe [88+rbp] = s

Skoky 

dobrá predikce 

; Prob 82%

Tělo virtuální funkce seeds eax, DWORD PTR [8+rcx]





ret jne

špatná predikce 

call

ret NPRG054 Vývoj vysoce výkonného software - 2014/2015 David Bednárek

50

Kritický kód - Intel C++ 64-bit 

Zdrojový kód

std::for_each( b, e, [&](Fruit * p){ s += p->seeds(); });



Smyčka po inline expanzi

for(; b != e; ++ b) s += (*b)->seeds();



 

write-read read-write test-access

Restart pipeline

mov


mov


call

QWORD PTR [8+rax]

add

r14, 8

add


cmp

r14, r13

jne

.lp

mov



Generovaný strojový kód

.lp:



Závislosti



Špatně predikovaný skok do virtuální funkce

; Prob 82%

Tělo virtuální funkce seeds eax, DWORD PTR [8+rcx]


51

Kritický kód - Intel C++ 64-bit  mov

eax, DWORD PTR [8+rcx]

ret



Konec smyčky

add

r14, 8

add


cmp

r14, r13

jne

.lp



; Prob 82%

Začátek smyčky

.lp: mov


mov


call

QWORD PTR [8+rax]

 mov



Tělo virtuální funkce seeds

Špatně predikovaný cíl volání eax, DWORD PTR [4+rcx]


Mikrooperace (odhad)

load

eax,[8+rcx]

load

t1,[rsp++]

jmp

t1

add

r14,8

load

t2,[88+rbp]

add

t2,eax

store

[88+rbp],t2

cmp

r14,r13,eflags

jne

.lp,eflags

load

rcx,[r14]

load

rax,[rcx]

load

t3,[8+rax]

store

[--rsp],rip

jmp

t3

load

eax’,[4+rcx]

load

t4,[rsp++]

jmp

t4 52

Odhad provedení kritického kódu s neúspěšnou predikcí 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

fetch+decode 1..3 4 5..7 8..9 10..14 1'..3'

load

1 .2 ..5 .. . 10 . 16 .. . 11 . 1' .. . 12 . 2' .. .


ALU

retire+store

6

eax,[8+rcx]

2: load

t1,[rsp++]

3: jmp

t1

4: add

r14,8

5: load

t2,[88+rbp]

6: add

t2,eax

7: store [88+rbp],t2

4

8

1: load

1 2..4 5 6..9 10

8: cmp

r14,r13,eflags

9: jne

.lp,eflags

10: load rcx,[r14] 11: load rax,[rcx] 12: load t3,[8+rax] 13: store [--rsp],rip

11

14: jmp

t3

1': load eax’,[4+rcx] 2': load t4,[rsp++]

12..14

3': jmp

t4 53

Odhad provedení kritického kódu s úspěšnou predikcí fetch+decode 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 0 1 2 3 4

load 1 .2 ..5 . . 10 .. . 11 . 1’ . . 2’ . .12 . . 5’ . . 10’ .. . 11’ . 1’’ . . 2’’ . . 12’ . . 5’’ . . 10’’


ALU 4 8

6 4’ 8’

retire+store

1 2..4 5 6..9 10

11

1: load

eax,[8+rcx]

2: load

t1,[rsp++]

3: jmp

t1

4: add

r14,8

5: load

t2,[88+rbp]

6: add

t2,eax

7: store [88+rbp],t2 8: cmp

r14,r13,eflags

9: jne

.lp,eflags

10: load rcx,[r14]

6’ 4’’ 8’’

12..14 1’..4’ 5’..8’ 9’-10’ 11’

11: load rax,[rcx] 12: load t3,[8+rax] 13: store [--rsp],rip 14: jmp

t3

54

Výsledky (Intel Core Microarchitecture, 2.66 GHz) 16

14

čas na jeden objekt [ns]

12

10

8

6

4

2

0 50

500

5,000

50,000

500,000

5,000,000

50,000,000

počet objektů polymorfní objekty


polymorfní po skupinách

55

Hodnocení výsledků



Náhodně promíchané objekty 

Neúspěšná predikce skoku 





Zpoždění načítání instrukcí + zátěž spekulativně provedenými instrukcemi

Odhad 20 cyklů = 7.5 ns, měření 9-13 ns (cache misses)

Objekty uspořádané do skupin podle druhu 

Zlepšuje predikci skoků 

 

U malých dat neúčinné – procesor se nestíhá naučit

Zůstává režie nepřímého volání (ověření predikce) - zatěžuje procesor Odhad 8 cyklů = 3 ns, měření 3-8 ns (cache misses)


56

Jiný přístup class Apple {



Bez dědičnosti

int seeds() { return d2; }



int d1, d2, d3;



Volání nebudou nepřímá Překladač volané funkce integruje 

};



class Orange { int seeds() { return d3; } int d1, d2, d3, d4, d5; };



Bez ukazatelů 



Ušetříme 1 přístup do paměti Data jsou těsně vedle sebe

vector< Apple> dataA;



vector< Orange> dataO;



int s = 0; for_each( dataA.begin(), dataA.end(), [&]( Apple & x) { s += x.seeds(); }); for_each( dataO.begin(), dataO.end(), [&]( Orange & x) { s += x.seeds(); }); NPRG054 Vývoj vysoce výkonného software - 2014/2015 David Bednárek

Odpadá režie volání Dovoluje další optimalizace

 

Nulová režie Hardware prefetch

Použitelné pro operace nezávislé na pořadí Pro udržení pořadí je zapotřebí další struktura 

Pro operace závislé na pořadí neušetříme

57


14


12

10

8

6

4

2

0 50

500

5,000

50,000

500,000

5,000,000

50,000,000




nepolymorfní objekty

58

Sloupcově orientovaný přístup vector< int> Ad1, Ad2, Ad3;



vector< int> Od1, Od2, Od3, Od4, Od5;

Uložení po sloupcích  

int s = 0;

Umožňuje použití SIMD instrukcí Čtená data jsou těsně vedle sebe 

Lepší využití cache

for_each( Ad2.begin(), Ad2.end(), [&]( int x) { s += x; }); for_each( Od3.begin(), Od3.end(), [&]( int x) { s += x; });



Nevýhody  

Ignoruje výhody objektového programování (enkapsulace) Data jednoho objektu jsou rozptýlena 




Horší využití cache při náhodném přístupu

Moderní databázové stroje používají sloupcový přístup

59

Sloupcově orientovaný přístup vector< int> Ad1, Ad2, Ad3;



SIMD instrukce 

vector< int> Od1, Od2, Od3, Od4, Od5;

 int s = 0;



for_each( Ad2.begin(), Ad2.end(), [&]( int x) { s += x; });



for_each( Od3.begin(), Od3.end(), [&]( int x) { s += x; });







Použití vyžaduje znalost těchto instrukcí

Problém: zarovnání 

Data pro SIMD instrukci se načítají obvykle atomicky Vyžadují zarovnání větší než obvykle (SSE: 16 B)

Problém: nedělitelné zbytky na koncích polí  


Intel/AMD: MMX/SSE/AVX/... Některé překladače je dokážou vygenerovat samy Jinde existují knihovní funkce skrývající SIMD instrukce

Zvýšená režie cyklu SIMD se nevyplatí pro malá pole 60

Sloupcově orientovaný přístup – SSE3 #include <emmintrin.h> vector< __m128i> Ad1, Ad2, Ad3; std::size_t reserve;



Microsoft VC++/Intel C++ 

Knihovní funkce skrývající SIMD instrukce 



__m128i ss = 0; for_each( Ad2.begin(), Ad2.end() - 1, [&]( __m128i & x) {

Baleny jednotlivě

 

ss = _mm_add_epi32( ss, x);

Překladač je zná a integruje

Překladač sám přiděluje registry Použití vyžaduje znalost těchto instrukcí 

});

jednodušší než programování v assembleru

int s = ss.m128i_i32[ 0] + ss.m128i_i32[ 1]



+ ss.m128i_i32[ 2] + ss.m128i_i32[ 3]; for_each( Ad2.back().m128i_i32, Ad2.back().m128i_i32 + 4 - reserve,

__m128i je 128-bitový typ odpovídající SSE registru 



Překladač (někdy) zajistí zarovnání

_mm_add_epi32 odpovídá SIMD instrukci PADDQ 

4-krát součet 32-bitových čísel

[&]( int x) { s += x; }); NPRG054 Vývoj vysoce výkonného software - 2014/2015 David Bednárek

61


14


12

10

8

6

4

2

0 50

500

5,000

50,000

500,000

5,000,000

50,000,000




nepolymorfní objekty

po sloupcích

62



2

2

1

1

0 50

500

5,000

50,000

500,000

5,000,000

50,000,000

počet objektů nepolymorfní objekty


po sloupcích

63

Shrnutí



Uspořádání objektů podle typu 



Oddělení skladování objektů různých typů  



Zrychlení 4 až 8-krát proti společnému uspořádánému seznamu Navíc šetří paměť (odpadá režie dynamické alokace)

Uložení po sloupcích a použití SIMD instrukcí 



Zrychlení 2 až 4-krát proti náhodně uspořádanému průchodu

Zrychlení 3-krát proti oddělenému skladování

Celkové zrychlení 20 až 60-krát   

Jde o dobře zvolenou jednoduchou úlohu V reálnějších případech to tak dramatické nebude Vše je podmíněno možností změnit pořadí průchodu


64

Nástroje na ladění výkonu


65

Techniky ladění výkonu 

Optimalizovat celý program je zbytečná práce 



Pravidlo 90:10 nebo dokonce 99:1

Cíl 1: Identifikovat hotspot  

Místo v kódu, ve kterém program tráví významnou část celkového času Z logického pohledu hotspot zahrnuje i procedury z něj volané 



Jiný pohled: hotspot je kód, který se provádí mnohokrát 



Při této definici je však největším hotspotem main To ale nemusí znamenat, že se v něm tráví významný čas

Další možnost: hledat kód, který má problém 

Např. mnoho času na jednu instrukci 



Realistický přístup: Neumíme to definovat, ale poznáme to  



Z tohoto pohledu ubrání instrukcí vytváří problém

Programátor má představu, co by mělo být hotspotem Měření může ukázat, že představa byla špatná

Cíl 2: Zjistit, co zdržuje provádění hotspotu 

Detekce/počítání/lokalizace zdržujících událostí


66

Techniky měření chování programu



Instrumentace  



Úprava programu tak, aby se sám změřil Provádí překladač na mezikódu nebo zvláštní nástroj na binárním kódu Měřicí kód významně narušuje běh programu 



Profil: počet průchodů jednotlivými místy v programu   



Má smysl měřit pouze neovlivněné veličiny Základní bloky (přechody mezi nimi) Procedury Procedury včetně vzájemných volání

Optimalizace řízené profilem 

Překladač využívá dříve naměřený profil 



při určení, které části programu optimalizovat při výpočtu ceny u některých optimalizací


67




Sampling  

Pouští se nemodifikovaný program Ve vhodně vybraných okamžicích se zjistí aktuální pozice  

 

IP IP včetně volajících procedur (dešifrování návratových adres ze zásobníku)

Četnost pozic v celkovém seznamu vzorků určuje hotspoty Okamžiky samplování musí být   

Dostatečně řídké, aby neovlivňovaly běh programu Dostatečně husté, aby produkovaly statisticky významná data Známým způsobem korelované s během programu  

Nezávislé - náhodný sampling (aproximace: periodický sampling) Závislé na vybraných událostech (počet provedených instrukcí, přístupů do paměti apod.)


68




Sampling 

Techniky generování událostí 

Softwarové - přerušení časovačem  



Hardwarové - podpora v procesoru  



Vyžaduje častější přerušení než obvyklé nastavení časovače v OS Periodické přerušování nemusí být statisticky nezávislé na běhu programu Procesor generuje interní přerušení po dosažení nastaveného počtu událostí Hodinový signál, instrukce, přístupy do paměti, mispredikce, ...

Techniky záznamu vzorku  

Softwarové - záznam vytváří obsluha přerušení Hardwarové - záznam vytváří procesor zápisem do paměti   

Dovoluje častější vzorkování Nedovoluje zkoumání zásobníku Nedovoluje randomizaci vzorkovací periody


69

Paměťová hierarchie


70

Současné technologie polovodičových pamětí Statická RAM

Dynamická RAM

Flash EPROM

Princip záznamu

Elektrický obvod se dvěma stabilními stavy

Nabitý kondenzátor

Nabitý kondenzátor

Výdrž záznamu

Po dobu napájení

Desítky milisekund

Desítky let

Princip čtení

Měření napětí na výstupu obvodu

Vybití kondenzátoru

Ovlivnění vodivosti elektrickým polem kondenzátoru

Princip zápisu

Změna napětí vstupů obvodu

Nabití kondenzátoru

Nabití/vybití kondenzátoru tunelováním

Tranzistorů na bit

6

1

1/3

Moorův zákon – dvojnásobná kapacita

2 roky

1,5 roku

1,4 roku

Latence

0.5-5 ns dle velikosti

20-30 ns

dle architektury

Moorův zákon – poloviční latence

?

7 let

?


71

Dynamická RAM


72

Architektura paměti DRAM •Otevření řádku • řádkový dekodér

matice kondenzátorů

•

řádkový buffer

sloupcový dekodér

Adresa řádku se dekóduje Hodnota řádku se přenese do řádkového bufferu

•Čtení/zápis • •

Adresa sloupce se dekóduje Bit v řádkovém bufferu se přečte/nastaví

•Zavření řádku • adresa adresa řádku sloupce

data


Hodnota z řádkového bufferu se zapíše do řádku

73

Architektura paměti DRAM •Typické rozměry řádkový dekodér 1:16384

• matice kondenzátorů

• •

16384 řádků 8192 sloupců celkem 128 Mbit

•Typické časy řádkový buffer 8192 bit

•

•

• sloupcový dekodér 32:8192

tRCD = 13 ns tCL = 13 ns •

•

Čtení/zápis

tRP = 13 ns •

adresa adresa řádku sloupce 14 bit 8 bit

Otevření řádku

Zavření řádku

data 32 bit


74

Architektura paměti DRAM – příklad čipu banka 0

banka 1

banka 2

banka 3

banka 4

banka 5

banka 6

banka 7

•Typický • • •

•

čip

matice 128 Mbit 8 bank celkem 1 Gbit 256 M * 4 bit

•Paralelismus • dekodér banky 1:8

•

data 32 bit

• multiplexor 8*4:32

adresa banky 3 bit

řídící signály

• adresa 14 bit

data 4 bit


Banky mohou pracovat nezávisle V okamžiku předávání příkazu, adresy nebo dat je připojena jen jedna Synchronizováno hodinovým signálem – programované zpoždění mezi příkazy a daty Časový multiplex dat 8:1 75

Architektura paměti DRAM - příklad adresy a řízení

data 64 bit

čip 0

čip 1

čip 2

čip 3

•Rank • • čip 4

čip 5

čip 6

čip 7

• •

čip 256 M * 4 bit 16 čipů celkem 2 GB 256 M * 64 bit

•Paralelismus • čip 8

čip 9

čip 10

čip 11

•

Všechny čipy dělají totéž Každý řeší 4 bity

•Doplňky čip 12

čip 13


čip 14

čip 15

•

ECC: +2 čipy – paritní kontrola

76

Architektura paměti DRAM – typický 4GB DDR3 modul výběr adresy data ranku a řízení 64 bit

•DDR3 modul • rank 0

• • • •

dual rank každý rank 256 M * 64 bit celkem 4 GB 32 čipů 512 M * 64 bit

•Paralelismus • •

rank 1

•Doplňky •


Ranky pracují nezávisle Ke sběrnici může přistupovat jen jeden

„registered“: opakovač signálů 77

Architektura paměti DRAM - kanály výběr adresy data ranku a řízení 64 bit

•DDR3 kanál • modul 0

• rank 0

• •

rank 1

modul 1

•Paralelismus •

•

rank 2


Jednotlivé ranky obou modulů pracují nezávisle Data přenáší pouze jeden

•Varianty •

rank 3

dva paralelně propojené moduly každý modul 512 M * 64 bit celkem 8 GB 1 G * 64 bit

•

„registered“: až 4 moduly větší a pomalejší

78

Architektura paměti DRAM – dual channel kanál 0

kanál 1

modul 0

•Dual channel •

modul 2

• rank 0

rank 0

• •

rank 1

modul 1

rank 1

•Paralelismus

modul 3

• rank 2

rank 2

rank 3

rank 3


2 kanály každý kanál 1 G * 64 bit celkem 16 GB 1 G * 128 bit nebo 2 G * 64 bit

•

Kanály dělají totéž nebo Kanály pracují a přenášejí data nezávisle

79

Architektura paměti DRAM – Příklad: 4 * DDR3 4 GB DR x4 •Shrnutí • • • • • •


2 kanály 2*2 = 4 ranky nezávislá činnost 16 čipů shodná činnost 8 bank nezávislá činnost 16384 řádků jeden aktivní 8192 sloupců 32 vybraných

80

Architektura paměti DRAM •Atomická •

• •

•

operace

časový multiplex: 8 přenosů po 64 bitech celkem 512 bitů při 1600 MT/s zaměstná 1 kanál na 5 ns latence 26 ns, s úklidem 52 ns

•Paralelismus •

•

•


Zbývajících 31 bank kanálu může dělat něco jiného Propustnost kanálu stačí na 200 M operací/s Kanály jsou dva (až 4) 81

Rozhraní procesor - DRAM



Přímé připojení na DDR3 



Intel DMI, QPI, AMD HyperTransport 



Serio-paralelní rozhraní, různé šířky, až 25.6 GB/s

Intel FSB 



1-4 kanály po 64 bitech, každý až 1600 MT/s = 12.8 GB/s

1 kanál, 64 bitů, až 1600 MT/s = 12.8 GB/s

Komplikovanost rozhraní procesor – DRAM prodlužuje latenci 

celkem řádově 50 ns, samotná DRAM typicky 25 ns


82

Statická RAM


83

Architektura paměti SRAM •Řádky a sloupce • řádkový dekodér

matice klopných obvodů

•Čtení • •

sloupcový dekodér

data


Celý řádek vysílá své hodnoty Sloupcový dekodér vybírá data

•Zápis •

adresa adresa řádku sloupce

Aktivace probíhá současně

Sloupcový dekodér posílá signály „zapiš 0“ a „zapiš 1“ do vybraných sloupců

84

Architektura paměti SRAM •Banky •

Velké paměti jsou děleny na banky

•Paralelismus •

•

Operace v různých bankách se mohou překrývat V jednom cyklu lze zahájit pouze jednu operaci •

adresa banky

adresa řádku a sloupce

data


Společné sběrnice a dekodér banky brání plnému paralelismu

85

Architektura paměti SRAM •Dvoubránová

paměť •

V každé buňce je zdvojeno její vnější rozhraní •

•

Přístup ze dvou bran je zcela nezávislý •

•

Současný zápis různých hodnot do téže buňky je nežádoucí

Používá se pro malé výkonově kritické paměti •


cca 33% plochy navíc

registry, TLB 86

Asociativní paměť


87

Asociativní paměť tag

data

•Plně asociativní

paměť

=

•

= =

•

= =

Každý řádek má svůj komparátor Vyžaduje strategii výměny při zaplnění

•Drahá

= =

•

=

nejvýše desítky řádků •

tag


TLB1

data

88

Asociativní paměť •Přímo mapovaná

asociativní paměť

SRAM

• • •

•

=

Základem běžná paměť (SRAM) Společný komparátor Nevyžaduje strategii výměny při zaplnění Umožňuje číst data ještě před dokončením porovnání

•Prakticky

nepoužitelná • index

tag


data

Kolize jsou v reálných aplikacích příliš pravděpodobné 89

Asociativní paměť •N-cestně SRAM

asociativní paměť •

= SRAM

•

•Převládající

=

způsob implementace cache

SRAM

•

=

index

Přímo mapovaná asociativní paměť je použita N-krát Vyžaduje strategii výměny při zaplnění

tag


N mírně roste s velikostí cache

data 90

Cache poslední úrovně 

LLC = L2 nebo L3  

Obvykle společná pro všechna/některá jádra na čipu Typické velikosti 4-16 MB 



Cache Line = 512, někdy 1024 bitů 

  



Stupeň asociativity 8-16 Obvykle odpovídá velikosti atomické operace DDR3 DRAM

Latence kolem 10 ns Komunikace LLC – DRAM – vždy celá Cache Line Komunikace s nižšími úrovněmi – obvykle 128 nebo 256 bitů najednou

Paralelismus 

Celý proces přístupu do cache je pipeline 



lze zahájit 1 přístup každé 1-3 cykly procesoru

Cache může být dělena na banky 

přístup do různých bank může být paralelní


91

Cache prostřední úrovně



L2 v systémech s L3 

   

Každé jádro mívá vlastní Typické velikosti 256 KB - 4 MB Cache Line téměř vždy 512 bitů Latence 5-10 ns Komunikace s okolními úrovněmi – obvykle 128 nebo 256 bitů najednou


92

Cache první úrovně 

L1D  

Pouze pro data (instrukce mají vlastní L1I cache) Každé jádro má vlastní 

   





Systém musí řešit přístup k datům v L1 cache sousedního jádra

Typické velikosti 16-64 KB Cache Line téměř vždy 512 bitů Latence 1-2 ns Komunikace s vyšší úrovní – obvykle 128 nebo 256 bitů najednou Komunikace s jádrem – podle šířky operandu instrukce (8 až 128 bitů)

Paralelismus 

Celý proces přístupu do cache je pipeline 



v každém cyklu může začít nový přístup

Cache může mít více bran  

v každém cyklu mohou začít dva přístupy, pokud vedou na jiné adresy komunikace s vyšší úrovní běží na pozadí (eject, prefetch)


93

TLB 

Překlad virtuálních adres na fyzické 

Často dvě úrovně TLB 

DTLB1 pouze pro data, 16-64 záznamů 







L1D bývá „virtually-indexed-physically-tagged“

Latence TLB2 v řádu 2-3 ns Není-li záznam v TLB:  



TLB2 společná, cca. 512 záznamů

Latence DTLB1 bývá započtena do latence L1D 



odpovídá 64-256 KB adresového prostoru

„page walk“ - procesor realizuje 2-4 přístupy do paměti (cache) „page fault“ – řeší operační systém

Paralelismus  

TLB bývá vícebránová – obsluhuje čtení i zápisy paralelně Virtually-indexed cache   

L1 cache indexována virtuální adresou (nebo ofsetem uvnitř stránky) Překlad v TLB může běžet paralelně s adresací L1 cache Vyžaduje speciální opatření pro případ násobného mapování téže fyzické adresy


94

Typické použití bitů adresy (Intel Sandy Bridge) bit

47-40

39-24

23 22 21 20 19 18 17 16 15 14 13 12 11 10

9

8

7

6

5

4

3

2

1

0

virtuální adresa tag DTLB1

index assoc tag

TLB2

index assoc

fyzická adresa tag L1D

index assoc tag

L2

index assoc tag

L3

index assoc

velikost

256 TB

1 TB

16 MB


1 MB

64 KB

4 KB

64 B

95

Typická latence a propustnost – Intel Sandy Bridge latence (cykly)

A L U

operací/ cyklus

B/operace

B/cyklus

GB/s [3 GHz CPU]

registry

0 (započteno teoreticky 4-16 v čase 14, prakticky instrukce) 3-6

až 112 SIMD až 160

teoreticky 480

L1D

4

3 (2*R+1*W) 4-16

12-48

36-144

L2

12

1

32

32

96

L3

26-31

1

32

32

96

2/15

64

8.5

25.6

DDR3-1600 cca 120 dual channel

reg L1

L2

L3


DRAM 96

Typická latence a propustnost – Intel Sandy Bridge Quad Core

A L U

A L U

A L U

A L U reg L1

L2

L3


DRAM 97

Důsledky pro programování 

Velikosti, latence a architektury cache jsou různé  

Spolehlivě lze odhadnout pouze dolní mez L1 (16KB) Ladit software na přesné velikosti všech úrovní je téměř nerealizovatelné  



Velikost Cache Line lze odhadnout spolehlivě – 64B 

Přesunovat do procesoru méně než 64B je plýtvání 



autotuning, NUMA awareness cache-oblivious algoritmy

spojové seznamy či stromy s malými uzly jsou neefektivní

Velikost TLB1 je velmi malá 

Přístup na větší počet míst paměti je problematický pro TLB, ne pro L1  

L1 udrží stovky živých míst, TLB pouze desítky Bucket-sort nebo merge může být TLB-bound 



více než 64 živých bodů vzdálených od sebe více než 4 KB

Bloky dynamicky alokovaných dat mohou být velmi vzdálené 

100-prvkový vyhledávací strom se nemusí vejít do DTLB1


98

Nešikovně naprogramovaný kód může dobrý překladač napravit Nevhodnou datovou strukturu překladač nenapraví (a nepomůže ani naprogramování v asembleru)


99

Úrovně cache 

Registry poskytují cache úrovně 0 

Použítí této „cache“ řídí překladač 

 

Velikost řádky je velikost registru (podle řešené úlohy; SIMD: 128/256 bit) Velikost “L0-cache” dána počtem registrů (Intel: 8/16, některé obsazené)  





32 až 512 B Pro danou úlohu a platformu programátor dokáže určit

Lze programovat na míru (týká se jádra algoritmu)

Velikost řádku Cache je stabilní - 64B 



Programátor může vytvořit šanci nebo zlepšit podmínky úpravou kódu

Lze programovat na míru (týká se zejména datových struktur)

V intervalu 4KB-16MB leží mnoho hranic důležitých velikostí   

Bez znalosti konkrétní varianty CPU nelze určit přesnou polohu hranic Každé zdvojnásobení velikosti úlohy může dramaticky změnit poměry Nejvhodnější je přístup převzatý z Cache-Oblivious algoritmů 

Rekurzivní dělení úlohy na části


100

Cache-oblivious algorithms


101




Cache-awareness  



Cache-obliviousness 



Algoritmus je vyladěn pro konkrétní parametry cache Prakticky obtížně proveditelné - parametrů je příliš mnoho

Víme, že cache existuje, ale neznáme její parametry

Cache-oblivious algorithms  

Pohled na složitost algoritmů zohledňující existenci cache Algoritmy fungující z tohoto pohledu dobře


102

Cache-oblivious algorithms (zjednodušený pohled) 

Cache-oblivious algorithms [1999] 

Pohled na složitost algoritmů zohledňující existenci cache  

Počítáme přístupy k hlavní paměti (cache misses) Složitost je funkcí velikosti vstupu (n) a velikosti cache (C) 



Zkoumá se obvykle asymptotické chování 



O(f(n,C))

Pro většinu algoritmů je asymptotické chování úměrné časové složitosti (t(n))   



Zjednodušeno (parametrem bývá i velikost cache line)

O(f(n,C)) = O(t(n)*g(C)) g(C) říká, jak často algoritmus generuje cache miss obvykle g(C) < 1 a klesá s velikostí C

Příklad: Násobení matic (n*n) 

Učebnicový algoritmus (i-j-k iterace)  



Pro n2>C každý přístup (k pravému operandu) generuje cache miss O(n3) - nezávisí na C; g(C) = 1

Cache-oblivious algoritmus (rekurzivní dělení) 

O(C-1/2 *n3) tj. g(C) = C-1/2


103

Cache-oblivious algorithms 


Pohled na složitost algoritmů zohledňující existenci cache  



Počítáme přístupy k hlavní paměti (cache misses) Předpokládáme pouze 1 úroveň cache

Který algoritmus je lepší? 

Minimalizujeme g(C) pro všechna C (nikoliv asymptotické chování) 





Dobré chování pro cache jakékoliv velikosti implikuje dobré chování pro více úrovní

Stále jde o asymptotický pohled vzhledem k n 

Zanedbáváme multiplikativní konstanty, neřešíme rozdíl čtení/zápis  



Pro reálné problémy může být výhodnější asymptoticky horší algoritmus Práce s pamětí nemusí být kritické místo algoritmu

Zanedbané konstanty často výrazně zkreslují chování pro malá C  



To není jednoznačné zadání, ale porovnání obvyklých g jednoznačné bývá (např. C-1/2 < 1)

Jádro algoritmu bývá vhodnější implementovat s přibližnou znalostí chování L1 cache Překladač obvykle neumí sám využít registry jako L0 cache

Jako inspirace se vždy vyplatí


104




Rozděl a panuj  

Problém P0 se dělí na podproblémy P1 a P2 Pamětová složitost: m0 < m1 + m2 



Pro m0 > C se problém P0 do cache nevejde 



Část dat D12 je používána oběma podproblémy: |D12| = d12 = m1 + m2 - m0 Část dat D12 pravděpodobně bude čtena pro P2 znovu z hlavní paměti

Počítání přístupů do hlavní paměti (výpadků cache) 

Každý podproblém musí alespoň jednou načíst/zapsat svá data 



První přístup nebudeme počítat

Vrstva P0 přispěje druhým čtením D12 o velikosti d12


105

Násobení matic - rozděl a panuj

 

C = A * B, velikosti A[i,k], B[k,j], C[i,j] i-split - dělení problému v dimenzi i   

i0 = i1 + i2 ; j0 = j1 = j2 ; k0 = k1 = k2 Matice A a C se dělí napůl - podproblémy jsou na nich disjunktní Matice B se nedělí - oba podproblémy ji používají celou: d12 = k0 * j0 



j-split a k-split - další možnosti dělení 



Matice B se pro velká data čte z hlavní paměti opakovaně

Jiný příspěvek d12 a jiné rozměry podúloh

Končíme u velikosti m0 = i0*k0 + j0*k0 + i0*j0 < C 

Pod touto velikostí je z hlediska opakovaných výpadků cache cena 0


106


Normalizace  

Časová složitost: t0 = t1 + t2 Počítáme g(C) 

 



počet (druhých a dalších) přístupů do hlavní paměti na jednotku času

g0 (C) = d12/t0 + g1(C) * t1/t0 + g2(C) * t2/t0 pro m0 > C g0 (C) = 0 pro m0 < C

Násobení matic - i-split   



i0 = i1 + i2 ; j0 = j1 = j2 ; k0 = k1 = k2 d12 = k0 * j0 Časová složitost t0 = i0*j0*k0 ; t1 = i1*j0*k0 ; t2 = i2*j0*k0 Normalizovaný počet opakovaných přístupů k hlavní paměti 



g0 (C) = 1/i0 + g1(C) * i1/i0 + g2(C) * i2/i0

Při dělení napůl i1 = i2 ; g1(C) = g2(C) 

g0 (C) = 1/i0 + g1(C)


107

Násobení matic - rozděl a panuj 

Rekurzivní kroky  





i-split: gi,j,k (C) = 1/i + g i/2,j,k(C) j-split: gi,j,k (C) = 1/j + g i,j/2,k(C) k-split: gi,j,k (C) = 1/k + g i,j,k/2(C)

Končíme u velikosti iF*kF + jF*kF + iF*jF < C  

Rozhoduje součin dvou největších rozměrů Pro dané počáteční a zvolené koncové 

Cena rekurzivního sestupu nezávisí na cestě:  

 



gS(C) = 1/iS +...+ 1/iF + 1/jS +...+ 1/2jF + 1/kS +...+ 1/2kF 1/2iF + 1/2jF + 1/2kF < gS(C) < 1/iF + 1/jF + 1/kF

Nejlevnější je sestup do koncového bodu se shodnými dvěma největšími rozměry Nejmenší rozměr koncového bodu má být co největší

Nejlepší koncový bod pro iS > jS > kS    

iF = jF = kF = C1/2 pro kS > C1/2 ; cena gS(C) = O(C-1/2) iF = jF = C1/2 ; kF = kS pro jS > C1/2 > kS ; cena gS(C) = O(C-1/2) iF = C / js ; jF = jS ; kF = kS pro iS > C1/2 > jS ; cena gS(C) = O(js /C) iF = is ; jF = jS ; kF = kS pro C > iS * jS ; cena gS(C) = 0


108

Násobení matic - cache-aware 





Cache-aware algoritmus - pokud známe velikost cache C  

Zvolíme koncový bod (objem dat spolehlivě pod velikostí C) Ke koncovému bodu sestoupíme iterací přes ty rozměry, které přesahují C1/2 

Iterace odpovídá několika sestupům stejným druhem splitu 



Na pořadí vzájemného vnoření iterací teoreticky nezáleží 



Režie rekurze je větší než režie iterace Prakticky na vnoření záleží (cache line, prefetch, čtení/zápisy,...)

Předpokládaná normalizovaná cena gS(C) = O(C-1/2) nebo menší 

32 KB L1 cache & 8 B double: C = 4096; C-1/2 = 1/64 

"jeden" (O(1)) přístup k L2 cache na 64 ALU operací


109

Násobení matic - cache-oblivious







Cache-oblivious algoritmus - připravenost na libovolné C 

Split se provádí v rozměru, který je největší   

Nejprve dosáhne stavu, kdy jsou dva větší rozměry shodné Následuje střídání splitů v těchto dvou rozměrech Po dosažení shody všech rozměrů střídání všech tří splitů 



Strassenova algebraická finta: Místo tří splitů dělení na 7 podúloh

Celkový počet výpadků cache je O(C-1/2 *i*j*k)


110

Cache-oblivious algorithms – vliv bloků



Zjednodušená složitost uvažuje pouze velikost cache C 



Výsledek nezávisí na způsobu uložení dat v pamětí

Úplná cache-aware složitost uvažuje i velikost bloku B 

 

Blokem je řádka cache případně stránka vzhledem k TLB

f(C,B) Počítají se přesuny bloků mezi cache a hlavní pamětí 

Lepší paměťová struktura jich spotřebuje méně


111

Cache-oblivious algorithms – vliv bloků 

Příklad: Násobení matic (n*n) 

Učebnicový algoritmus (i-j-k iterace), uložení po řádcích    



Pro n>C každý přístup (k pravému operandu) generuje cache miss f(C,B) = O(n3) - nezávisí na C; g(C) = 1 Při uložení po sloupcích zdržuje přístup k levému operandu Při uložení po čtvercích B1/2 * B1/2 se složitost zlepší na O(B-1/2 * n3)

Cache-oblivious algoritmus (rekurzivní dělení, rekurzivní uložení) 

O(C-1/2 *B-1*n3) tj. g(C) = C-1/2*B-1



Typické hodnoty konstant (neřešíme společnou multiplikativní konstantu)       

8 registrů, double: C = 8, B = 1, g(C) = 1/2.8, jednotková cena 1/3 cyklu CPU 8 SSE registrů, double: C = 16, B = 2, g(C) = 1/8 32KB L1 cache, double: C = 4K, B = 8, g(C) = 1/512, jednotková cena 1 cyklus CPU 64-entry TLB, double: C = 64, B = 512, g(C) = 1/4K 8MB L3 cache, double: C = 1M, B = 8, g(C) = 1/8K, jednotková cena 8 cyklů CPU 8 GB RAM, 64 KB blok, double: C = 1G, B = 8K, g(C) = 1/256M, jednotka 300K cyklů (SSD) 512 GB SSD, 64 KB blok, double: C = 64G, B = 8K, g(C) = 1/4G, jednotka cca 2M cyklů (HDD)


112

Nejvýznamnější cache-oblivious algoritmy 

Násobení matic  



Transpozice matice 



O(1+(n/B)(1+log(n)/log(C)))

Funnelsort 



O(1+mn/B)

FFT 



O(1+n2/B+n3C1/2/B) Strassen: nlog2(7)

O(1+(n/B)(1+log(n)/log(C)))

Binární vyhledávací stromy (van Emde Boas) 

O(log(n)/log(B)) pro C << n


113

Cache-oblivious algoritmy



Otázky spojené s cache-oblivious algoritmy 

Ignorujeme strategii výměny cache 



Ignorujeme vícevrstevnost cache hierarchie 



Nevadí: LRU se nechová hůře než ideální cache poloviční velikosti Nevadí, pro inkluzivní cache se každá vrstva chová stejně, jako by byla samostatná

Ignorujeme nedokonalou asociativitu cache  

Teoreticky: Náhrada cache hashovací tabulkou s dobrou hashovací funkcí složitost nezhorší Prakticky: Nedokonalost hashovací funkce vadí 

Často jde o triviální funkce vyřezávající bity z adresy


114

Ideální algoritmus 

Celková architektura „ideálního algoritmu“ 

Jádro úlohy pracující v registrech (podúloha velikosti 32-512 B) 

 



Pouze lokální proměnné, pokud možno žádné pole Proměnné čteny z paměti na začátku/zapisovány do paměti na konci V ideálním případě SIMD instrukce

Podúlohy do velikosti 8-16KB  

Data se vejdou do L1 Data podúlohy mohou být v paměti mírně nesouvislá  



Podúloha řešena iterativně nad jádrem úlohy  



Každý blok násobkem 64 B (cache line) Jsou-li bloky vzdálenější než 4 KB, pak nejvýše 32 bloků (TLB1) Rekurzivní řešení mívá příliš velký overhead Iterace umožňuje prefetch

Úlohy větší než 16 KB 

Řešeny rekurzivně metodami Cache-Oblivious algoritmů    



Obvykle se dělí na dvě podúlohy o polovičním počtu operací Každá podúloha má větší než poloviční spotřebu paměti Vybírá se takový způsob dělení, který minimalizuje paměťový překryv podůloh Okolo 16 KB se rekurze nahradí iterací podúlohy

Data každé podúlohy by měla mít malý počet bloků (problém TLB)


115

Jiný pohled na cache


116

Algoritmy a cache 

Přístupy do paměti v algoritmech jsou dvou druhů 

S předvídatelnou adresou 

Lineární průchody polem

for ( i = 0; i < N; ++ i ) { /*...*/ a[ i] /*...*/ } 

Lineární průchody s větším skokem

for ( j = 0; j < M; ++ j ) for ( i = 0; i < N; ++ i ) { /*...*/ a[ i][ j] /*...*/ }



S "náhodnou" adresou 

Hashovací tabulky

for ( i = 0; i < N; ++ i ) { /*...*/ a[ hash( d[ i])] /*...*/ } 

Bucket-sort

for ( i = 0; i < N; ++ i ) { /*...*/ a[ b[ i]] /*...*/ } 

Binární vyhledávání

while ( /*...*/ ) { if ( a[ j] > /*...*/ ) j = /*...*/; else j = /*...*/; } 

Spojové struktury

while ( p != 0 ) { /*...*/ p = p->next; /*...*/ }


117


Přístupy s předvídatelnou adresou   

Efekt řádku cache: Husté lineární průchody mají dobré hit ratio Write buffers: Zápisy obvykle nezdržují Hardware prefetching 



procesor detekuje lineární průchody a načítá data do L1 předem

Software prefetching 

překladač generuje instrukce pro přístup k datům předem  



totéž může udělat programátor ručně 

 

běžné instrukce pro čtení - vyžadují jistotu příští iterace speciální instrukce pro spekulativní čtení - potlačené výjimky

u dnešních procesorů/překladačů nebývá zapotřebí

Latence přístupu se skryje paralelním vykonáváním jiné užitečné činnosti Rozhoduje prostupnost sběrnic paměť-cache-ALU (bandwidth) 

Algoritmy se optimalizují na nejlepší využití dané prostupnosti


118


Přístupy s "náhodnou" adresou 

Adresa nezávislá na předchozí iteraci 

Latenci přístupu lze skrýt paralelizací 



Někdy to dokáže sám překladač

Hashovací tabulky

for ( i = 0; i < N-1; ++ i ) { x = hash( d[ i+1]); /*...*/ v /*...*/; v = a[ x]; } 

Bucket-sort

for ( i = 0; i < N; i += 2 ) { /*...*/ a[ b[ i]] /*...*/ a[ b[ i+1]] /*...*/ }



Adresa závislá na předchozí iteraci (loop-carried dependence)  



Paralelizovat není s čím Rozhoduje latence přístupu Binární vyhledávání

while ( /*...*/ ) { if ( a[ j] > /*...*/ ) j = /*...*/; else j = /*...*/; } 

Spojové struktury

while ( p != 0 ) { /*...*/ p = p->next; /*...*/ }


119


Adresa závislá na předchozí iteraci (loop-carried dependence)  

Paralelizovat není s čím Vyžaduje globální úpravu algoritmu (změny rozhraní funkcí) 

Výměna vzájemné vnořenosti cyklů 

loop reversal; obecněji afinní transformace cyklů (loop skewing)



Vyžaduje stabilní počet iterací vnitřního cyklu



Binární vyhledávání

for ( i = 0; i < N; ++ i ) bsearch( a, M, b[ i]); 

upraveno na

bsearch_many( a, M, b, N);



U nevhodných datových struktur paralelizovat nelze 



Překážkou je nevyváženost počtu iterací

Paralelizace zhoršuje lokalitu přístupů do paměti 

Skrytí latence za cenu sníženého cache hit ratio


120

Loop reversal 

Původní průchod 

Většina sousedů v průchodu je závislá

J

K NPRG054 Vývoj vysoce výkonného software - 2014/2015 David Bednárek

121

Loop reversal 

Upravený průchod 

Většina sousedů v průchodu je nezávislá

J


122

Loop skewing 

Obecnější příklad

for J:=1 to N do



for K:=N-J to P do



A[J,K]:=A[J-1,K]+A[J,K-1]





J


123

Loop skewing 

Obecnější příklad

for J:=1 to N do



for K:=N-J to P do



A[J,K]:=A[J-1,K]+A[J,K-1]





J


124

“Paralelní” bsearch for ( i = 0; i < N; ++ i )

bsearch_many( a, M, b, N);

bsearch( a, M, b[ i]); void bsearch_many( a, M, b, N) void bsearch( a, M, x)

{

{

while ( /*???*/ ) while ( /*...*/ )

for ( i = 0; i < N; ++ i )

{

{ if ( a[ j] > x )

if ( a[ j[ i]] > b[ i] )

j = /*...*/;

j[ i] = /*...*/;

else

else j = /*...*/;

j[ i] = /*...*/;

} }


} }

125

Algoritmy a cache - další pohled 

Přístup na náhodné adresy 

Schopnost přístupu na náhodné adresy je pro algoritmus klíčová 



bsearch, hash,...

Nalezení příslušné buňky paměti je součástí užitečného výkonu algoritmu 

Program vykonává užitečnou práci pomocí adresních dekodérů paměti  



Adresní dekodéry jsou v paměti pořád - zaměstnejme je! Paměť má nezávisle pracující bloky - zaměstnejme je paralelně

Přístup na předvídatelné adresy 

Předvídatelný (lineární) přístup nevyužívá schopnosti RAM 

Adresní dekodéry opakovaně dekódují podobné adresy 



Architektura RAM stroje je pro takové algoritmy nadbytečná 



Zbytečný hardware, zbytečná spotřeba energie

Běžné programovací jazyky jsou této architektuře podřízeny

Vystačili bychom s Turingovskou páskou  

Neumíme ji fyzicky realizovat Neumíme v tomto prostředí programovat


126

2016 David Bednárek

Recommend Documents