Sekvenční architektury II. Zpracování instrukcí

Sekvenˇcní architektury II

Zpracování instrukcí

Jak zvýšit výkon CPU I

zkrátit cˇ as nutný ke zpracování 1 instrukce I

urychlit cˇ asovaˇc (Timer) = zvýšení taktu I

I

I

I

I

to je technicky velmi nároˇcné, poslední dobou se frekvence ˇ ≈ 3GHz CPU nemení zvyšování frekvence vede k velkému nárustu ˚ produkovaného tepla i samotné zvyšování frekvence vyžaduje zásah do architektury

použít tzv. pipelining = jistá forma paralelizace

ˇ více operací najednou provádet I I

tím již dostáváme paralelní systém ale tzv. superskalární zpracování patˇrí mezi implicitneˇ paralelní systémy

Definition ˇ Je-li nekterý systém schopný paralelneˇ zpracovávat kód psaný pro sekvenˇcní systém, mluvíme o implicitneˇ paralelním systému.

Pˇrehled procesoru˚ firmy Intel Název 8086,80186,80286 80386,80386SX,80386DX 80486,80486SX,80486DX Pentium, Pentium MMX Pentium Pro,Pentium 2,3,Celeron Pentium 4 Intel Core2 Core i3, i5, i7, Xeon Core i3, i5, i7, Xeon Core i3, i5, i7, Xeon Core i3, i5, i7, Xeon

Architektura 86 80386 80486 P5 P6 Netburst Core arch. Nehalem Sandy Bridge Ivy Bridge Haswell

Rok uvedení 1978 1985 1989 1993 1995 2000 2006 2010 2011 2012 2013

Pˇrehled procesoru˚ firmy AMD

Název Am386, Am486, Am5x86 K5 K6, K6-2, K6-III Athlon, Duron, Sempron Athlon 64, Opteron, Sempron Phenom, Athlon, Opteron FX-8xxx, FX-6xxx, FX-4xxx

Architektura Amx86 K5 K6 K7 K8 core K10 Bulldozer Bobcat Jaguar

Rok uvedení 1979 1995 1997 1999 2003 2007 2011

Pipelining I.

Procesor zpracovává instrukce pomocí pipeliningu: I

ˇ umožnuje urychlit zpracování instrukcí

I

dovolí taktování na vyšší frekvence

ˇ Vezmeme si následující kód: LOAD R1, @10 # nacti do reg. 1 hodnotu z adresy 10 ADD R1, @12 # pricti do reg. 1 hodnotu a adresy 12 STORE R1, @20 # zapis reg. 1 na adresu 20

Pipelining III. TAKT 1

TAKT 2

TAKT 3 ˇcas

LOAD R1,@10

INSTR. 1

ADD R1,@12

INSTR. 2

STORE R1,@20

instrukce

INSTR. 3

Pipelining IV.

PIPELINING se podobá výrobní lince I

ˇ na více kroku, zpracování instrukce se rozdelí ˚ napˇr. I I I I I

naˇctení instrukce (instruction fetch) - IF dekódování instrukce (instruction decode) - ID naˇctení operandu (operand fetch) - OE provedení instrukce (instruction execution) - IE zápis operandu (operand write) - OW

I

tyto kroky jsou jednodušší na provedení

I

díky tomu lze zkrátit délku jednoho taktu - ten nyní odpovídá jednomu kroku zpracování

I

ˇ lze zˇretezit ˇ provádení

Pipelining V. 1

TAKT 1 2 3

4

TAKT 2 5 6

TAKT 3 ˇcas

IF ID OF LOAD R1,@10

INSTR. 1

IF ID OF IE INSTR. 2 ADD R1,@12 IF ID N/A OW STORE R1,@20 N/A = data dependency instrukce

INSTR. 3

Pipelining VI.

Architektura P5 P6 Netburst Core Nehalem–Haswell

Délka pipeline 5 10-14 20-31 14 14-19

Pipelining VII. Pipelining se potýká se tˇremi typy závilostí, které snižují jeho efektivitu: I

datová závislost - data dependency I

I

závislost na zdrojích - resource dependency I

I

nastává ve chvíli, kdy jedna instrukce potˇrebuje data, která ješteˇ nejsou spoˇctena ˇ pˇristupovat napˇr. na v situaci, kdy dveˇ instrukce chtejí ˇ nebo do stejného registru stejné místo v pameti

závislost na podmínce - branch dependency I

I

v situaci, kdy není znám výsledek výpoˇctu, jenž muže ˚ ˇ (napˇr. ovlivnit, jakým zpusobem ˚ bude kód dále prováden ˇ nejsou data k vyhodnocení podmíneného skoku) ˇ se vyskytuje jedna podmínka na udává se, že v prum ˚ eru každých 5-6 instrukcí

Pipelining VIII.

Problémy s datovou závislostí a závislostmi na zdrojích se ˇreší pomocí: I

ˇ instrukcí mimo poˇradí - out of order execution provádení I

I I

I

procesor pˇrehazuje poˇradí zpracování instrukcí tak, aby se ˇ vyhnul zminovaným závislostem ˇ i pˇrekladaˇc pˇri ruzných muže ˚ to provádet ˚ optimalizacích ˇ vetšinou nepomáhá u závislostech na podmínce

pˇrejmenování registru˚ – registers renaming I

ˇ uložení procesor se muže ˚ rozhodnout, že zmení ˇ promenných v registrech, pokud to pomuže ˚ lepšímu zpracování kódu

Pˇredvídání podmínek Problémy se závislostí na podmínce se ˇreší pomocí: I

pˇredvídání výsledku˚ podmínek - speculative execution, branch prediction I

I

I I

I

ˇ procesor se pokusí uhodnout, která vetev programu má ˇ šanci, že bude provádena ˇ vetší ˇ eˇ pˇred tu pak zaˇcne pomocí pipeline zpracovávat ješt vyˇrešením samotné podmínky ˇ to má pˇrekvapiveˇ velkou úspešnost až 99% pokud pˇredvídání selže, je nutné zaˇcít zpracovávat druhou ˇ vetev ˇ celé pipeline, což vede k to si vyžaduje vyprázdnení velkému zpomalení I

I

na architektuˇre Nehalem odhadem 20 taktu˚

ˇ pipeliny pˇríliš dlouhé to je duvod, ˚ proˇc nelze delat I

ˇ ˇ delení na menší elementární kroky umožnuje rychlejší taktování

Pˇredvídání podmínek I

k tomu, aby procesor dokázal odhadnout výsledek ˇ podmíneného skoku, používá set associative cache zvanou Branch Target Buffer

I

velikost se nezná, ale odhaduje se na 4kB (P5) a 8-16kB (Sandy Bridge)

I

cache používá jako klíˇc adresu cíle skoku ˇ uložená hodnota odpovídá pravdepodobnosti, že skok bude proveden (taken) nebo ne (not taken) a zpracuje se hned následující instrukce

I

Zdroj: www.agner.org/optimize/optimizing_cpp.pdf

Pˇredvídání podmínek I

procesor si navic pamatuje kratkou historii toho, jak ˇ podminené skoky dopadly v posledních n pˇrípadech

I

za tím úˇcelem se používá jednoduchá metoda vyvinutá T.Y.Yehem a Y.N.Pattem

Zdroj: www.agner.org/optimize/optimizing_cpp.pdf

Superskalární zpracování I.

I

jsou-li dveˇ instrukce na sobeˇ zcela nezávislé, je možné je zpracovat obeˇ souˇcasneˇ

I

lze tak využít dveˇ nebo více pipeline k efektivnímu využití je potˇreba mít instrukce dobˇre ˇ setˇrídené

I

I I

I

ˇ behem ˇ to lze delat pˇrekladu - pˇrekladaˇc nebo za chodu programu - procesor

Intel zavedl superskalární zpracování v procesorech P5 Pentium

Superskalární zpracování II.

1

2

3

LOAD R1,@10

IF

ID

OF

ˇcas INSTR. 1

LOAD R2,@11

IF

ID

OF

INSTR. 2

ADD R1,@12

IF

ID

OF

IE

INSTR. 3

ADD R2,@13

IF

ID

OF

IE

INSTR. 4

IF

ID N/A OW

INSTR. 5

STORE R1,@20 instrukce

4

5

6

Optimalizace na zpracování podmínek Pro optimální využití pipeline je nutné minimalizovat ˇ vyšetˇrování podmínek, obzvlášteˇ tech, které jsou špatneˇ pˇredvídatelné ˇ následující kód: Pˇríklad: Budeme opakovaneˇ provádet 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

void p e r f o r m T e s t ( const i n t ∗ data , const i n t s i z e , i nt& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i ++ ) { i f ( data [ i ] == 1 ) a ++; i f ( data [ i ] == 0 ) a = 0; i f ( data [ i ] == −1 ) a−−; } }

Optimalizace na zpracování podmínek I

1 2 3 4 5 6 7 8 9 10 11 12 13 14

ˇ pole data budeme naplnovat prodlužijícím se opakujicím náhodným vzorem hodnot -1,0,1

void s e t u p T e s t ( i n t ∗ data , const i n t s i z e , const i n t p a t t e r n L e n g t h ) { i n t ∗ p a t t e r n = new i n t [ p a t t e r n L e n g t h ] ; srand ( 0 ) ; f o r ( i n t i = 0 ; i < p a t t e r n L e n g t h ; i ++ ) p a t t e r n [ i ] = rand ( ) % 3 − 1 ; f o r ( i n t i = 0 ; i < s i z e ; i ++ ) { data [ i ] = p a t t e r n [ i % p a t t e r n L e n g t h ] ; } delete [ ] p a t t e r n ; }

Optimalizace na zpracování podmínek Výsledky: Délka vzoru 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 I

ˇ Neúspešnost bez -O3 s -O3 0.0006% 0.0006% 0.0005% 0.0004% 0.0010% 0.0005% 3.9955% 3.0589% 7.1143% 4.6074% 5.1034% 1.4232% 8.0148% 2.2992% 10.9170% 2.5160% 15.0898% 3.4148% 16.9543% 11.1091% 17.8589% 12.1402% 18.7427% 14.9048% 18.6398% 17.6160% 18.3994% 19.6302% 18.3008% 21.0191% 18.3611% 21.6142% 18.3970% 21.9362% 18.3810% 22.0045% 18.3722% 22.0538% 18.3735% 22.0417% 18.3635% 22.0176% 18.3620% 22.0096%

vidíme, že s prodlužijícím se vzorem opakování klesá efektivita pˇredvídání podmínek

Optimalizace na zpracování podmínek

I

nesmíme také zapomenout, že každý cyklus v sobeˇ obsahuje podmínku, jež se musí ˇrešit v každé smyˇcce

I

její výsledek bude vždy stejný až na poslední pruchod, ˚ takže bude pˇredvídána s velkou efektivitou (alesponˇ u delších cyklu) ˚

I

i tak se ale vyplatí se této podmínky v cyklu zbavit pomocí tzv. rozbalení smyˇcky loop unrolling

Optimalizace na zpracování podmínek 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

void p e r f o r m U n r o l l e d T e s t ( const i n t ∗ data , const i n t s i z e , i nt& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i += 4 ) { i f ( data [ i ] == 1 ) a ++; i f ( data [ i ] == 0 ) a = 0; i f ( data [ i ] == −1 ) a−−; i f ( data [ i + 1 ] == 1 ) a ++; i f ( data [ i + 1 ] == 0 ) a = 0; i f ( data [ i + 1 ] == −1 ) a−−; i f ( data [ i + 2 ] == 1 ) a ++; i f ( data [ i + 2 ] == 0 ) a = 0; i f ( data [ i + 2 ] == −1 ) a−−; i f ( data [ i + 3 ] == 1 ) a ++; i f ( data [ i + 3 ] == 0 ) a = 0; i f ( data [ i + 3 ] == −1 ) a−−; } }

Optimalizace na zpracování podmínek ˇ eˇ pˇredvídané podmínky): Výsledky (neúspešn

Délka vzoru 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152

bez rozbalení bez -O3 s -O3 0.0006% 0.0006% 0.0005% 0.0004% 0.0010% 0.0005% 3.9955% 3.0589% 7.1143% 4.6074% 5.1034% 1.4232% 8.0148% 2.2992% 10.9170% 2.5160% 15.0898% 3.4148% 16.9543% 11.1091% 17.8589% 12.1402% 18.7427% 14.9048% 18.6398% 17.6160% 18.3994% 19.6302% 18.3008% 21.0191% 18.3611% 21.6142% 18.3970% 21.9362% 18.3810% 22.0045% 18.3722% 22.0538% 18.3735% 22.0417% 18.3635% 22.0176% 18.3620% 22.0096%

s rozbalením bez -O3 s -O3 0.0005% 0.0006% 0.0005% 0.0005% 0.0005% 0.0004% 0.0012% 0.0009% 0.0014% 0.0011% 0.0021% 0.0017% 2.0792% 0.3154% 3.9394% 0.0028% 7.3365% 1.0891% 11.9075% 2.3585% 16.8415% 4.1920% 20.7197% 6.7165% 22.6760% 10.5239% 22.8864% 15.7348% 22.8314% 20.9794% 22.8662% 25.6041% 22.8915% 28.3501% 22.8386% 29.7677% 22.8021% 30.1786% 22.7777% 30.3599% 22.7585% 30.3551% 22.7403% 30.2972%


I

rozbalení smyˇcek opravdu pomáhá

I

ˇ i pˇrekladaˇc rozbalení smyˇcek umí provádet

I

ˇ ˇ nevýhodou je, že se zvetšuje kód, což muže ˚ zatežovat instrukˇcní cache

Optimalizace na zpracování podmínek I

ˇ že kratší vzory umí CPU zpracovat efektivneji ˇ je videt,

I

ˇ na zpracování náhodné sekvence tedy zkusíme rozdelit bloky

Kód: 1 2 3

const i n t l o o p s = 3 2 ; f o r ( i n t i = 0 ; i < l o o p s ; i ++ ) p e r f o r m U n r o l l e d T e s t ( data , s i z e , a ) ;

nahradíme kódem 1 2 3 4 5

const i n t l o o p s = 3 2 ; const i n t b l o c k S i z e = 3 2 ; f o r ( i n t o f f s e t = 0 ; o f f s e t < s i z e ; o f f s e t += b l o c k S i z e ) f o r ( i n t i = 0 ; i < l o o p s ; i ++ ) p e r f o r m U n r o l l e d T e s t ( &data [ o f f s e t ] , b l o c k S i z e , a ) ;

Optimalizace na zpracování podmínek ˇ eˇ pˇredvídané podmínky): Výsledky (neúspešn

Délka vzoru 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152

bez rozbalení bez -O3 s -O3 0.0006% 0.0006% 0.0005% 0.0004% 0.0010% 0.0005% 3.9955% 3.0589% 7.1143% 4.6074% 5.1034% 1.4232% 8.0148% 2.2992% 10.9170% 2.5160% 15.0898% 3.4148% 16.9543% 11.1091% 17.8589% 12.1402% 18.7427% 14.9048% 18.6398% 17.6160% 18.3994% 19.6302% 18.3008% 21.0191% 18.3611% 21.6142% 18.3970% 21.9362% 18.3810% 22.0045% 18.3722% 22.0538% 18.3735% 22.0417% 18.3635% 22.0176% 18.3620% 22.0096%

s rozbalením bez -O3 s -O3 0.0005% 0.0006% 0.0005% 0.0005% 0.0005% 0.0004% 0.0012% 0.0009% 0.0014% 0.0011% 0.0021% 0.0017% 2.0792% 0.3154% 3.9394% 0.0028% 7.3365% 1.0891% 11.9075% 2.3585% 16.8415% 4.1920% 20.7197% 6.7165% 22.6760% 10.5239% 22.8864% 15.7348% 22.8314% 20.9794% 22.8662% 25.6041% 22.8915% 28.3501% 22.8386% 29.7677% 22.8021% 30.1786% 22.7777% 30.3599% 22.7585% 30.3551% 22.7403% 30.2972%

s bloky bez -O3 s -O3 0.02% 0.04% 0.02% 0.04% 0.02% 0.03% 0.94% 1.19% 1.16% 1.69% 0.02% 0.03% 2.66% 0.79% 1.74% 0.48% 2.04% 0.26% 2.24% 0.36% 2.47% 0.56% 2.71% 0.88% 2.87% 1.46% 2.92% 2.04% 2.92% 2.49% 2.95% 2.65% 2.95% 2.72% 2.95% 2.76% 2.94% 2.78% 2.94% 2.78% 2.93% 2.77% 2.94% 2.77%


10

10

1 misprediction in %

0.1

0.01

0.1

0.01

0.001

0.001 baseline unrolling blocks

0.0001 1

4

16

64

256 1k 4k 16k Pattern length

baseline unrolling blocks

0.0001

64k 256k 1M

1

4

16

64


10

misprediction in %

misprediction in %

1

1

0.1

0.01 baseline unrolling blocks

0.001 1

4

16

64


64k 256k 1M

Porovnání efektivity pˇredvídání podmínek na Intel Core 2 E6600, Intel i7 4600M a AMD Phenom 2 X6 1075T s -O3.

64k 256k 1M

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

baseline unrolling blocks CPU ticks per element

CPU ticks per element


4

16

64

256 1k 4k Pattern length


1

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

16k

64k 256k

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

1M


1

4

16

64


16k

64k 256k


1

4

16

64


16k

64k 256k

1M

Poˇcet taktu˚ CPU na jeden element na Intel Core 2 E6600, Intel i7 4600M a AMD Phenom 2 X6 1075T s -O3.

1M

Optimalizace na zpracování podmínek Mužeme ˚ také použít pˇríkaz switch: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

void p e r f o r m S w i t c h T e s t ( const i n t ∗ data , const i n t s i z e , i nt& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i ++ ) { switch ( a [ data ] ) { case 1 : a ++; break ; case −1: a−−; break ; default : a = 0; } } }

Optimalizace na zpracování podmínek nebo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

void p e r f o r m U n r o l l e d S w i t c h T e s t ( const i n t ∗ data , const i n t s i z e , in t& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i += 4 ) { switch ( a [ data ] ) { case 1 : a ++; break ; case −1: a−−; break ; default : a = 0; } switch ( a [ data + 1 ] ) { case 1 : a ++; break ; case −1: a−−; break ; default : a = 0; } switch ( a [ data + 2 ] ) { case 1 : a ++; break ; case −1: a−−; break ; default : a = 0; } switch ( a [ data + 3 ] ) { case 1 : a ++; break ; case −1: a−−; break ; default : a = 0; } } }

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0




baseline unrolling blocks switch blocks unrolled switch blocks 4

16

64



1

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

16k

64k 256k

23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

1M

baseline unrolling blocks switch blocks unrolled switch blocks

1

4

16

64


16k

64k 256k

baseline unrolling blocks switch blocks unrolled switch blocks

1

4

16

64


16k

64k 256k

1M

Poˇcet taktu˚ CPU na jeden element na Intel Core 2 E6600, Intel i7 4600M a AMD Phenom 2 X6 1075T s -O3.

1M

Optimalizace na zpracování podmínek Nyní pˇrídáme poˇcet podmínek na jeden element pole: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

void p e r f o r m M u l t i v a l u e T e s t ( const i n t ∗ data , const i n t s i z e , const i n t n , i nt& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i ++ ) { f o r ( i n t j = −n ; j <= n ; j ++ ) { i f ( data [ i ] == n ) a ++; i f ( data [ i ] == −n ) a−−; } i f ( data [ i ] == 0 ) a = 0; } }

Optimalizace na zpracování podmínek Vnitˇrní smyˇcku rozbalíme pomocí C++ šablon: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

template < i n t n > struct MultivalueTester { s t a t i c void t e s t ( const i n t data , i n t & a ) { i f ( data == n ) a ++; i f ( data == −n ) a−−; M u l t i v a l u e T e s t e r < n − 1 > : : t e s t ( data , a ) ; } }; template <> struct MultivalueTester < 0 > { s t a t i c void t e s t ( const i n t data , i n t & a ) { i f ( data == 0 ) a = 0; } }; template < i n t n > void p e r f o r m T e m p l a t e M u l t i v a l u e T e s t ( const i n t ∗ data , const i n t s i z e , i nt& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i += 4 ) { M u l t i v a l u e T e s t e r < n > : : t e s t ( data [ i ] , a ) ; M u l t i v a l u e T e s t e r < n > : : t e s t ( data [ i + 1 ] , a ) ; M u l t i v a l u e T e s t e r < n > : : t e s t ( data [ i + 2 ] , a ) ; M u l t i v a l u e T e s t e r < n > : : t e s t ( data [ i + 3 ] , a ) ; } }

100

100

10

10

1

misprediction in %

misprediction in %


0.1 0.01 0.001 n=2 n=4 n=8 n=16 n=32

0.0001 0.00001 1

4

16

64


1 0.1 0.01 0.001 n=2 n=4 n=8 n=16 n=32

0.0001 0.00001

64k 256k 1M

1

4

16

64


64k 256k 1M

100

misprediction in %

10 1 0.1 0.01 0.001 n=2 n=4 n=8 n=16 n=32

0.0001 0.00001 1

4

16

64


64k 256k 1M

Procento neúspešných pˇredvídání pˇri 2n + 1 poˇctu podmínek na element na Intel Core 2 E6600, Intel i7 4600M a AMD Phenom 2 X6 1075T s -O3.

optimalizace na zpracování podmínek

I

tento pˇríklad celkoveˇ ukazuje, že:

Rozbalení krátkého for cyklu pomocí šablon C++ muže ˚ pˇrinést až 8-násobné urychlení.


I

ˇ rozbalování smyˇcek pˇrekladaˇce dokáží provádet automaticky

I

u gcc k tomu slouží pˇrepínaˇc -funroll-loops

I

podíváme se na jeho efektivitu (gcc verze 4.8)

Optimalizace na zpracování podmínek ˇ Rozbalování smycek Pˇríklad: Výpoˇcet sumy 1 2

f o r ( i n t i = 0 ; i < s i z e ; i ++ ) sum += data [ i ] ;

1 2 3 4 5

f o r ( i n t i = 0 ; i < s i z e ; i += 2 ) { sum += data [ i ] ; sum += data [ i + 1 ] ; }

1 2 3 4 5 6 7

for ( int i = 0; { sum += data [ sum += data [ sum += data [ sum += data [ }

...

i < s i z e ; i += 4 ) i ]; i + 1 ]; i + 2 ]; i + 3 ];


Unrolling žádný 2 4 8 16 32 64

-O3 1.8353 0.4984 0.4660 0.2447 0.1853 0.1342 0.1372

Takty na element -O3 -funroll-loops 1.14267 0.44991 0.46567 0.23750 0.13921 0.12992 0.12835

Efekt rozbalení smyˇcek na Intel i7 4600M.

Optimalizace na zpracování podmínek I I I I I

vidíme, že použití -funroll-loops dává lepší výsledky, pokud jsme sami žádný unrolling neprovedli pokud provedem unrolling sami, mužeme ˚ tím ješteˇ mnoho získat a to až do 16-ti násobného rozbalení ˇ for cyklu bylo vetší, ˇ pokud by telo mohlo by ale dojít k velkému nárustu ˚ kódu a zahlcení instrukˇcní cache to, že jeden element zpracujeme jen za jednu osminu taktu CPU je zpusobeno ˚ vektorizací (viz. další cˇ ásti pˇrednášky) ukazuje se, že rozbalení smyˇcky pomocí C++ šablon je neefektivní, pˇrekladaˇc pak zˇrejmeˇ nedokáže provést vektorizaci

Volání funkcí I I I I

64-bitové procesory mají dvojnásobek registru, ˚ lze tedy pˇredávat více parametru˚ pomocí nich a ne pˇres zásobník lze tak pˇredat až 8 parametru˚ typu double/float a 6 typu int nebo ukazatel volání virtuální metody obnáší dynamické urˇcení typu a ˇ skok tedy podmínený otestujeme si, jak to muže ˚ snížit výkon

Volání funkcí Pˇríklad s virtuální metodou: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class adder { public : v i r t u a l void addNumber ( i n t & n ) const = 0 ; }; class oneAdder : public adder { public : void addNumber ( i n t & n ) const { n += data [ 0 ] ; data [ 0 ] ∗= −1; } ; }; class twoAdder : public adder { public : void addNumber ( i n t & n ) const { n += data [ 1 ] ; data [ 1 ] ∗= −1; } ; }; I

ˇ metody napsali pouhé n += 1 nebo pokud bysme do tela n += 2, pˇrekladaˇc by to eliminoval

Volání funkcí Pˇríklad s pˇríkazem switch: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class switchAdder { public : switchAdder ( i n t c ) : number ( c ) { } ; void addNumber ( i n t & n ) const { switch ( t h i s −>number ) { case 0 : n += data [ 0 ] ; break ; case 1 : n += data [ 1 ] ; break ; case 2 : n += data [ 2 ] ; break ; case 3 : n += data [ 3 ] ; break ; } data [ t h i s −>number ] ∗= −1; } protected : i n t number ; };

Volání funkcí Pˇríklad s šablonovým parametrem: 1 2 3 4 5 6 7 8 9 10

template < i n t i n d e x > class templateAdder { public : void addNumber ( i n t & n ) const { n += data [ i n d e x ] ; data [ i n d e x ] ∗= −1; }; }; I I

ovšem nahrazení virtuálních metod šablonovými parametry není vždy možné ˇ návrhu a pokud ano, vyžaduje cˇ asto výraznou zmenu aplikace

Volání funkcí Výsledky testu: Virtuální metoda switch Nevirtuální metoda Šablonový parametr inline metoda Bez volání funkce I I I I I I

Intel Core2 7.08 1.77 1.90 1.96 1.89 1.82

Intel i7 5.85 0.83 0.84 0.89 0.81 0.81

AMD Phenom 2 7.11 1.78 1.89 1.91 1.88 1.82

vidíme, že volání virtuální metody je cca. 4-krát pomalejší ostatní volání vychází stejneˇ volání pomocí switch je rychlejší, CPU zˇrejmeˇ nedokáže pˇredvídat volání virtuálních metod implementace bez volání funkce a inline volání vychází stejneˇ šlo o velmi jednoduché fce., takže je pˇrekladaˇc zˇrejmeˇ zpracoval jako inline pokud se všechny parametry vejdou do registru, ˚ nemusí nás volání funkce stát nic

Eliminace podmínek I

I

I

standard C/C++ definuje, že je-li napˇr. ve výrazu ˇ podmínkaA && podmínkaB podmínkaA nesplnena, podmínkaB se už nevyhodnocuje proto je lepší zpisovat dˇríve podmínky, které budou ˇ ˇ nebo podmínky, které se pravdepodobn eˇ nesplneny snadno vyhodnotí podobná úvaha platí i pro operaci ||

Eliminace podmínek I 1

cˇ asto používanou podmínku i f ( i >= 0 && i < s i z e )

nahradit podmínkou 1 I

I 1

i f ( ( unsigned i n t ) i < s i z e )

pˇretypovaní na unsigned int nestojí vubec ˚ nic a je-li i ˇ po pˇretypování hodneˇ zaporné celé cˇ íslo, stane se z nej velké kladné cˇ íslo, takže podmínce nevyhoví podobneˇ podmínku i f ( i >= c && i < s i z e )

lze nahradit za 1

i f ( ( unsigned i n t ) i − c < s i z e − c )

kde výraz size - c lze pˇredpoˇcítat

Zpracování algebraických výrazu˚ I I I I I I I

výraz a + b + c + d je ekvivalentní výrazu ( a + b ) + ( c + d ) první je sekvence tˇrí operací druhý je suma dvou výrazu, ˚ které mohou být zpracovány nezávisle CPU tak muže ˚ využít superskalární zpracování kódu a lépe využít pipeline ˇ automaticky pˇrekladaˇce tyto úpravy provádejí v pˇripadeˇ aritmetiky s plovoucí desetinou cˇ árkou ale oba výrazy nejsou ekvivalentní ˇ zameˇ novat ˇ pˇrekladaˇc by je tedy nemel

Zpracování algebraických výrazu˚ Pˇríklad: Porovnáme následující tˇri zápisy stejného výrazu. 1 2 3

sum += n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8 ; sum += ( n1 + n2 ) + ( n3 + n4 ) + ( n5 + n6 ) + ( n7 + n8 ) ; sum += ( ( n1 + n2 ) + ( n3 + n4 ) ) + ( ( n5 + n6 ) + ( n7 + n8 ) ) ;

Výsledek: Výraz 1 2 3

int 1.6 1.4 1.4

Intel i7 4600M float double 1.6 3.2 1.5 3.0 1.5 3.0

AMD Phenom 2 X6 1075T int float double 2.0 3.0 5.8 1.9 2.8 5.4 1.9 2.6 5.0

Poˇcet taktu˚ na zpracování daných výrazu˚ s pˇrekladaˇcem gcc-4.8.2 s -O3. I I

výsledky meˇrení to ale nepotvrzují a ukazuje se, že ˇ r stejneˇ pˇrekladaˇc optimalizuje všechny tˇri výrazy témeˇ u úloh s velkou citlivostí na pˇresnost výpoˇctu je tedy dobré dávat pozor na optimalizace pˇrekladaˇce

Zpracování algebraických výrazu˚ ˇ Nároˇcnost nekterých celoˇcíselných operací s typem int. Operace * / % 2 % 3 I I

Intel i7 4600M 0.5 2.2 0.6 2.3

AMD Phenom 2 X6 0.6 3.6 0.8 4.3

ve výsledcích je zapoˇcítána možnost vektorizace % 2 pˇrekladaˇc optimalizuje pomocí bitového OR

Zpracování algebraických výrazu˚ ˇ Nároˇcnost nekterých operací s plovoucí desetinnou cˇ árkou. Operace * / pow( x, 2.0) pow( x, 2.13) sqrt exp log sin int -> float -> I

Intel i7 4600M float double 0.6 1.2 1.5 5.7 19.1 1.8 150.3 146.6 16 16 49 46 73 71 58 53 0.7 1.2 – 1.3

AMD Phenom 2 X6 float double 0.8 1.9 3.4 7.6 8.9 1.2 229 229 34 23 96 94 149 147 119 118 1.5 3.9 – 4.1

konstanty jako 1.0/3.0 jsou typu double, pˇrí výpoˇctech s typem float je tˇreba psát ( float ) 1.0/3.0 jinak dojde k výpoˇctu v typu double

Výjimky v C++ I I I I I I I

výjimky v C++ jsou efektivní nástroj pro ošetˇrení výjimeˇcných situací ˇ ji propagovat nahoru pˇri vzniku výjimky je potˇreba umet zásobníkem zárovenˇ se volají všechny potˇrebné destruktory ˇ pˇripravit to je nároˇcný proces a je potˇreba se na nej dnešní pˇrekladaˇce implementují tzv. zero-cost exception handling ˇ by to znamená, že pokud výjimka nevznikne, nemelo použití výjimek v kódu naši aplikaci zpomalit ˇ ošetˇrení vzniklé výjimky je s tímto pˇrístupem pomalejší, ale to už nevadí

Výjimky v C++ Pˇriklad: Efektivta zpracování kódu s výjimkami. I

porovnáme následující dveˇ funkce

1 2 3 4 5 6 7 8 9 10 11 12 13

void p e r f o r m T e s t ( const i n t ∗ data , const i n t s i z e , i nt& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i ++ ) { i f ( data [ i ] == 1 ) a ++; i f ( data [ i ] == 0 ) a = 0; } }

1 2 3 4 5 6 7 8 9 10 11 12 13

void p e r f o r m T e s t W i t h E x c e p t i o n ( const i n t ∗ data , const i n t s i z e , in t& a ) { a = 0; f o r ( i n t i = 0 ; i < s i z e ; i ++ ) { i f ( data [ i ] == 1 ) a ++; i f ( data [ i ] == 0 ) throw −1; } }

Výjimky v C++ Výsledky: bez výjimky s výjimkou zpracování výjimky I I

AMD Phenom 2 X6 1075T 2.1 2.7 6408

Intel i7 4600M 1.28 1.29 4179

tabulka udává výsledný poˇcet taktu˚ CPU na zpracování jednoho elementu, pokud nevznikne žádná výjimka poslední ˇrádek ˇríká, tolik taktu˚ zabere zpracování vzniklé výjimky

Výjimky v C++ I I

vidíme, že zero-cost zpracování výjimek je opravdu ˇ efektivní, obzvlášt’ na novejších CPU použití výjimek navíc muže ˚ eliminovat podmínky pro testování chybových kódu, ˚ což muže ˚ výpoˇcet dokonce ješteˇ trochu urychlit

Aserce I

I

ˇ dojít, ošetˇrení výjimeˇcných stavu, ˚ ke kterým by nemelo pokud program dobˇre funguje, je také možné pomocí asercí a makra assert program se musí dobˇre otestovat a v produkˇcní verzi se aserce úplneˇ vyˇradí

Shrnutí I I I I I

ˇ rychlost zpracování instrukcí v CPU je výrazneˇ ovlivnena efektivitou využití pipeline ˇ tu nejvíc narušují podmínené skoky CPU zpracovává kód spekulativneˇ a za urˇcitých okolností ˇ je schopný podmíené skoky dobˇre odhantou dopˇredu vyplatí se podmínky eliminovat, zpracovávat data po ˇ loop unrolling menších blocích a provádet zpracování výjimek v C++ lze dnes považovat za bezproblémové z pohledu rychlosti zpracování kódu

Sekvenční architektury II. Zpracování instrukcí

Recommend Documents