Kvantitativní principy návrhu počítačů

Architektura poˇcítaˇcových systému˚ Kvantitativní principy návrhu poˇcítaˇcu˚

ˇ Ceské vysoké uˇcení technické v Praze Fakulta informaˇcních technologií Katedra poˇcítaˇcových systému˚

Aktualizace výukových materiálu˚ spolufinancována z Fondu rozvoje vysokých škol v rámci projektu cˇ . 1939/2012

ˇ (CVUT FIT)

Kvantitativní principy návrhu poˇcítaˇcu˚

BI-APS, 2012, cviˇcení 1

1 / 31

Trocha historie ˇ jak by vývoj mohl Velmi struˇcný historický pˇrehled. Odhadnete, pokraˇcovat. Implementaˇcní technologie: relé → elektronky → tranzistory → MOS → VLSI → ...? ˇ výpoˇcetní výkon: Kde je soustˇreden procesorová jednotka → poˇcítaˇc na stole → webový/aplikaˇcní server → cloud → grafická karta → ...? Zpusob ˚ programování: strojový kód → assembler → C, Pascal, BASIC... → C++, Java → komponenty, CASE nástroje → ...? Propojení poˇcítaˇcu: ˚ žádné → lokální síteˇ → Internet → mobilní data → ...?

ˇ (CVUT FIT)



2 / 31

Nedávná historie Procesor Intel Pentium 4 Prescott 3.4E GHz Uvedení na trh: Minimální velikost motivu (λ): Velikost cˇ ipu: Poˇcet tranzistoru: ˚ Poˇcet jader: Velikost cache: Frekvence hodin: Projektovaný ztrátový výkon (TDP):

ˇ (CVUT FIT)



3 / 31

Nedávná historie Procesor Intel Pentium 4 Prescott 3.4E GHz Uvedení na trh: Q2/2004 Minimální velikost motivu (λ): 90 nm Velikost cˇ ipu: 112 mm2 Poˇcet tranzistoru: ˚ 125 · 106 Poˇcet jader: 1 (2 vlákna) Velikost cache: 1 MB Frekvence hodin: 3,4 GHz Projektovaný ztrátový výkon (TDP): 105 W

ˇ (CVUT FIT)



3 / 31

Souˇcasnost Procesor Intel Xeon E7-8870 Uvedení na trh: Minimální velikost motivu (λ): Velikost cˇ ipu: Poˇcet tranzistoru: ˚ Poˇcet jader: Velikost cache: Frekvence hodin: Projektovaný ztrátový výkon (TDP):

ˇ (CVUT FIT)



4 / 31

Souˇcasnost Procesor Intel Xeon E7-8870 Uvedení na trh: Q2/2011 Minimální velikost motivu (λ): 32 nm Velikost cˇ ipu: 512 mm2 Poˇcet tranzistoru: ˚ 2, 6 · 109 Poˇcet jader: 10 (20 vláken) Velikost cache: 30 MB Frekvence hodin: 2,4 GHz (turbo max. 2,8 GHz) Projektovaný ztrátový výkon (TDP): 130 W

ˇ (CVUT FIT)



4 / 31

Souˇcasnost Grafický cˇ ip NVIDIA GK110 ˇ komerˇcneˇ dostupný cˇ ip“) („nejvetší Uvedení na trh: Minimální velikost motivu (λ): Velikost cˇ ipu: Poˇcet tranzistoru: ˚ Max. ztrátový výkon (TDP):

ˇ (CVUT FIT)



5 / 31

Souˇcasnost Grafický cˇ ip NVIDIA GK110 ˇ komerˇcneˇ dostupný cˇ ip“) („nejvetší Uvedení na trh: Q4/2012 Minimální velikost motivu (λ): 28 nm Velikost cˇ ipu: 550 mm2 Poˇcet tranzistoru: ˚ 7, 1 · 109 Max. ztrátový výkon (TDP): 300 W

ˇ (CVUT FIT)



5 / 31

ˇ Nekteré empirické zákony Moore’s law (1965): The number of transistors on a chip doubles annually. Rock’s law (Moore’s 2nd law): The cost of semiconductor tools doubles every four years. Machrone’s law (1984): The PC you want to buy will always be $5000. Metcalfe’s law: A network’s value grows proportionally to the number of its users squared. Wirth’s law: Software is slowing faster than hardware is accelerating

ˇ (CVUT FIT)



6 / 31

Mooruv ˚ zákon

ˇ (CVUT FIT)



7 / 31

Výkonnost poˇcítaˇcu˚

Nástup mikroprocesoru˚ – nejen vylepšení stávající technologie, ale ˇ zmena paradigmatu ˇ (CVUT FIT)



8 / 31

Výkonnost poˇcítaˇcu˚

Zpomalování výkonnosti pro jednovláknové programy? ˇ (CVUT FIT)



9 / 31

ˇ Casová složitost a výkonnost Vlak (Pendolino) vs. letadlo (ATR42): úkon stejný, ale ruzná ˚ doba Úkon = cesta Praha – Ostrava, nezáleží na poˇctu osob Doba cesty: tPendolino = 3 h, tATR42 = 1 h. 3 Letadlo je tPendolino tATR42 = 1 = 3 krát rychlejší. Výkonnost P(T ): inverzní hodnota doby T provedení 1 úkonu PT (T ) =

1 1 1 = = cˇ asová složitost 1 úkonu cesta PHA–OVA T

Poˇcítaˇcová analogie: úkon: provedení 1 programu doba: doba T provedení programu X je k krát rychlejší než Y ˇ výkonnost než Y X má k krát vetší ˇ (CVUT FIT)

⇐

k=


Ty PT (Tx ) = PT (Ty ) Tx BI-APS, 2012, cviˇcení 1

10 / 31

ˇ Casová složitost a propustnost Pendolino vs. ATR42: ruzná ˚ doba cesty a také ruzn ˚ eˇ veliký úkon Úkon = # pˇrepravených osob na trase Praha – Ostrava Pendolino: rP = 3333osob , ATR42: rA = 461osob h h ˇ Pendolino je rrPA = 111 = 2, 4 krát propustn ejší. 46 Výkonnost P(n, T ): n úkonu˚ za cˇ as T Pr (n, T ) =

# osob n c úkon = = = =r cˇ as. složitost cesta PHA–OVA T t

Poˇcítaˇcová analogie: úkon: ruzný, ˚ provedení n krát jednoho programu doba: doba T pro provedení úkonu ˇ než Y X je k krát propustnejší ˇ výkonnost než Y X má k krát vetší ˇ (CVUT FIT)

⇐

k=


Pr (nX , TX ) TY nX = Pr (nY , TY ) TX nY BI-APS, 2012, cviˇcení 1

11 / 31

ˇ Casová složitost a výkonnost Otázka k zamyšlení: Když na stejnou linku pˇridáme další dopravní prostˇredek stejného typu, ˇ jak se zmení: latence propustnost výkonnost

ˇ (CVUT FIT)



12 / 31

ˇ Casová složitost a výkonnost Otázka k zamyšlení: Když na stejnou linku pˇridáme další dopravní prostˇredek stejného typu, ˇ jak se zmení: latence ˇ nezmení, doba jedné cesty je stejná propustnost zdvojnásobí, za stejnou dobu pˇrepravíme 2x více osob výkonnost záleží, jak ji poˇcítáme, jestli z latence nebo propustnosti

ˇ (CVUT FIT)



12 / 31

Amdahluv ˚ zákon 1 Amdahluv ˚ zákon (AZ) = výpoˇcet výkonového zisku, cˇ ili zrychlení S, ˇ dosaženého vylepšením nejaké cˇ ásti poˇcítaˇce

S=

PNEW výkonnost pˇri využití vylepšení = výkonnost bez využití vylepšení POLD

nebo S=

doba výpoˇctu bez využití vylepšení T = OLD doba výpoˇctu pˇri využití vylepšení TNEW

ˇ úlohy na poˇcítaˇci Zrychlení S = cˇ íslo udávající, kolikrát je beh ˇ s vylepšením rychlejší oproti behu stejné úlohy na puvodním ˚ poˇcítaˇci

ˇ (CVUT FIT)



13 / 31

Amdahluv ˚ zákon 2 Definujeme: FE =

puvodní ˚ doba výpoˇctu zlepšené cˇ ásti úlohy ≤1 puvodní ˚ celková doba výpoˇctu

SE =

puvodní ˚ doba výpoˇctu zlepšené cˇ ásti úlohy >1 doba výpoˇctu zlepšené cˇ ásti úlohy

a

Doba výpoˇctu TNEW na vylepšeném poˇcítaˇci se bude skládat z: (1 − FE )TOLD = doba výpoˇctu té cˇ ásti úlohy, kterou nelze vylepšit FE T = doba výpoˇctu vylepšené cˇ ásti úlohy SE OLD ˇ (CVUT FIT)



14 / 31

Amdahluv ˚ zákon 3 Doba výpoˇctu TNEW na vylepšeném poˇcítaˇci: TNEW

FE = TOLD (1 − FE ) + SE

Celkové zrychlení SOVERALL odpovídající danému vylepšení:

SOVERALL =

ˇ (CVUT FIT)

TOLD = TNEW

1 (1 − FE ) +

FE SE



15 / 31

Amdahluv ˚ zákon – pˇríklad 1 ˇ obsahují sadu nových Procesory Intel Core (Westmere) a novejší instrukcí AES-NI, pomocí které lze operace šifrování a dešifrování v urˇcitých operaˇcních módech šifry AES urychlit až 10x. 1

Jaké bude celkové urychlení šifrovací aplikace, v níž šifrování a dešifrování algoritmem AES pˇredstavuje 70 % doby výpoˇctu (bez využití nových instrukcí)?

ˇ (CVUT FIT)



16 / 31

Amdahluv ˚ zákon – pˇríklad 1 ˇ obsahují sadu nových Procesory Intel Core (Westmere) a novejší instrukcí AES-NI, pomocí které lze operace šifrování a dešifrování v urˇcitých operaˇcních módech šifry AES urychlit až 10x. 1

Jaké bude celkové urychlení šifrovací aplikace, v níž šifrování a dešifrování algoritmem AES pˇredstavuje 70 % doby výpoˇctu (bez využití nových instrukcí)?

FE

= 0.7

SE

= 10

S =

1 0.3 +

ˇ (CVUT FIT)

0.7 10

=

1 = 2.702 0.37



16 / 31

Amdahluv ˚ zákon – pˇríklad 1 2

Jakou cˇ ást puvodní ˚ doby výpoˇctu musí pˇredstavovat šifrování, aby celkové zrychlení bylo dvojnásobné?

ˇ (CVUT FIT)



17 / 31

Amdahluv ˚ zákon – pˇríklad 1 2

Jakou cˇ ást puvodní ˚ doby výpoˇctu musí pˇredstavovat šifrování, aby celkové zrychlení bylo dvojnásobné?

1

S =

(1 − FE ) + 1

2 =

(1 − FE ) + FE

ˇ (CVUT FIT)

FE SE FE 10

= 0.55



17 / 31

Amdahluv ˚ zákon – pˇríklad 2 Pro FP výpoˇcty v poˇcítaˇcové grafice se cˇ asto používá operace odmocniny FPSQRT a výkonnost procesoru˚ pro grafiku je na jejím ˇ silneˇ závislá. efektivním provádení Pˇredpokládejme, že FPSQRT zabírá 20% a všechny FP operace zabírají 50% doby výpoˇctu kritické zkušební úlohy pro grafiku. Úkolem ˇ je rozhodnout, zda je výhodnejší: 1

ˇ instrukce FPSQRT 10x zrychlit provádení

2

ˇ všech FP instrukcí 1.6x zrychlit provádení

ˇ (CVUT FIT)



18 / 31

Amdahluv ˚ zákon – pˇríklad 2 ˇ Rešení: 1

SFPSQRT =

2

SFP =

1 0.2 (1 − 0.2) + 10 1

(1 − 0.5) +

0.5 1.6

=

=

1 = 1.22 0.82

1 = 1.23 0.8125

ˇ 2. možnost je o neco ˇ málo rychlejší než 1. Záver:

ˇ (CVUT FIT)



19 / 31

Amdahluv ˚ zákon – pˇríklad 3 Pˇredpokládejme, že jsme vylepšili urˇcitý režim cˇ innosti poˇcítaˇce s faktorem zrychlení 10. Vylepšený režim se používá v 50% cˇ asu ˇ reno jako procentuální podíl na celkové dobeˇ výpoˇctu na výpoˇctu, meˇ poˇcítaˇci s vylepšeným režimem. Jaké je celkové zrychlení a jaký je podíl urychlované cˇ ásti výpoˇctu na celkové puvodní ˚ dobeˇ výpoˇctu? Pozn.: Pˇripomínáme, že do Amdahlova zákona vstupuje podíl puvodní ˚ cˇ ásti doby výpoˇctu, který lze vylepšit.

ˇ (CVUT FIT)



20 / 31

Amdahluv ˚ zákon – pˇríklad 3 Pˇredpokládejme, že jsme vylepšili urˇcitý režim cˇ innosti poˇcítaˇce s faktorem zrychlení 10. Vylepšený režim se používá v 50% cˇ asu ˇ reno jako procentuální podíl na celkové dobeˇ výpoˇctu na výpoˇctu, meˇ poˇcítaˇci s vylepšeným režimem. Jaké je celkové zrychlení a jaký je podíl urychlované cˇ ásti výpoˇctu na celkové puvodní ˚ dobeˇ výpoˇctu? Pozn.: Pˇripomínáme, že do Amdahlova zákona vstupuje podíl puvodní ˚ cˇ ásti doby výpoˇctu, který lze vylepšit.

(1 − FE ) =

FE 1 1 10 ⇒ FE = = = = 0.91 1 1 SE 11 1 + SE 1 + 10 S=

ˇ (CVUT FIT)

1 (1 − FE ) +

FE SE

=

11 = 5.5 2



20 / 31

CPU výkonnostní rovnice Výkonnost CPU, vyjádˇrená pomocí doby TCPU (prg), po kterou jednotka CPU vykonává program prg, je P(TCPU (prg)) =

1 TCPU (prg)

Všechny poˇcítaˇce používají hodiny s konstantní frekvencí ⇒ cykly (ticks, clock ticks, clock periods, cycles, clock cycles). Rychlost hodin se udává jako: doba trvání hodinového cyklu (clock period) - TCLK , nebo frekvence taktu˚ (clock rate) - fCLK

fCLK =

ˇ (CVUT FIT)

1 TCLK



21 / 31

CPU výkonnostní rovnice 2 Doba CPU pro vykonání daného programu prg je CPU výkonnostní rovnice TCPU (prg) = TCLK × CycCPU (prg) = (1/fCLK ) × CycCPU (prg) CycCPU (prg) = # hodinových cyklu˚ CPU pro provedení programu prg. Pokud známe poˇcet instrukcí IC (instruction count) pro provedení ˇ programu prg, mužeme ˚ vypoˇcítat CPI = prum ˚ erný poˇcet hodinových cyklu˚ na instrukci (clock cycles per instruction), nebo pˇrevrácenou hodnotu IPC (instructions per clock cycle). CPI(prg) =

ˇ (CVUT FIT)

1 CycCPU (prg) = IPC(prg) IC(prg)



22 / 31

CPU výkonnostní rovnice 3 ˇ Doba CPU pro vykonání daného programu prg s promennými IC a CPI je CPU výkonnostní rovnice TCPU (prg) = IC(prg)×CPI(prg)×TCLK = IC(prg)×CPI(prg)×(1/fCLK ) ˇ ricích jednotek dostáváme Po pˇrevedení komponentu˚ této rovnice do meˇ

instrukce hod. cyklus sekunda sekunda × × = = TCPU (prg) program instrukce hod. cyklus program

Rozklad TCPU (prg) demonstruje závislost TCPU (prg) na 3 parametrech: 1

hodinový cyklus TCLK – hodinová frekvence fCLK

2

CPI = # hodinových cyklu˚ na jednu instrukci daného programu prg

3

IC = # instrukcí daného programu prg

ˇ (CVUT FIT)



23 / 31

Závislost parametru˚ TCPU ˇ Pokud se nekterý z parametru˚ zlepší o k %, pak se zlepší o k % i TCPU . Parametry TCLK , CPI, IC jsou provázány:

Program Pˇrekladaˇc Architektura instrukˇcního souboru (ISA) Organizace CPU Technologie CPU

IC • • •

CPI • • • •

TCLK

• • •

• – pˇrímý vliv • – není souˇcástí systému • – nepˇrímý, zprostˇredkovaný vliv

ˇ (CVUT FIT)



24 / 31

ˇ CPU výkonnostní rovnice 1 Pˇresnejší ˇ metrika: Pˇresnejší CycCPU (prg) =

n X

(ici × cpii )

i=1

TCPU (prg) =

n X

! ici × cpii

× TCLK

i=1

kde ici = # provedení instrukcí i programu prg, ˇ cpii = prum ˚ erný # hodinových cyklu˚ na instrukci i, n = # instrukcí v architektuˇre instrukˇcního souboru (ISA Instruction Set Architecture). ˇ (CVUT FIT)



25 / 31

ˇ CPU výkonnostní rovnice 2 Pˇresnejší ˇ Prum ˚ erné CPI n X

CPI(prg) =

(ici × cpii )

i=1

IC(prg)

=

n X i=1

ici × cpii IC(prg)

ˇ cpii zahrnuje vliv cˇ ekacích stavu, ˚ výpadku˚ vnitˇrní skryté pameti atd. ˇ rit a poˇcítat (v nekterých ˇ cpii lze meˇ pˇrípadech) ˇ Dále je uveden pˇríklad, kde prum ˚ erná hodnota CPI je vypoˇcítána na základeˇ znalosti IC a hodnot: ici = # instrukcí typu ALU, Load, Store a Branch ˇ cpii prum ˚ erná hodnota pro instrukce typu ALU, Load, Store a Branch ˇ (CVUT FIT)



26 / 31

ˇ CPU výkonnostní rovnice – pˇríklad Pˇresnejší Pˇríklad typického mixu instrukcí RISC procesoru: Instrukce ALU Load Store Branch CPI

ˇ (CVUT FIT)

ici /IC 0.5 0.2 0.1 0.2

cpii 1 5 3 2

(ici /IC) × cpii ? ? ? ? ?


% cˇ as ? ? ? ?


27 / 31


ˇ (CVUT FIT)

ici /IC 0.5 0.2 0.1 0.2

cpii 1 5 3 2

(ici /IC) × cpii 0.5 1 0.3 0.4 2.2


% cˇ as 23 % 45 % 14 % 18 %


27 / 31


ici /IC 0.5 0.2 0.1 0.2

cpii 1 5 3 2

(ici /IC) × cpii 0.5 1 0.3 0.4 2.2

% cˇ as 23 % 45 % 14 % 18 %

Otázky: 1

Jakým zpusobem ˚ se urychlí celkový výpoˇcet, pokud vylepšením ˇ klesne cpiLoad na 2? datové vnitˇrní skryté pameti

2

Pˇredchozí zlepšení porovnejte s použitím vylepšení predikce skoku, které zmenší cpiBranch na 1.

3

Co se stane, když budou 2 ALU instrukce vykonávány najednou? ˇ (CVUT FIT)



27 / 31

ˇ CPU výkonnostní rovnice – pˇríklad Pˇresnejší IC · CPIOLD · TCLK T CPIOLD ˇ Rešení: Využijeme, že S = OLD = = TNEW IC · CPINEW · TCLK CPINEW Alternativneˇ lze využít spoˇcítané podíly na dobeˇ výpoˇctu a dosadit pˇrímo do Amdahlova zákona Tedy: 1

2

3

2.2 = 1.38 1.6 2.2 S2 = = 1.05 2.1 2.2 S3 = = 1.13 1.95 S1 =

ˇ (CVUT FIT)



28 / 31

ˇ rení výkonnosti – MIPS Meˇ ˇ rení výkonnosti jednotkami MIPS: Definice meˇ MIPS =

IC TCPU ×106

=

IC IC×CPI×TCLK ×106

=

fCLK CPI×106

= [106 × instr ./s]

MIPS závisí na: ISA a programu, nebot’ CPI závisí na programu, mixu instrukcí Dusledek: ˚ výkonnost vyjádˇrena v jednotkách MIPS je závislá na programu, i když se tato závislost cˇ asto neuvádí Uvažujte úlohu, která má 1 955 789 FP operací a) ˇrešena na procesoru bez FP instrukcí trvá 136 ms, CPIa = 6 b) ˇrešena na procesoru s FP instrukcemi trvá 11 ms, CPIb = 10 Kolik je poˇcet provedených instrukcí ICa a ICb ? Kolik instrukcí v pˇrípadeˇ a) je tˇreba na jednu FP operaci? Kolik je MIPSa a MIPSb ?

ˇ (CVUT FIT)



29 / 31

ˇ rení výkonnosti – MIPS Meˇ ˇ Rešení: Pˇredpokladáme, že TCLK stejné pro a) i b). Potom z rovnice pro TCPU v pˇrípadeˇ b) dostáváme: TCLK = 0.56 ns Dále pˇredpokládáme, že 1 FP instrukce = 1 FP operace. Potom z rovnice pro TCPU v pˇrípadeˇ a) získáme ICa = 40 301 106, pro vykonání 1 FP operace tudíž potˇrebujeme cca 20 instrukcí procesoru a. MIPSa = 296 MIPSb = 177

ˇ (CVUT FIT)



30 / 31

Úkoly na doma 1

Latence vs. propustnost Jsou dveˇ horské chaty, jedna na kopci, druhá pod kopcem. Jejich vzdálenost je 10 km. Je tˇreba mezi nimi pˇrenášet data. ˇ a porovnejte latenci a propustnost techto ˇ Spoˇctete dvou variant: I I

2

Mikrovlnný spoj s rychlostí 10 Mbit/s. Bernardýn, který ve váˇcku na krku nese 10 disku˚ DVD, každý s ˇ kapacitou 4,7 GB. Bernardýn behá rychlostí 20 km/h.

Ztrátové teplo ˇ a porovnejte vyzaˇrované teplo na jednotku plochy Spoˇctete (W/cm2 ) pro: I I

Grafický cˇ ip GK110, TDP 300W, plocha cˇ ipu 550 mm2 . ˇ plotýnky 19 cm, pˇríkon 2 kW. Elektrický vaˇriˇc, prum ˚ er

ˇ (CVUT FIT)



31 / 31

Kvantitativní principy návrhu počítačů

Recommend Documents