Principy počítačů I ZVYŠOVÁNÍ VÝKONU PROCESORŮ. Sériové zpracování. Pipeline. Úspora při použití pipeline. Problém 1: přístup k datům

2003/2004 ZS

RNDr. David Obdržálek

2003/2004 ZS


Principy počítačů I

Sériové zpracování

ZVYŠOVÁNÍ VÝKONU PROCESORŮ „Copak je po jméně? Co růží zvou – i zváno jinak vonělo by stejně.“ William Shakespeare

2003/2004 ZS


2003/2004 ZS

Pipeline


Úspora při použití pipeline Pipeline s k kroky, zpracování n instrukcí. Zrychlení:

S=

nk k + (n − 1)

Pro n>>k:

S →k

2003/2004 ZS


Zásadní problém • Pipeline zavádí paralelismus

2003/2004 ZS


Problém 1: přístup k datům • čtení dat z externí paměti způsobí zpoždění ve fázi fetch

• Bez ohledu na to, co se děje uvnitř, musí se procesor navenek tvářit striktně sekvenčně

1

2003/2004 ZS


2003/2004 ZS

Problém 2: datová závislost

load decode

1 2 i1 i2

3

4

i1(r2) i2(r4)

load op2

i1(r1)

store

5

6

7

8

9

–

–

i2(r3)

–

–

i2

i1(r3)

–

– i2(r5)

Loop: add $r3, $r2, $r1 sub $r6, $r5, $r4 beq $r3, $r6, Loop

i1 i2

load op1

execute

Problém 3: závislost skoků

r3 ← r2 + r1 r5 ← r4 – r3

add $r3, $r2, $r1 sub $r5, $r4, $r3


i1

2003/2004 ZS


2003/2004 ZS

Problém 4: skoky

paměť skoku

• skok si vynutí vyprázdnění pipeline • Řešení:

• Motorola MC88110: – cyklická paměť 32 instrukcí – při skoku se uloží 2 instrukce z větve – asociativní vyhledávání dle adresy

– multiple streams – look ahead / look behind buffer – delayed branch – branch prediction

2003/2004 ZS



zpoždění skoku • odložení skutečného skoku, dokud není zjištěna přesná adresa. Mezitím jsou vykonávány „neškodné“ instrukce • nutná spolupráce kompilátoru! • RISC 2, SPARC – 1 instrukce Mips X, Accel, CDC GaAs – 2 instrukce

2003/2004 ZS


predikce skoku • v instrukci uložena „nápověda“. Podle toho se instrukce načítají. Je-li nápověda správně, nedojde ke ztrátě. Je-li nápověda špatně, vyprázdní se pipeline, načte se správný obsah. • statická predikce – rozhodnutí bez znalosti skutečné historie průběhu – může dělat jak překladač, tak hardware: cykly obvykle skáčí na začátek, jen 1x neskočí

2

2003/2004 ZS


2003/2004 ZS


predikce skoku

Vývoj pipeline Superpipelining

• dynamická predikce

2003/2004 ZS

–


rozdělení kroků pipeline na menší → jednodušší → rychlejší (v singulárním případě: procesor s pipeline délky 5 je 5x rychlejší než procesor bez pipeline (pipeline délky 1)): MIPS R4000: 8 kroků: 1. Instruction Fetch (1st half) 2. Instruction Fetch (2nd half) 3. Register Fetch 4. Data Cache Access (1st half) 5. Data Cache Access (2nd half) 6. Tag Check 7. Write Back

2003/2004 ZS


Vývoj pipeline

Vývoj pipeline

Superscalar pipelining

Dynamic pipeline

– více paralelních částí pipeline: RISC System/6000: větvení (fork) po dekódování: •

různé cesty v pipeline pro integer a floating-point

– dnes někdy i více celých pipeline

2003/2004 ZS


Další zrychlování Simultánní multithreading

– přeplánování problematických částí: • • •

fetch and decode unit functional units (5-10) commit unit

2003/2004 ZS


Statistika užívání instrukcí skupina

zastoupení

přesuny dat

45,28%

• do pipeline se zavádějí instrukce různých vláken, které na sobě jistě nebudou závislé

řízení

28,73%

aritmetika

10,75%

Predikce hodnoty

porovnávání

5,92%

• Pozorování ukazuje, že instrukce Load zavede ve více než ½ případů stejnou hodnotu → budeme to předpokládat

logické operace

3,91%

posuny, rotace

2,93%

bitové operace

2,05%

I/O a ostatní

0,43%

3

2003/2004 ZS


2003/2004 ZS


Další pozorování

Výzkum DEC

• 56% konstant je v rozsahu ±15 (5 bitů) • 98% konstant je v rozsahu ±511 (10 bitů) • 95% podprogramů potřebuje pro předání parametrů méně než 24 bytů

V typickém programu bylo • použito 58% instrukční sady • pro 98% instrukcí stačilo pouhých 15% firmware

2003/2004 ZS


2003/2004 ZS

Změna priorit

MIPS

• Důraz na to, co je nejvíce potřeba a co trvá nejdéle • Implementace méně používaných instrukcí může zhoršit celkový návrh • Spolehnout se na vyšší jazyky a optimalizující kompilátory • Paměť je dnes rychlejší a levnější

2003/2004 ZS



CISC vs RISC • CISC – Coplex Instruction Set Computer (zpětné označení) • RISC – Reduced Instruction Set Computer

• 80. léta, John Hennessy – Stanford University • Stanford – silný v kompilátorech → vývoj procesoru, jehož architektura by vyjadřovala snížení kompilátoru na úroveň HW (místo obvyklého povyšování HW na úroveň SW)

2003/2004 ZS


Strategie návrhu RISCu • zjištění nejpoužívanějších instrukcí (simulace a analýza programů) • optimalizace datových cest pro tyto instrukce • přidání dalších instrukcí, pokud jsou rozumně využitelné a nezpomalí procesor • přesunutí komplexních činností do kompilátoru

4

2003/2004 ZS


2003/2004 ZS

CISC

Pokus o definici RISC • N.J.Davis:

• Proč se tedy vlastně vyvinuly? – (První stroje měly jednoduchou architekturu) – Cena HW klesla, cena SW stoupla – Přesun složitosti do HW usnadní programování – Méně instrukcí pro daný úkol znamená méně přístupů do (pomalé a drahé) paměti – Implementace pomocí mikrokódu se dá snadno změnit

2003/2004 ZS


– omezená a jednoduchá instrukční sada – velké množství obecných registrů – důraz na optimalizaci pipeline

• Colwell: – provádění instrukcí v 1 taktu – architektura load/store – hardwired design – relativně málo instrukcí a způsobů adresování – pevný formát instrukcí – větší význam kompilátoru

2003/2004 ZS

Charakteristické rysy pro RISC • • • • • • • • • • •

jedna instrukce na cyklus operace registr – registr architektura load – store malý počet a jednoduché adresovací režimy pevný formát instrukce malý počet a jednoduché instrukce velké množství registrů použití linky proudového zpracování (pipeline) zvláštní zpracování skoků hardwired návrh obvodového řešení silná závislost na kompilátoru

2003/2004 ZS




První procesory typu RISC Výzkumné systémy:

– MIPS (Stanford) – RISC 1, RISC 2 (Berkeley) – IBM-801

2003/2004 ZS


RISC – typičtí představitelé • Desktop/Server: – Alpha (Digital) – PA-RISC (Hewlett-Packard) – PowerPC (IBM + Motorola) – MIPS (Silicon Graphics) – SPARC (Sun Microsystems)

5

2003/2004 ZS


RISC – typičtí představitelé • Embedded systems: – ARM (Advanced RISC Machines) – Thumb (Advanced RISC Machines) – SuperH (Hitachi) – M32R (Mitsubishi) – MIPS16 (Silicon Graphics)


Alpha

MIPS I

PA-RISC 1.1

PowerPC

SPARC V8

1992

1986

1986

1993

1987

32

32

32

32

32

64 bits, flat

32 bits, flat

32 bits, flat

32 bits, flat

Aligned

Aligned

48 bits, segmented Aligned

Unaligned

Aligned

1

1

5

4

2

Page

Page

Page

Page

Page

8 KB

4 KB

4 KB

4 KB

8 KB

Memory mapped

Memory mapped Memory mapped Memory mapped Memory mapped

Integer registers 31 GPR (number, model, x 64 bits size)

31 GPR x 32 bits

31 GPR x 32 bits

32 GPR x 32 bits

31 GPR x 32 bits

Separate floating-point registers

31 x 32 or 31 x 64 bits

16 x 32 or 16 x 64 bits

56 x 32 or 28 x 64 bits

32 x 32 or 32 x 64 bits

32 x 32 or 32 x 64 bits

Floating-point format

IEEE 754 single, double

IEEE 754 single, IEEE 754 single, IEEE 754 single, IEEE 754 single, double double double double

2003/2004 ZS

Návrh procesoru • • • • • • •


Date announced Instruction size (bits) Address space (size, model) Data alignment Data addressing modes Protection Minimum page size I/O

Web Extension I: Survey of RISC Architectures

2003/2004 ZS

2003/2004 ZS


zvolit RISC nebo CISC?

pevná/proměnná délka instrukcí? pevný/proměnný počet a typ operandů? počet adresovacích režimů? mikrokód/hardwired řadič? stupeň paralelismu? důraz na vyšší programovací jazyky? schopnosti kompilátoru?

• Neexistuje jednoznačná odpověď! – Kvantitativní přístup: porovnat velikosti programů a rychlost provádění – Kvalitativní přístup: vyhodnotit podporu vyšších programovacích jazyků a schopnosti technologií – Problémy: • žádné dva procesory RISC a CISC nejsou přímo porovnatelné • není konečná sada testovacích programů • obtížné odlišit vliv HW a vliv kompilátoru

• (většina dnešních návrhů bere z obou kategorií)

2003/2004 ZS


Konvergence CISC a RISC

2003/2004 ZS


„Ideální RISC“ Hloubka linky

• od 80-let se technologie i znalosti změnily • mnohé techniky jsou používány procesory z obou táborů: • CISC – schopné vykonávat v 1 taktu více instrukcí, • RISC – se zlepšením technologií zbývá místo, vyplnění komplikovanějšími instrukcemi

• vznikají „post-RISC“ návrhy, kombinující oba přístupy s metodami, které nejsou použity v žádné z těchto kategorií (přesto si „RISC“ zachovává charakteristické vlastnosti)

Dekódování

•5

•1 • 16 • 32 • 64 • 128 • 256

128 • 32 •

64 •

Počet registrů

•3

•4 •

fix •

32 •

•5

•3 hw

var •

•7

•2 micro •

Délka instrukce

Adresovací mody

•1

micro+ nano •

64 •

• ¼ • spec. jednotka •½ • zpožděný skok

Počet instrukcí

•1 •2 •3

Větvení

CPI

Kiviatův graf The RISC Concept – A Survey of Implementations (1991)

6

2003/2004 ZS


2003/2004 ZS

Procesor SPARC (1)


Procesor SPARC (2) Hloubka linky

• původní návrh z procesorů RISC-I a RISC-II z university v Berkeley, • trojice čipů, • propojení s koprocesorem pro pohyblivou řádovou čárku, • rozdělení registrů do oken • tagované instrukce

2003/2004 ZS


Dekódování

•5

•3 •3

•4 hw

Délka instrukce

•7

•2 micro •

var •

Adresovací mody

•1

micro+ nano •

•

•1

•5

fix •

• • 32 • 64 • 128 • 256 • ¼ • spec. jednotka •½ • zpožděný skok 16

128 • 64 • 32 •

64 •

Počet instrukcí

•1

32 •

•2

Počet registrů

•3

Větvení

CPI

2003/2004 ZS

Procesor IBM RS/6000 (1)


Procesor IBM RS/6000 (2) Hloubka linky

• • • • • • •

harwardská architektura šířka vyrovnávací paměti instrukcí 128 bitů datová sběrnice 64 bitů vícenásobné jednotky dekódování některých operací mikrokódem !! speciální jednotka predikce větvení programu používá metodu přejmenování registrů

2003/2004 ZS


Procesor Intel 80860 (1)

Dekódování

•5

•3 •3

•4 hw

var •

•7

•2 micro •

Délka instrukce

Adresovací mody

•1

micro+ nano •

•

fix •

•5

128 • 64 • 32 •

64 •

•1

• 16 • 32 • 64 • 128 • 256 • ¼ • spec. jednotka •½ • zpožděný skok

Počet instrukcí

•1

32 •

•2

Počet registrů

•3

Větvení

CPI

2003/2004 ZS


Procesor Intel 80860 (2) Hloubka linky Dekódování

• • • • •

šířka slova 32 bitů šířka sběrnice s vyrovnávací pamětí 128 bitů hardwarové přejmenovávání registrů vícenásobné funkční jednotky speciální grafická jednotka

•5

•1 • 16 • 32 • 64 • 128 • 256

128 • 32 •

64 •

Počet registrů

•3

•4 •

fix •

32 •

•5

•3 hw

var •

•7

•2 micro •

Délka instrukce

Adresovací mody

•1

micro+ nano •

64 •

• ¼ • spec. jednotka •½ • zpožděný skok

Počet instrukcí

•1 •2 •3

Větvení

CPI

7

2003/2004 ZS


2003/2004 ZS

post-RISC


Přechod RISC – Post-RISC

• Rozdíl od superskalárních RISCů: – přidání ne-RISCových instrukcí (pro zvýšení výkonu) → architektura FISC (Fast Instruction Set Computer) – agresivní přerovnávání instrukcí v průběhu zpracování – „out-of-order execution,“ „speculative execution“ (odklon od závislosti na kompilátoru) – nové uspořádání, nové jednotky – větší míra paralelismu Beyond RISC – The Post-RISC Architecture (1996)

2003/2004 ZS


2003/2004 ZS

Nové komponenty: • • • •


Predecode unit, I-cache

predecode unit renaming registers reorder buffer retire unit

• instrukce načítány po blocích • částečné dekódování zjistí vlastnosti instrukcí a uloží je do vyrovnávací paměti instrukcí • dodatečné příznaky určují: – identifikaci skoků – typ potřebné exekuční jednotky – zda bude instrukce potřebovat paměť

„generic post-RISC“

2003/2004 ZS


záznam v I-cache

• ve vyrovnávací paměti uloženo:

2003/2004 ZS


fetch / flow • načítání z I-cache musí být chytré • záznam v I-cache ukazuje na další blok instrukcí • ukáže-li se odkaz jako špatný, je změněn

– blok instrukcí – historie skoků – predekódované příznaky – historie vykonávání bloku

8

2003/2004 ZS


2003/2004 ZS

decode / branch


Barvení instrukcí

• vlastní dekódování instrukce • rozdělení na dva proudy do doby, než je znám skutečný cíl skoku • „barvení instrukcí“

2003/2004 ZS


Výsledky z Branch Unit • Fetch/Flow Unit


Instruction Dispatch and Reorder Buffer • dekódované instrukce „čekají“ na provedení • k provedení dojde, jsou-li k dispozici

– aktualizace flow history – načtení správných instrukcí

– vstupní hodnoty – výstup – exekuční jednotka

• Branch/Decode Unit – aktualizace branch history

• Dispatch and Reorder Buffer • Completed Instruction Buffer

• přednost mají

– zahození instrukcí, které se nemají (neměly) vykonat

2003/2004 ZS

2003/2004 ZS


– starší instrukce – instrukce load

2003/2004 ZS

Datové závislosti při přerovnání • True data dependency – RAW (Read after Write) – výstup instrukce je použit jako vstup následující

• Output dependency – WAW (Write after Write) – dvě instrukce zapisují na stejné místo


Eliminace WAW MOVE r3, r7 ADD r3, r4, r5 MOVE r1, r3 …

MOVE r3, r7 ADD r8, r4, r5 MOVE r1, r8 …

• Anti-dependency – WAR (Write after Read) – zatímco jedna instrukce zpracovává data, další instrukce tato data změní

(WAW a WAR lze vyřešit přeznačením)

9

2003/2004 ZS


2003/2004 ZS


out-of-order execution

execution units • podobně jako u RISC • jednotky, které nepočítají v 1 cyklu, použijí pipeline • jednotky load/store obvykle umožňují rozpracovat více přístupů najednou

2003/2004 ZS


2003/2004 ZS


Completed Instruction Buffer, Retire Unit • ukládání vykonaných instrukcí, spolu s: – příznakem vygenerované výjimky – mapováním (přejmenováním) použitých registrů

• Retire unit odebírá instrukce z bufferu: – v takovém pořadí, v jakém by byly sekvenčně zpracovány – může „uvolnit“ v 1 taktu více instrukcí

Problém – výjimky • při výskytu výjimky musí procesor „zastavit činnost“ na tomto místě – instrukce, které jsou po této instrukci, nesmí ovlivnit stav stroje – nesmí existovat nezpracované instrukce ležící před touto instrukcí – všechny výjimky způsobené předchozími instrukcemi jsou vyřízeny

„precizní přerušení/výjimka“

2003/2004 ZS


RISC vs post-RISC • RISC: výkon je dán stupněm paralelismu • post-RISC: výkon je dán počtem najednou odkládaných instrukcí

2003/2004 ZS


Proudová linka (u post-RISC) Fetch

Decode

Vyrovnávací paměť jednotky přidělování instrukcí

Execute

Vyrovnávací paměť odkládací jednotky

Instrukce

Retire

10

2003/2004 ZS


2003/2004 ZS

Příklady procesorů post-RISC • procesory s ojedinělými znaky post-RISC – DEC Alpha 21164, SUN UltraSPARC

• procesory s typickou organizací post-RISC – IBM PowerPC 604, MIPS R10000, HP PA-8000

• smíšené organizace – Intel Pentium P6 („interesting blend of architectures“)

2003/2004 ZS


DEC Alpha 21164 • • • •

používá pouze minimum z návrhu post-RISC vysoký základní hodinový kmitočet predikce skoku → tabulka historie skoků obecně nepoužívá spekulativního provádění instrukcí (pouze některé mimo pořadí) • nemá možnost precizního přerušení

2003/2004 ZS

DEC Alpha 21164 21164

Instruction Cache

Integer Instruction Fetch Decode Branch

Integer FP FP

Slučovací logika Vyrovnávací paměť dat

Bus Interface Unit

2003/2004 ZS


SUN UltraSPARC 40-bit adresa

Paměť Cache 98 kB


Vnější vyrovnávcí paměť

128-bit data


• • • • • • • •

více RISC než Post-RISC instrukce v balíku po 4 v I-cache 2 záznamy pro branch history mezi fetch a dispatch je fronta 12 instrukcí některé instrukce odkládány out-of-order 2xINT ALU, 5xFP ALU 9 Load, 8 Store buffer fast context switch, traps, motion estimation

2003/2004 ZS

SUN UltraSPARC


MIPS R10000 • • • • • • •

„exceptionally Post-RISC“ zaměřený na grafiku a floating-point plně 4cestně superskalární architektura 64k dvoucestná cache „on chip“ tři plánovací fronty (pro 5 pipeline) nemá flow prediction, branch prediction klasické „shadow map“ – ukládání mapy registrů před skokem • „branch resume cache“ – ukládání instrukcí

11

2003/2004 ZS


2003/2004 ZS

MIPS R10000


HP PA-8000 • • • •

(PA-7000 typický RISC, PA-8000 zcela jinak) IRB pro 56 instrukcí (28 aritm. + 28 memory) velká SRAM cache „off chip“ plně asociativní BTAC (Branch Target Address Cache) pro predikci toku instrukcí (32) – inside CPU • možnost vypnout dynamic branch prediction

2003/2004 ZS


2003/2004 ZS

HP PA-8000


Procesor PowerPC 604 • čtyřcestný superskalární návrh • predikční mechanismus – vyrovnávací paměť cílových adres (BTAC) – tabulka historie větvení (BHT, dvoubitová)

• přejmenovávané registry, registry podmínkových kódů • rezervační stanice pro exekuční jednotky • speciální jednotka pro "branch-on-counter"

2003/2004 ZS


PowerPC 604

/ 64

Branch Processing Unit

/

BTAC

JTAG

Reservation Station (2 Entry)


32

Single Cycle Integer Unit

/

+-*/

/

+-*/

32

32

/

/

BHT


GPR File Rename Buffers (8)

Multiple Cycle Integer Unit

Load/Store Unit

/

Rename Buffers (8)

/

128


FPR File

64

64

/

Floating Point Unit +-*/

32

EA Calculation

Tags

32

16 Entry Reorder Buffer

• instrukční sada CISC interpretována mikrooperacemi na jádře post-RISC • implementován jako dva čipy na jedné podložce

Dispatch Unit

128

/

COMPLETION UNIT

Procesor Intel Pentium P6

IMMU

CTR

Rename Buffers

Instruction Queue (8 words)

Time Base

/


INSTRUCTION UNIT Fetcher

Clock Multiplier

2003/2004 ZS

128

16 kByte Cache

DMMU Finish Load Queue

/

32 Tags

16 kByte Cache

Bus Interface Unit

– stejný hodinový kmitočet – zvláštní sběrnice mezi procesorem a vyrovnávací pamětí

• třícestný superskalární návrh

32-bit Address Bus 64-bit Data Bus

12

2003/2004 ZS


Třícestný model procesoru P6

2003/2004 ZS


Bloková struktura procesoru P6 System Bus (External) L2 Cache

Bus Interface Unit Instruction Fetch Unit

Next IP Unit

Instruction Cache

Bus Interface Unit Simple Instruction Decoder

L1 I-Cache

Simple Instruction Decoder

Memory Reorder Buffer

Branch Target Buffer

Instruction Decoder Complex Instruction Decoder

Microcode Instruction Sequencer

L1 D-Cache Register Alias Table

Retirement Unit

Dispatch/ Execute Unit

Fetch/Decode Unit

Retire Unit

Reorder Unit (Instruction Pool)

Retirement Register File (IA Registers)

Data Cache Unit

Reservation Station

FP Unit

Instruction Pool

FP Unit

Integer Unit

Integer Unit

Memory Interface Unit

Internal Buses

2003/2004 ZS


Proudová linka v P6 Jednotka vyzvednutí instrukcí

Přejmenování registrů a změna uspořádání

Dekódování instrukcí

Port0

Odkládací jednotka

Port1 BTB0 BTB1

IFU0

IFU1

IFU2

ID0

ID1

RAT

ROB

RS

Port2

ROB

RRF

Port3 Port4

Členění proudové linky u procesoru P6 Dvě paralelní linky proudového zpracování PF

X1

D1

D2

EX

X2

WB

MR/W

2003/2004 ZS

WBF

Pohyblivá řádová čárka

Pevná řádová čárka

Mex

MW/M

M


Dekódování makroinstrukcí

Reservační stanice a exekuční jednotky Vyrovnávací paměť cílů větvení

2003/2004 ZS

WBM

MMX

• maximálně tři makroinstrukce/jeden cyklus • maximálně šest mikrooperací/jeden cyklus • makroinstrukce může být max. 7 bytů a dekóduje se : – operace registr/registr → 1 µop – operace load → 1 µop – operace store → 2 µop – operace read/modify/write → 4 µop

• složitější µop mají více než 4 µop a potřebují více cyklů na dekódování


Dataflow CPU vs Post-RISC

13

Principy počítačů I ZVYŠOVÁNÍ VÝKONU PROCESORŮ. Sériové zpracování. Pipeline. Úspora při použití pipeline. Problém 1: přístup k datům

Recommend Documents