Vývoj vysoce výkonného software

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

Vývoj vysoce výkonného software


O čem to bude

3

O čem to bude

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

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


O čem to nebude

O čem to nebude


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

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 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í



Proč?

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


matrix_

zero 128

matrix_

zero 256

matrix_

zero 512

matrix_

zero 1024

matrix_

random 128

matrix_

random 256

matrix_

random 512

matrix_

random 1024

matrix_

one 128

matrix_

one 256

matrix_

one 512

matrix_

one 1024

0.001

0.01

0.1

1

10

100

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


128 zeros 128 random

128 ones 256 zeros 256 random

256 ones 512 zeros 512 random

512 ones 1024 zeros

1024 random

1024 ones

2048 zeros

2048 random

2048 ones

1

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;

12

class Fruit {

...

virtual int seeds() = 0;

};

class Apple : public class Fruit {

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

...

};

class Orange : public class Fruit {

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

...

};

vector< Fruit *> data;

Klasické objektové řešení Abstraktní třída s virtuální funkcí Konkrétní třídy

Různá data Různé implementace virtuální

funkce Kontejner

Obsahuje ukazatele na abstraktní třídu

Toto řešení existuje ve všech objektových jazycích V jazyzích s referenční semantikou

jsou ukazatele skryté

List< Fruit> data;



13

class Fruit {

virtual int seeds() = 0;

};

class Apple : public class Fruit {

virtual int seeds() { return d2; }

int d1, d2, d3;

};

class Orange : public class Fruit {

virtual int seeds() { return d3; }

int d1, d2, d3, d4, d5;

};

vector< Fruit *> data;

int s = 0;

for_each( data.begin(), data.end(),

[&]( Fruit * p) { s += p->seeds(); });

Jak je to rychlé?

Testovací data 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

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



14

void test()

{

int s = 0;

for_each( data.begin(), data.end(),

[&]( Fruit * p) { s += p->seeds(); });

}

generate_data();

test(); // cold run

time_before = now();

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

test();

time_after = now();

cout << (time_after - time_before) / N;

Testovací prostředí Test je opakován N-krát N je voleno tak, aby celkový čas

byl přiměřený V našem testu sekundy

Program si měří čas sám Ve standardu C++ vhodná funkce

now() není Plaformy nabízejí různé možnosti

Ty lepší jsou pouze pro privilegované V našem testu měříme "wall

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



Výsledky testu 1 000 000 objektů

Celkem 10,4 ms 10,4 ns na objekt

1 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ů

Hardware Intel Core2Quad Q6700 2,66 GHz 4 GB RAM

Operační systém Windows 7 64-bit

64-bitový kód

Překladače MS Visual C++ 2010 MS Visual C++ 2012 Intel Composer XE 2013 Rozdíly menší než 5%

Výsledky


64-bitový kód (Intel-64) 1 000 000 objektů



Ukazatele jsou delší 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...

32-bitový kód (IA-32) 1 000 000 objektů



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


64-bitový kód (Intel-64) 1 000 000 objektů náhodně

10,4 ns na objekt 1 000 objektů náhodně

9,0 ns na objekt

1 000 000 objektů round-robin 8,0 ns na objekt

1 000 objektů round-robin 2,6 ns na objekt

1 000 000 objektů skupinově 7,6 ns na objekt

1 000 objektů skupinově 2,8 ns na objekt

32-bitový kód (IA-32) 1 000 000 objektů náhodně

10,7 ns na objekt 1 000 objektů náhodně

10,0 ns na objekt

1 000 000 objektů round-robin 5,9 ns na objekt

1 000 objektů round-robin 2,2 ns na objekt

1 000 000 objektů skupinově 5,3 ns na objekt

1 000 objektů skupinově 2,6 ns na objekt

Výsledky - závislost na distribuci dat


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

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


Vývoj procesorů

21Bill Dally, nVidia at HiPEAC 2015










Typické mikroarchitektury procesorů (2000-2012)

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


Intel Netburst Microarchitecture [2000]

32


Intel NetBurst Microarchitecture [2000]

33


Intel Core Microarchitecture Pipeline [2006]

34


Intel Core Microarchitecture

35

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)


Intel Core Microarchitecture

36

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

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 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


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


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


Závislosti

Závislost (dependence) Povinnost provést jednu operaci/instrukci po jiné Částečné uspořádání operací/instrukcí v jednom BB

Datová závislost (dependence) 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


Scheduling

Scheduling pouze odhaduje skutečné časování 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 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í


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á


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í


Scheduling - pokročilé techniky

Loop unrollingV cyklech s malým počtem instrukcí někdy není co paralelizovatSoučasné zpracování dvou nebo více iterací pomůže

Modulo scheduling, software pipelining


Příklad – Intel compiler – x64

/*...*/

k = i >> 1;

j = 0;

do {

r8 = *p;

r9 = *(p+1);

s ^= r8;

s ^= r9;

p += 2;

j += 1;

} while ( j < k );

/* ... */

char chksum( char * p, int i){ char s = 0; while ( i > 0 ) { s ^= *p++; --i; } return s;}

..B1.4: movsbq (%rdi), %r8

movsbq 1(%rdi), %r9xorl %r8d, %eax

xorl %r9d, %eaxaddq $2, %rdiaddl $1, %ecxcmpl %edx, %ecxjb ..B1.4


Průchod polymorfní datové struktury - pohled procesoru


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

Skoky dobrá predikce

ret jne

špatná predikce call

Zdrojový kódstd::for_each( b, e, [&](Fruit * p){ s += p->seeds(); });

Smyčka po inline expanzifor(; b != e; ++ b) s += (*b)->seeds();

Generovaný strojový kód.lp:

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 ; Prob 82%

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

ret

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


Závislosti write-read read-write test-access

Restart pipeline Špatně

predikovaný skok do virtuální funkce

Zdrojový kódstd::for_each( b, e, [&](Fruit * p){ s += p->seeds(); });

Smyčka po inline expanzifor(; b != e; ++ b) s += (*b)->seeds();

Generovaný strojový kód.lp:




add r14, 8


cmp r14, r13

jne .lp ; Prob 82%


ret




ret

Konec smyčkyadd r14, 8


cmp r14, r13

jne .lp ; Prob 82%

Začátek smyčky.lp:




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

ret

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



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: cmpr14,r13,eflags

9: jne .lp,eflags

10: load rcx,[r14]

11: load rax,[rcx]

12: load t3,[8+rax]

13: store [--rsp],rip

14: jmp t3

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

2': load t4,[rsp++]

3': jmp t4

fetch+decode load ALU retire+store0 1..31 42 5..73 8..94 10..145 1'..3'6 17 . 2 48 . . 59 . . 8 1

10 . 10 2..411 . 16 6 512 . . 6..913 . 11 1014 . 1'15 . .16 . 12 1117 . 2'18 . .19 . 12..14

Odhad provedení kritického kódu s neúspěšnou predikcí

53


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: cmpr14,r13,eflags

9: jne .lp,eflags

10: load rcx,[r14]

11: load rax,[rcx]

12: load t3,[8+rax]

13: store [--rsp],rip

14: jmp t3

fetch+decode load ALU retire+store0 1 41 . 2 82 . . 53 . . 10 14 . . 2..45 . 6 56 11 6..90 . 1’ 4’ 101 . . 2’ 8’2 . .12 113 . . 5’4 . . 10’5 .. 12..146 . 6’ 1’..4’7 11’ 5’..8’0 . 1’’ 4’’ 9’-10’1 . . 2’’ 8’’2 . . 12’ 11’3 . . 5’’4 . . 10’’

Odhad provedení kritického kódu s úspěšnou predikcí

54


Výsledky (Intel Core Microarchitecture, 2.66 GHz)

55

50 500 5,000 50,000 500,000 5,000,000 50,000,000 500,000,0000

2

4

6

8

10

12

14

16

polymorfní objekty polymorfní po skupinách

počet objektů

čas n

a je

den

obje

kt [n

s]


Hodnocení výsledků

56

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)


class Apple {

int seeds() { return d2; }

int d1, d2, d3;

};

class Orange {

int seeds() { return d3; }

int d1, d2, d3, d4, d5;

};

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(); });

Bez dědičnosti Volání nebudou nepřímá Překladač volané funkce integruje

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

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

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

Jiný přístup

57



58

50 500 5,000 50,000 500,000 5,000,000 50,000,000 500,000,0000

2

4

6

8

10

12

14

16

polymorfní objekty polymorfní po skupinách nepolymorfní objekty

počet objektů

čas n

a je

den

obje

kt [n

s]


vector< int> Ad1, Ad2, Ad3;

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; });

Uložení po sloupcích Umožňuje použití SIMD instrukcí Čtená data jsou těsně vedle sebe

Lepší využití cache

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

Sloupcově orientovaný přístup

59


vector< int> Ad1, Ad2, Ad3;

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; });

SIMD instrukce Intel/AMD: MMX/SSE/AVX/... Některé překladače je dokážou

vygenerovat samy Jinde existují knihovní funkce skrývající

SIMD instrukce 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í Zvýšená režie cyklu SIMD se nevyplatí pro malá pole

Sloupcově orientovaný přístup

60


#include <emmintrin.h>

vector< __m128i> Ad1, Ad2, Ad3;

std::size_t reserve;

__m128i ss = 0;

for_each( Ad2.begin(), Ad2.end() - 1,

[&]( __m128i & x) {

ss = _mm_add_epi32( ss, x);

});

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,

[&]( int x) { s += x; });

Microsoft VC++/Intel C++ Knihovní funkce skrývající SIMD

instrukce Baleny jednotlivě

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

__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

Sloupcově orientovaný přístup – SSE3

61



62

50 500 5,000 50,000 500,000 5,000,000 50,000,000 500,000,0000

2

4

6

8

10

12

14

16

polymorfní objekty polymorfní po skupinách nepolymorfní objekty po sloupcích

počet objektů

čas n

a je

den

obje

kt [n

s]



63

50 500 5,000 50,000 500,000 5,000,000 50,000,000 500,000,0000

1

2

3

nepolymorfní objekty po sloupcích

počet objektů

čas n

a je

den

obje

kt [n

s]


Shrnutí

64

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

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í 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


Nástroje na ladění výkonu


Techniky ladění výkonu

66

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é

Při této definici je však největším hotspotem main Jiný pohled: hotspot je kód, který se provádí mnohokrát

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 Z tohoto pohledu ubrání instrukcí vytváří problém

Realistický přístup: Neumíme to definovat, ale poznáme to 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í


Techniky měření chování programu

67

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

Má smysl měřit pouze neovlivněné veličiny Profil: počet průchodů jednotlivými místy v programu

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í



68

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.)



69

Sampling Techniky generování událostí

Softwarové - přerušení časovačem 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

Hardwarové - podpora v procesoru 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


Paměťová hierarchie


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

71

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 ?


Dynamická RAM


•Otevření řádku• 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• Hodnota z

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

Architektura paměti DRAM

řádkovýdekodér

sloupcovýdekodér

adresasloupce

adresařádku

data

řádkovýbuffer

matice kondenzátorů


•Typické rozměry• 16384 řádků• 8192 sloupců• celkem 128 Mbit

•Typické časy• tRCD = 13 ns

• Otevření řádku• tCL = 13 ns

• Čtení/zápis• tRP = 13 ns

• Zavření řádku


řádkovýdekodér1:16384

sloupcovýdekodér32:8192

adresasloupce

8 bit

adresařádku14 bit

data32 bit

řádkovýbuffer

8192 bit

matice kondenzátorů


•Typický čip• matice 128 Mbit• 8 bank• celkem 1 Gbit• 256 M * 4 bit

•Paralelismus• 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

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

data32 bit

dekodérbanky

1:8

adresabanky3 bit

multiplexor8*4:32

data4 bit

adresa14 bit

řídícísignály

banka 0 banka 1 banka 2 banka 3 banka 4 banka 5 banka 6 banka 7


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

•Paralelismus• Všechny čipy

dělají totéž• Každý řeší 4 bity

•Doplňky• ECC: +2 čipy –

paritní kontrola

Architektura paměti DRAM - příkladčip 3čip 2čip 1čip 0

čip 7čip 6čip 5čip 4



adresya řízení

data64 bit


•DDR3 modul• dual rank• každý rank

256 M * 64 bit• celkem 4 GB• 32 čipů• 512 M * 64 bit

•Paralelismus• Ranky pracují

nezávisle• Ke sběrnici může

přistupovat jen jeden

•Doplňky• „registered“:

opakovač signálů

Architektura paměti DRAM – typický 4GB DDR3 modul

rank0

rank1

adresya řízení

data64 bit

výběrranku


•DDR3 kanál• dva paralelně

propojené moduly• každý modul

512 M * 64 bit• celkem 8 GB• 1 G * 64 bit

•Paralelismus• Jednotlivé ranky

obou modulů pracují nezávisle

• Data přenáší pouze jeden

•Varianty• „registered“: až 4

moduly• větší a pomalejší

Architektura paměti DRAM - kanályadresya řízení

data64 bit

výběrranku

rank0

rank1

modul 0

rank2

rank3

modul 1


•Dual channel• 2 kanály• každý kanál

1 G * 64 bit• celkem 16 GB• 1 G * 128 bit

nebo2 G * 64 bit

•Paralelismus• Kanály dělají

totéžnebo

• Kanály pracují a přenášejí data nezávisle

Architektura paměti DRAM – dual channelkanál 0 kanál 1

rank0

rank1

modul 0

rank2

rank3

modul 1

rank0

rank1

modul 2

rank2

rank3

modul 3


•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

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


•Atomická operace• časový multiplex:

8 přenosůpo 64 bitech

• celkem 512 bitů• při 1600 MT/s

zaměstná 1 kanálna 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)



Rozhraní procesor - DRAM

82

Přímé připojení na DDR3 1-4 kanály po 64 bitech, každý až 1600 MT/s = 12.8 GB/s

Intel DMI, QPI, AMD HyperTransport Serio-paralelní rozhraní, různé šířky, až 25.6 GB/s

Intel FSB 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


Statická RAM


•Řádky a sloupce• Aktivace probíhá

současně•Čtení

• Celý řádek vysílá své hodnoty

• Sloupcový dekodér vybírá data

•Zápis• Sloupcový

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

Architektura paměti SRAM

řádkovýdekodér

sloupcovýdekodér

adresasloupce

adresařádku

data

matice klopných obvodů


•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• Společné

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


adresařádku

asloupce

adresabanky

data


•Dvoubránová paměť

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

navíc• 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• registry, TLB



Asociativní paměť


•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ů• TLB1


tag data

tag data

==

====

==


SRAM

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

• 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á

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


tag data

=

index


•N-cestně asociativní paměť

• Přímo mapovaná asociativní paměť je použita N-krát

• Vyžaduje strategii výměny při zaplnění

•Převládající způsob implementace cache

• N mírně roste s velikostí cache


tag dataindex

SRAM

=

SRAM

=

SRAM

=


Cache poslední úrovně

91

LLC = L2 nebo L3 Obvykle společná pro všechna/některá jádra na čipu Typické velikosti 4-16 MB

Stupeň asociativity 8-16 Cache Line = 512, někdy 1024 bitů

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í


Cache prostřední úrovně

92

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


Cache první úrovně

93

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)


TLB

94

Překlad virtuálních adres na fyzické Často dvě úrovně TLB

DTLB1 pouze pro data, 16-64 záznamů odpovídá 64-256 KB adresového prostoru

TLB2 společná, cca. 512 záznamů Latence DTLB1 bývá započtena do latence L1D

L1D bývá „virtually-indexed-physically-tagged“ Latence TLB2 v řádu 2-3 ns Není-li záznam v TLB:

„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


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

95

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

DTLB1tag

indexassoc

TLB2tag

indexassoc

fyzická adresa

L1Dtag

indexassoc

L2tag

indexassoc

L3tag

indexassoc

velikost 256 TB 1 TB 16 MB 1 MB 64 KB 4 KB 64 B


ALU

Typická latence a propustnost – Intel Sandy Bridge

96

latence (cykly)

operací/cyklus

B/operace B/cyklus GB/s[3 GHz CPU]

registry 0 (započteno v čase instrukce)

teoreticky 14, prakticky 3-6

4-16 až 112SIMD 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

DDR3-1600dual channel

cca 120 2/15 64 8.5 25.6

reg L1 L2 L3 DRAM


Typická latence a propustnost – Intel Sandy Bridge

97

reg

ALU

L1 L2 L3 DRAM

ALU

ALU

ALU

Quad Core


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é

autotuning, NUMA awareness cache-oblivious algoritmy

Velikost Cache Line lze odhadnout spolehlivě – 64B Přesunovat do procesoru méně než 64B je plýtvání

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


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)


Úrovně cache

Registry poskytují cache úrovně 0 Použítí této „cache“ řídí překladač

Programátor může vytvořit šanci nebo zlepšit podmínky úpravou kódu 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

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


Cache-oblivious algorithms



102

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

Cache-obliviousness 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


Cache-oblivious algorithms (zjednodušený pohled)

103

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)

Zjednodušeno (parametrem bývá i velikost cache line) 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))

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



104

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í)

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



105

Rozděl a panuj Problém P0 se dělí na podproblémy P1 a P2

Pamětová složitost: m0 < m1 + m2

Část dat D12 je používána oběma podproblémy: |D12| = d12 = m1 + m2 - m0

Pro m0 > C se problém P0 do cache nevejde Čá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


Násobení matic - rozděl a panuj

106

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

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

j-split a k-split - další možnosti dělení 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



107

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)


Násobení matic - rozděl a panuj

108

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í <iS;jS;kS> a zvolené koncové <iF;jF;kF>

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


Násobení matic - cache-aware

109


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 Režie rekurze je větší než režie iterace

Na pořadí vzájemného vnoření iterací teoreticky nezáleží 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í


Násobení matic - cache-oblivious

110


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)


Cache-oblivious algorithms – vliv bloků

111

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ě


Cache-oblivious algorithms – vliv bloků

112

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)


Nejvýznamnější cache-oblivious algoritmy

113

Násobení matic O(1+n2/B+n3C1/2/B) Strassen: nlog2(7)

Transpozice matice O(1+mn/B)

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

Funnelsort 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


Cache-oblivious algoritmy

Otázky spojené s cache-oblivious algoritmy Ignorujeme strategii výměny cache

Nevadí: LRU se nechová hůře než ideální cache poloviční velikosti Ignorujeme vícevrstevnost cache hierarchie

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


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á

Každý blok násobkem 64 B (cache line) Jsou-li bloky vzdálenější než 4 KB, pak nejvýše 32 bloků (TLB1)

Podúloha řešena iterativně nad jádrem úlohy 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)


Jiný pohled na cache


Algoritmy a cache

117

Přístupy do paměti v algoritmech jsou dvou druhů S předvídatelnou adresou

Lineární průchody polemfor ( i = 0; i < N; ++ i ) { /*...*/ a[ i] /*...*/ }

Lineární průchody s větším skokemfor ( 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-sortfor ( i = 0; i < N; ++ i ) { /*...*/ a[ b[ i]] /*...*/ }

Binární vyhledáváníwhile ( /*...*/ ) { if ( a[ j] > /*...*/ ) j = /*...*/; else j = /*...*/; }

Spojové strukturywhile ( p != 0 ) { /*...*/ p = p->next; /*...*/ }


Algoritmy a cache

118

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

totéž může udělat programátor ručně 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


Algoritmy a cache

119

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í tabulkyfor ( i = 0; i < N-1; ++ i ) { x = hash( d[ i+1]); /*...*/ v /*...*/; v = a[ x]; }

Bucket-sortfor ( 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é strukturywhile ( p != 0 ) { /*...*/ p = p->next; /*...*/ }


Algoritmy a cache

120

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 nabsearch_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


Loop reversal

121

Původní průchod Většina sousedů v průchodu je závislá

K

J


Loop reversal

122

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

K

J


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]

123

K

J


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]

124

K

J


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

bsearch( a, M, b[ i]);

void bsearch( a, M, x)

{

while ( /*...*/ )

{

if ( a[ j] > x )

j = /*...*/;

else

j = /*...*/;

}

}

bsearch_many( a, M, b, N);

void bsearch_many( a, M, b, N)

{

while ( /*???*/ )

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

{

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

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

else

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

}

}

“Paralelní” bsearch

125


Algoritmy a cache - další pohled

126

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 Zbytečný hardware, zbytečná spotřeba energie

Architektura RAM stroje je pro takové algoritmy nadbytečná 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

Date post:	24-Feb-2016
Category:	Documents
Upload:	kalkin
View:	44 times
Download:	0 times

Vývoj vysoce výkonného software

Documents