tutorial

Description

Optimalizace ahodnocení efektivitylineárních kódůIvan Šimeček, Pavel TvrdíkDepartment of Computer Science and EngineeringFaculty of Electrical EngineeringCzech Technical UniversityKarlovo nám. 13121 35 Prague 2Czech RepublicThis research has been supported by grant IBS 3086102.Obsah prezentace 2(1) Proč optimalizovat?(2) Architektura procesorů Intel (AMD) a některé nové rysy(3) SW techniky pro optimalizaci(4) Pravděpodobnostní model chování skryté paměti(5) Knihovny pro LA, výhody a nevýhody(6) Příklady použití jednotlivých optimalizačních postupůProč optimalizovat? 3Motivační příkladNásobení matic (MMM): A(n,n)×B(n,n) = C(n,n) Klasický algoritmus pro násobení (podle definice). Pro uložení čísel a výpočet použita dvojitá přesnost (typ double).Pro všechna měření (kromě vyjímky na slajdu 15) byla použita následující konfigurace: Intel Pentium 4• 2.4GHz, výrobcem udávaná špičková výkonnost procesoru 2.4 Gflops.• 512MB hlavní paměť na 400MHz, 8KB skrytá paměť 1. úrovně (L1) a 128KB skrytápaměti 2. úrovně (L2). Intel kompilátor (ICC) s přepínači pro maximální výkon.Standardní implementace MMM 4AlgorithmSMMM(in double A,B[1,...,n][1,...,n]; out C[1,...,n][1,...,n])(∗ Standardní implementace MMM∗)for i = 1 to n dofor j = 1 to n dobegins = 0;for k = 1 to n dos+ = A[i][k]∗B[k][j];C[i][j] = s;endPožadavky na paměťovou sběrniciNa 1 prvek výsledné matice je třeba z paměti načíst 2n čísel.VýkonnostPočet aritmetických FPU operací za ...

Informations

• Publié par: Enya
• Nombre de lectures: 28
• Langue: Slovak

Extrait

Optimalizace a hodnocení efektivity lineárních kódů

Ivan Šimeček, Pavel Tvrdík

Department of Computer Science and Engineering Faculty of Electrical Engineering Czech Technical University Karlovo nám. 13 121 35 Prague 2 Czech Republic

This research has been supported by grant IBS 3086102.

(1)

(2)

(3)

(4)

(5)

(6)

Proč optimalizovat?

Obsah prezentace

Architektura procesorů Intel (AMD) a některé nové rysy

SW techniky pro optimalizaci

Pravděpodobnostní model chování skryté paměti

Knihovny pro LA, výhody a nevýhody

Příklady použití jednotlivých optimalizačních postupů

2

Proč optimalizovat?

Motivační příklad

Násobení maticMM):(MA(n, n)×B(n, n) =C(n, n)

 Klasický algoritmus pro násobení (podle definice).

 Pro uložení čísel a výpočet použita dvojitá přesnost (typdouble).

Pro všechna měření (kromě vyjímky na slajdu 15) byla použita následující konfigurace:

 Intel Pentium 4

•2.4GHz, výrobcem udávaná špičková výkonnost procesoru 2.4 Gflops. •512MB hlavní paměť na 400MHz, 8KB skrytá paměť 1. úrovně (L1) a 128KB skrytá paměti 2. úrovně (L2).

 Intel kompilátor (ICC) s přepínači pro maximální výkon.

3

Standardní implementace MMM

AlgorithmSMMM(indoubleA, B[1, . . . , n][1, . . . , n];outC[1, . . . , n][1, . . . , n]) (∗Standardní implementace MMM∗) fori= 1tondo forj= 1tondo begin s= 0; fork= 1tondo s+ =A[i][k]∗B[k][j]; C[i][j] =s; end

Požadavky na paměťovou sběrnici

Na 1 prvek výsledné matice je třeba z paměti načíst2nčísel.

Výkonnost

Počet aritmetických FPU operací za jednotkový čas:

V . = 2∙n 3 T SMMM .

4

Pro

č

optimalizovat

?

5

Architektura procesorů Intel a některé nové rysy

Vektorizace výpočtu

Nové procesory obsahují podporu pro vektorové výpočty.

 Intel:

•od Pentia MMX pro typinteger, •od Pentia III pro typfloat(technologie SSE), •od Pentia IV pro typdouble(technologie SSE2).

 AMD:

•od AMD K6 pro typinteger, •od AMD K6-2 pro typfloat(technologie 3D now!), •od Athlon pro typdouble.

Architektura vektorové jednotky

 Miniaturní architekturaSIMD(Simple Instruction Multiple Data):

•Procesor obsahujeéovorktveregistry pro krátká pole dat. •Jedna operace nad vektorovým registrem = paralelní operace nad jednotlivými položkami pole.

6

Typy vektorových instrukcí:













Vektorizace výpočtu (pokr.)

binární aritmetické operace (sčítání, odčítání, násobení) (viz Obr. 1(a)),

redukce pomocí takových operací (viz Obr. 1(b)),

binární logické operace (AND, NAND, OR, XOR),

porovnávací operace, maximum, minimum,

konverze mezi jednotlivými formáty (byte,word,doubleword,owdrquad),

posuvné operace.

7

cdohízhctireca.íareciíetáunlaztkožky)Pol u. (4 cykl eřpzhcákžolopanéslvizáýtíbějsmne )3oPečit bmdome ( .výstupníssjedním ávorínědejáhpmínpřámzaedratezncí deti ( . )2 ěmitossu forcykluKlasický vada ( :ykžoP usympaívPo1)žklo

Podpora v kompilátorech:

 automatická detekce vhodného procesoru (ICC).

Vektorizace výpočtu (pokr.)

8

 automatická vektorizace (ICC),

 podpora nových datových typů (GCC+ICC),

Výkonnost

vektorizovaného

MMM

9

pálhcyrauorpťěmaánávovchstčaejínhcadjěíšěpnš,tsúejíhostjužitožpoMalá -w(sseayast-cisoaměnicosvitasytikrytápaměťsestup yzopžuti.a eD.fS: ěpvdraup br něobodimýnavížodubytaddnísouseěpouprávtaai(ápstasa)ld=tsorvoro ;ati p)2( vunoužpoěbbnyzrzvaědopodbaduuorpívanádatrávěpoužp=)laropmet(ávosča1) : ( tylikaloníčotevypýtozéhípylněn a nap isínízáv itivyt.

Architektura procesorů Intel a některé nové rysy

10

Skrytá paměť (cache)

ižon[Rans=]ikolbs=ů,upstaseňiaoc )sz,ilenýnhcaneč...,R[0,.  1m h−1]pamesadínm1odejusey(inožů(okblt) dohdisjuorsedělííř.d 1  řt knntcíth lodu.  2 k cíífmof: pínstsorýleCerda sjedulka)tabhashvocamupačaononnzezom )=heacecivat (ícavolytpzoráne

Velikost velikosti

datové B S je

části

Velikost a

skryté

paměti

struktura skryté paměti

se stupněm asociativity

C S

=

s

∙

B S

∙

h.

s

a

h

množinami

bloků

o

11