Osnova přednášky Procesory využívající ILP. Dynamická predikce skoku. Zpracování komplexních instrukcí v pipeline

Osnova přednášky ° Procesory využívající ILP ° Dynamická predikce skoku

Pokročilé architektury procesorů II. Dynamická predikce skoku a plánování instrukcí Spekulativní provádění instrukcí Pipelining CISC procesorů a přesné přerušení

° Zpracování komplexních instrukcí v pipeline

° Dynamické plánování instrukcí ° Spekulativní provádění instrukcí ° Skutečné procesory – kombinace těchto technik

Architektura počítačů

Procesory využívající ILP

Zpětná kompatibilita a vysoká výkonnost ?

° Superpipelinové procesory

° Řešení založené na překladači nepomohou tam, kde máme velké množství programů, kde rekompilace není pravděpodobná či vůbec možná

• Velký počet stupňů pipeline umožňuje dosáhnout krátkého Tclk • CPI bývá horší v důsledku latencí v pipeline a paměťovém subsystému ° Statické superskalární procesory (static, in-order superscalar) • Zpracovávají více instrukcí paralelně ale v programovém pořadí • Typická šířka 3-4 instrukce • Velmi závislé na kvalitním překladači ° VLIW procesory • Instrukce obsahuje více paralelních operací • Hazardy detekuje a řeší překladač (téměř výlučně) • Šířka instrukcí typicky 6-10 paralelních operací ° Dynamické superskalární procesory (dynamic, out-of-order superscalar) • Zpracovává více instrukcí paralelně i mimo programové pořadí • Dnes typicky podporuje spekulativní provádění instrukcí za skokem

Snížení IC – VLIW (více paralelních operací v jedné instrukci)

Snížení T clk – superpipelining (více stupňů pipeline) a rychlejší technologie

TCPU= IC * (CPIpipe_ideal + Stalls Per Instr) * Tclk

° Problém přerušení u proudově pracujícího procesoru

Ing. Miloš Bečvář


Zvýšení výkonnosti – ILP techniky

° Zvětšení šířky pipeline (superscalar) nebo hloubky (superpipeline) zvyšují Stalls Per Instruction (SPI)

Snížení CPIpipe_ideal pomocí paralelním prováděním více instrukcí – superskalární proc. Překrytí pozastavování (stallů) užitečným výpočtem – dynamické plánování, dynamická predikce skoku, spekulativní provádění instrukcí


Osnova přednášky ° Procesory využívající ILP ° Dynamická predikce skoku ° Zpracování komplexních instrukcí v pipeline

° Potřebujeme HW techniky na snížení SPI =>Potřebujeme predikci skoku ke snížení pozastavování kvůli skokům => Potřebujeme překrývat pozastavování kvůli RAW hazardům užitečným výpočtem jiných instrukcí – provádění instrukcí mimo pořadí (dynamické plánování) => Potřebujeme pokračovat vykonávat instrukce i když všechny hazardy nebyly ještě rozpoznány a vyřešeny - spekulativní provádění instrukcí

° Problém přerušení u proudově pracujícího procesoru ° Dynamické plánování instrukcí ° Spekulativní provádění instrukcí ° Skutečné procesory – kombinace těchto technik

Tyto techniky snižují CPI (zvyšují IPC=1/CPI) ale mohou zvýšit Tclk

a někdy i spekulativní provádění Load/Store instrukcí Architektura počítačů



Predikce Skoku

Dynamická predikce skoku

FRONTA INSTR. IF

ID

RF

EX1

1-bitová Branch History Table (BHT) v Pipeline

° Predikce může být “Statická” (v době překladu, zakódována v instrukci) nebo “Dynamická” (za běhu v HW) EXN

Instruction Fetch Stage

WB

° Predikce je užitečná pouze pokud cílová adresa skoku je známa dříve než výsledek podmínky (to platí pro nejčastější PC-relativní skoky) Instr. Fetch

Instr. Decode

Frontend Pipeline

Reg. Fetch

Execute Stages

Write Back

Backend Pipeline

U SUPER-SUPER procesorů je problém s latencí skoku. Nelze to vyřešit rozšířením delay slotu (to je častým řešením u VLIW) a proto se používá PREDIKCE skoku. Frontend načítá instrukce podle predikce a ukládá je do fronty. Backend provádí instrukce a verifikuje predikci. V případě chybné predikce vypláchneme všechny chybně načtené instrukce z pipeline (včetně zmíněné fronty) Penalizace za chybnou predikci skoku = délka pipeline Pokud instrukce za skokem jsou provedeny dříve než je ověřena jeho predikce, hovoříme o tzv. spekulativním provádění instrukcí.

1-bitová Branch History Table • BHT indikuje zdali skok naposledy byl nebo nebyl proveden • Kompletní adresa PC není kontrolována u BHT (s chybnou predikcí se počítá) ° Problém: v cyklu, 1-bitová BHT bude mít dvě chybné predikce (průměrný cyklus má 10 iterací => 20 % neúspěšnost predikce): • V poslední iteraci (BHT predikuje pokračování cyklu místo ukončení) • V první iteraci když cyklus provádíme znovu (BHT predikuje ukončení cyklu místo pokračování)

LOOP:

Not Taken Not Taken instr_before_loop Predict Predict Taken Not ………. Taken ………. Taken ………. Looping Taken ………. BNEZ R1, LOOP Graf přechodů jednobitové predikce skoku instr_after_loop

Next time executing this code including loop Architektura počítačů

31

31

PC

PC

+4

° Je dynamická predikce skoku lepší než statická ?

PC (11:0) 12

- Zdá se, že ano. Nejlepší statická predikce skoku na bázi profilování kódu dosahuje přesnosti kolem 90 % pro FP programy a 70 - 90 % for celočíselné programy (měření SPEC). To není dostatečné pro superskalární procesory. - Dynamické prediktory často vyžaduje „zahřívací“ dobu než se stabilizuje na správné predikci. Statická predikce (je-li správná) tuto nevýhodu nemá.

0


2-bitová Branch History Table

32

31

Instruction Cache

Instruct. Decode

IR

T

(10) Predict Weakly Taken

T

NT

(01) Predict Weakly Not Taken

T

(00) Predict Strongly Not Taken

“Saturační čítač” NT

T

(10) Predict Weakly Taken

32

(01) Predict Weakly Not Taken

NT

T

° Agresivnější technikou je predikce cílové adresy skoku založené na Branch Target Address Caches (BTAC), Branch Target Instruction Caches (BTIC) a Return Address Stack (RAS) – umožňuje implementovat tzv. zero cycle branches

(00) Predict Strongly Not Taken

=> Vysvětlení BTAC, BTIC a RAS je v doplňkovém výukovém materiálu (pro zájemce).

NT T

“Hystereze”

Branch Target Address

° Pokročilé procesory kombinují několik technik predikce k docílení více než 90 % úspěšnosti predikce skoku

T NT

+

° Nevýhoda predikce skoku je nutné zpoždění kvůli dekódování instrukce a výpočet cílové adresy skoku (ztrácíme i při úspěšné predikci nejméně jeden takt a neumíme předpovídat počítané skoky – instrukce JR)

NT

(11) Predict Strongly Taken

Branch Displacement

Shrnutí dynamické predikce skoků

T

(11) Predict Strongly Taken

0

It is a branch

° 2-bitový prediktor je základem složitějších technik predikce využívající lokální a globální historii skoků

° Dvě implementační varianty (výkonnost podobná).

NT

Taken / Not Taken (1 bit)


° Řešení: 2-bitová schemata kde se predikce mění až po dvou chybných predikcích

NT

BHT 4096 x 1 bit

Change PC !

0

16

Dynamická predikce je jedinou možností pokud nemůžeme změnit ISA a chceme vyšší výkonnost ze starých programů, které nelze rekompilovat.


° Nižší bity PC adresují tabulku 1-bitových hodnot

Instruction Decode Stage Pipeline Registers (IF/ID)

Nevýhoda 2-bitového prediktoru vůči 1-bitovému - delší doba „zahřívání“ Architektura počítačů


Osnova přednášky

Přidání komplexnějších instrukcí k DLX

° Procesory využívající ILP

ID stage LW Rd, (Rs+Rt)

Chceme přidat následující instrukce k DLX ° Dynamická predikce skoku 1. LW Rd, (Rs + Rt)

Reg(Rd)=Mem(Reg(Rs)+Reg(Rt))

2. SW (Rs + Rt), Rd

Mem(Reg(Rs)+Reg(Rt))=Reg(Rd)

3. LW Rt, Imm(Rs)!

Reg(Rt)=Mem(Imm+Reg(Rs)); Reg(Rs)=Reg(Rs)+Imm

4. SW Imm(Rs)!,Rt

Mem(Imm+Reg(Rs)) =Reg(Rt); Reg(Rs)=Reg(Rs)+Imm

° Zpracování komplexních instrukcí v pipeline ° Problém přerušení u proudově pracujícího procesoru ° Dynamické plánování instrukcí ° Spekulativní provádění instrukcí

Přidané instrukce v DLX pipeline

° Skutečné procesory – kombinace těchto technik

busA= Reg[Rs] busB= Reg[Rt] SW Rd, (Rs + Rt) busA=Reg[Rs] busB=Reg[Rt] ??? = Reg[Rd] LW Rt, Imm(Rs)! busA= Reg[Rs] ImmExt = Imm SW Imm(Rs)!, Rt busA = Reg[Rs] busB = Reg[Rt] ImmExt<= Imm

EX stage

MEM stage

WB stage

S= busA + busB

M=Mem(S)

Reg[Rd]=M

S= busA + busB

Mem(S) =???

-

S = busA + ImmExt

M=Mem(S)

S = busA + ImmExt

Mem(S)=busB

Reg[Rt]=M Reg[Rs]=S Reg[Rs]=S

1.a 4. instrukce může být přidána do procesoru beze změny struktury pipeline. Instrukce SW Rd, (Rs + Rt) vyžaduje tři čtecí porty ve stupni ID Instrukce LW Rt, Imm(Rs)! vyžaduje dva zápisové porty ve stupni WB. Tyto instrukce jsou užitečné, ale ne tak časté aby se vyplatilo měnit kvůli nim pipeline. Řešením je rozbít tyto instrukce na sekvenci dvou mikroinstrukcí .


Rozbití instrukcí na mikroinstrukce SW (Rs + Rt), Rd

nahradíme při dekódování sekvencí


Provádění „komplexních“ instrukcí v pipeline

LW Rt, Imm(Rs)!

Reg(R32)=Reg(Rs)+Reg(Rt) Mem(Reg(R32))<=Reg(Rt) nahradíme při dekódování sekvencí

1. addi Rs, Rs, Imm 2. lw Rt, (Rs)

Reg(Rs)=Reg(Rs)+Imm Reg(Rt)=Mem(Reg(Rs))

Mikroinstrukce jsou v pipeline přímo proveditelné, R32 je programátorovi nepřístupný registr využívaný mikroinstrukcemi (tzv. microarchitecture scratch-pad register). CISC procesory jsou charakteristické existencí takovýchto registrů. Výsledné instrukce budou provedeny ve dvou taktech. Architektura počítačů

Pipelining CISC processorů ° Přímý pipelining komplexních instrukcí je obtížný

IF

SW (R1+R2), R3

ID

add R32, R1, R2

1. add R32, Rs, Rt 2. sw (R32), Rt


ID

EX

MEM

° Nativní CISC pipeline se vyznačuje vícetaktovými stupni (Pokud je třeba, stráví instrukce v daném stupni více taktů).

WB

forwarding of R32

sw (R32), R3

ADD R6, R4, R5

IF stall

IF

EX

MEM

ID

EX

WB

MEM

WB

Komplexní instrukce stráví více taktů ve stupni ID - V každém taktu je „emitována“ jedna mikroinstrukce Jednoduché RISC instrukce jsou „přeloženy“ na právě jednu mikroinstrukci. Dekodér ve stupni ID již musí být sekvenční obvod a procesor musí obsahovat další registry (pro implementaci komplexních instr.).

Tato technika je používána např. v procesorech PowerPC. Architektura počítačů

° Komplexní adresační módy a dekódování => dodatečná ALU pro výpočet efektivní adresy (Instrukce typu register-memory) Register Memory Pipeline: Fetch – Decode- Register Fetch – Address Calculation - Memory – Execute – Write Back) ° Složitá detekce hazardů, forwarding (instrukce čtou a zapisují data v průběhu provádění) ° Složité řešení přesného přerušení (schopnost přerušení a restartu uprostřed komplexní instrukce) ° Používaná řešení jsou unikátní pro každý CISC procesor ° Alternativou je rozbití komplexních instrukcí do mikroinstrukcí a implementace pipeliningu na úrovni mikroinstrukcí. Architektura počítačů

Proudový CISC: pipelining mikroinstrukcí Frontend Pipeline Prediction and Fetch Control

Flush IQueue

Control Memory (µInstructions)

µP C

PC

Instruction Cache (unif. Cache)

Instr. Queue

Comb. Log. S1

Comb. Log. S2

Instruction Decoder and µSequencer

µInstructions = µOperations = RISC-like instr.


Instrukce Dekódování

• Vertikální mikroinstrukce připomínají RISC instrukce • Mikronstrukce jsou vykonávány pomocí “RISC-like” pipeline

Osnova přednášky ° Procesory využívající ILP ° Dynamická predikce skoku ° Zpracování komplexních instrukcí v pipeline ° Problém přerušení u proudově pracujícího procesoru ° Dynamické plánování instrukcí ° Spekulativní provádění instrukcí ° Skutečné procesory – kombinace těchto technik

• Tento přístup je základem implementace moderních superskalárních CISC procesorů firem Intel i AMD. Architektura počítačů

Sekvenční zpracování instrukcí - Základní cyklus Načtení

mikronstrukci protože komplexní instrukce se vyskytují v programech zřídka.)

• Tento přístup byl zvolen u pozdějších modelů CISC počítačů VAX, IBM360, M68030 a též i486 a všechny novější x86.

Comb. Log. S3

Microinstruction Pipeline = similar to RISC pipeline (“Backend Pipeline”)

Branches, Calls, Returns, ...

Proudově pracující CISC procesory • Instrukce jsou “překládány” na sekvence jedné či více mikroinstrukcí. (CISC instrukce odpovídá obvykle jedné


Sekvenční sémantika vs proudové zpracování

Příklady přerušení (výjimek)

Sekvenční sémantika:

Požadavky na korektnost provádění programu

° Žádost V/V zařízení o obsluhu (I/O device request)

° Procesor zpracovává instrukce sekvenčně v programovém pořadí.

1. Program vypočítá správný výsledek (v souladu se sekvenční sémantikou - stejný jako na procesoru bez pipeliningu)

° Volání služeb OS (Supervisor Call SVC)

° Zpracování instrukcí se nepřekrývá.

2. Program generuje stejná přerušení (výjimky) Stav procesoru při přerušení je konzistentní se sekvenční sémantikou provádění instrukcí (stejný jako na procesoru bez pipeliningu )

Instrukce

° Běh programu může být přerušen pouze na hranici mezi instrukcemi Provedení

Provedení

Instrukce #1

Instrukce #N Test Přerušení HW obsluha Přerušení


Splnění požadavků na proudově pracujícím procesoru

° Trasování programu, breakpoint ° Aritmetické přerušení – přeplnění, podtečení, dělení nulou … ° Výpadek stránky (Page Fault) ° Nezarovnaný přístup k paměti (Misaligned Memory Access)

Ad 1: Instrukce mohou být zpracovávány proudově pokud zabráníme datovým, řídícím a strukturním hazardům. T.j. respektujeme datové a řídící závislosti v programu.

° Porušení ochrany paměti (Memory Protection Fault)

Ad 2: Splnění tohoto požadavku na proudově pracujícím procesoru není obecně zaručeno. Procesor, který má tuto vlastnost je schopen tzv. přesného přerušení (precise interrupt, precize exception).

° Chyba HW – parita, ECC chyba, pokles úrovně napájení (Machinecheck exception, power down, brownout)


° Nedefinovaná instrukce (Undefined opcode)


Přerušení u proudově pracujícího procesoru

Klasifikace typů přerušení – 5 parametrů

Zdroje vnitřních přerušení v celočíselném DLX • K přerušení může dojít v každém taktu

° Synchronní x Asynchronní vůči běhu programu - synchronní způsobené instrukcí (vnitřní přerušení)

• Současně může dojít k přerušení z více zdrojů

- asynchronní způsobené externím HW (vnější přerušení)

• Pořadí výskytu přerušení nemusí odpovídat pořadí instrukcí v programu

• Výpadek stránky, nezarovnaný přístup, chyba ochrany paměti

° Žádané uživatelem x Vynucené • Stav procesoru nemusí být v okamžiku přerušení konzistentní se sekvenční sémantikou vykonávání instrukcí (sekvenčně konzistentní)

- obsluha uživatelem žádaných je snazší (je možné dokončit instrukci)

Řešení je relativně snadné pro přerušení mezi instrukcemi (většina vnějších přerušení a uživatelem žádaná přerušení):

° Maskovatelné x Nemaskovatelné - aritmetické přerušení lze u některých poč. maskovat

1. Dokončíme provádění rozpracovaných instrukcí (uvedeme procesor do sekvenčně konzistentního stavu)

° V rámci instrukce x Mezi instrukcemi - přerušení v rámci instrukce způsobuje nemožnost instrukci dokončit ° Nutnost návratu po obsluze x Ukončení programu s chybou

IF

2. Do pipeline vložíme sekvenci vnitřních instrukcí, která uloží stav PC (příp. i dalších reg.) a spustí obslužnou rutinu přerušení (viz instrukce TRAP v DLX)

Obtížná je přesná obsluha přerušení v rámci instrukce (většina vnitřních přerušení), která vyžadují návrat po obsluze.


ID • Nedefinovaná instrukce EX • Aritmetické přerušení (záleží na definici v ISA) MEM • Výpadek stránky, nezarovnaný přístup, chyba ochrany paměti WB • Nemůže nastat

V každém taktu mohou nastat až 4 vnitřní přerušení …


Příklad programu se vznikem více přerušení

Podmínky pro přesné přerušení u proudového zpracování


Obsluha přerušení u celočíselného DLX

Stupeň potvrzení (commit) v pipeline LW R1, (R2)-13

IF

MULTF F0,F1,F2 ADD R5, R6, R4 VM page boundary ????

ID

EX

MEM

WB

IF

ID

EX

MEM

IF

ID IF

EX ID

Missaligned memory access Unsupported instruction

WB MEM EX

Arithmetic overflow

WB MEM

WB

Page fault / TLB miss

LW R1, (R2)-13

=> Po stupni potvrzení již víme, že instrukce dobře dopadne (tj. nedojde k přerušení.)

ADD R5, R6, R4 VM page boundary

Podmínky pro přesné přerušení 1. Všechny instrukce dorazí do stupně potvrzení v programovém pořadí

Procesor má schopnost přesného přerušení pokud: 1. Procesor obsluhuje přerušení v programovém pořadí (to nemusí být shodné s pořadím jejich „objevení“ v pipeline).

2. Instrukce nemění stav procesoru ani paměti před stupněm potvrzení.

Principy implementace: •

2. Stav procesoru při obsluze musí být sekvenčně konzistentní: Instrukce před zdrojem přerušení musí být dokončeny. Instrukce za zdrojem přerušení nesmí změnit stav procesoru nebo paměti. (Provedení instrukce, která je zdrojem přerušení závisí na definici v ISA a typu přerušení.) Architektura počítačů

IF

Stupeň potvrzení (commit) je takový stupeň pipeline, kde platí, že všechna přerušení v pipeline mohou vzniknout nejpozději v tomto stupni.

• •

Požadavky na přerušení se akumulují ve speciálním stavovém slově, které společně s instrukcí a hodnotou jejího PC postupuje v pipeline až do stupně potvrzení. Procesor testuje přerušení u instrukcí ve stupni potvrzení, přerušení v rámci instrukce jsou potom obsluhována v pořadí jejich vzniku. Obsluha je zahájena zrušením všech instrukcí v pipeline před stupněm potvrzení a dokončení provádění instrukcí za stupněm potvrzení. Architektura počítačů

MULTF F0,F1,F2

???? Save WB_PC and trap to service routine

ID

EX

MEM

IF

ID

EX

IF

ID

WB NOP NOP

IF

NOP

IF

ID

EX

MEM

WB

Stupněm potvrzení (commit) je stupeň MEM u IntDLX Celočíselný DLX má schopnost přesného přerušení neboť 1. Všechny instrukce dorazí do MEM v programovém pořadí 2. Instrukce nemění stav procesoru ani paměti před stupněm MEM.


Úplný DLX nemá schopnost přesného přerušení 1

MULTF F1, F4, F6

IF

SW 4(R2), R1 ADDF F0, F3, F2

2

3

4

5

6

ID

MX1

MX2

MX3

MX4

IF

ID

EX

MEM

WB

IF

ID

MX1 AX1

MX2 AX2

7

8

MEM

WB

Úplný DLX s přesným přerušením 9

1

10

MULTF F1, F4, F6

2

IF

SW 4(R2), R1 AX3

MEM

WB

3

5

6

Osnova přednášky 7

8

9


10

° Dynamická predikce skoku

ID

MX1

MX2

MX3

MX4

MEM

WB

IF

ID stall

ID stall

ID stall

ID

EX

MEM

WB

IF stall IF

ID IF stall

IFMX1 stall

MX2 IF

ID

AX1

AX2

ADDF F0, F3, F2

° Zpracování komplexních instrukcí v pipeline AX3

° Problém přerušení u proudově pracujícího procesoru Pomocí pozastavení pipeline je možné opět dosáhnout přesného přerušení. Je to ovšem za cenu snížení výkonnosti o cca 20 % (dle simulace na SpecFP92).

Instrukce nedorazí do stupně potvrzení (MEM) v programovém pořadí. Přerušení generované instrukcí MULTF nemusí být přesné neboť následující instrukce mohla změnit stav procesoru nebo paměti.

° Dynamické plánování instrukcí

Možné přístupy k problému přesného přerušení u procesorů a) Některá přerušení příp. vůbec žádná nejsou přesná (definice v ISA) b) Dva módy činnosti: s přesným přerušením a bez něj (rychlejší) c) Kombinované techniky nepřesného přerušení se SW podporou d) HW náročné techniky založené na reorder bufferu, history file a nebo future file. (Nad rámec předmětu X36APS).

Instrukce jsou spouštěny v programovém pořadí, ale dokončeny jsou mimo programové pořadí. (In-order issue, out-of-order completion). Procesor těchto vlastností obecně nemá zaručeno přesné přerušení. Architektura počítačů


Dynamické plánování instrukcí = provádění instrukcí mimo pořadí (Out of Order - OoO)

- Dispatch (spouštění)- instrukce které mají připravené operandy zahájí provádění

Clock Cycle Number Instruction LD

F6,34(R2)

LD

F2,45(R3)

SUBD

F8,F6,F2

DIVD

F10,F0,F6

ADDD

F6,F8,F2

1

2

IF

ID

EX MEM WB

IF

ID

3

IF

4

EX

5

6

7

8

M2

M3

9

10

11

12

13

14

15

16

17

M4

M5

M6

M7

M8

M9 M10 MEM WB

ID

stall

M1

IF

ID

A1

A2 MEM WB

IF

ID

stall stall

IF

ID

A1

RAW

stall stall stall stall stall stall stall A2 MEM WB

D1

D2

WAR

DIVD je pozastaven kvůli RAW hazardu vůči MULTD, ADDD je provedeno mimo pořadí => F6 je přepsáno novou hodnotou => WAR hazard může nastat

superskalárními a superpipeline procesory (CDC 6600, IBM 360/91) Architektura počítačů

© David Patterson, CS252 UCB 2000

- Instrukce jsou vydávány v (programovém) pořadí ale spouštěny mimo pořadí (Spuštění závisí na tom, kdy jsou operandy k dispozici – tzv. datově-řízené plánování)

MEM WB

° Nevýhody?

° Dynamické plánování bylo vyvinuto koncem 60. let dávno před

- Issue (vydávání)- instrukce jsou dekódovány, jsou vyřešeny strukturní hazardy a instrukce jsou vloženy do instrukčního okna (rezervačních stanic) kde čekají na své operandy

° Jak vyřešit problém odlišné latence instrukcí? • Forwarding kvůli RAW hazardům je obtížnější.

MULTD F0,F2,F4

• Složitost implementace – nové typy hazardů, forwarding … • Implementace přesných přerušení je složité

Dynamické plánování – základní princip

° Jak vyřešit WAR a WAW hazardy? – mohou nastat a jsou častější

° Základní myšlenka: Umožnit instrukcím za pozastavením pokračovat:

° Provádění mimo pořadí = Provádění mimo programové pořadí

° Skutečné procesory – kombinace těchto technik

° Stupeň ID je rozdělen do dvou podstupňů

• Funguje i pro závislosti nerozpoznatelné v době překladu • Jednodušší překladač • Program přeložený pro jeden procesor funguje dobře i na jiném

F0,F2,F4 F10,F0,F8 F12,F8,F14

° Spekulativní provádění instrukcí


Problémy dynamického plánování?

° Proč v HW za běhu programu?

DIVD ADDD SUBD

4


© David Patterson, CS252 UCB 2000

° Mezi vydáním a spuštěním čekají instrukce na data různou dobu v rezervačních stanicích (také nazývané instruction pool, instruction issue queue, scheduler, instruction window) ° Procesory se liší v implementaci stupňů vydávání/spouštění ale používají stejného základního principu (také terminologie se liší) ° Instrukce čtou a zapisují operandy mimo programové pořadí => WAW a WAR hazardy Architektura počítačů

Řešení WAW a WAR hazardů ° Detekce WAW a WAR hazardů – instrukce nemůže být spuštěna pokud je prováděna instrukce zapisující do stejného registru (WAW) a nemůže zapsat data pokud jiná instrukce ještě potřebuje starou hodnotu (WAR) (poprvé použito v CDC6600) - vyřešeno technikou scoreboardingu - scoreboard indikuje stav všech registrů a řídí vydávání/spouštění instrukcí – viz např. M88110

Dosažení vyšší výkonnosti pomocí spekulace

Osnova přednášky

Požadavky na korektnost provádění programu


1. Program vypočítá správný výsledek (v souladu se sekvenční sémantikou - stejný jako na procesoru bez pipeliningu)

° Dynamická predikce skoku

2. Program generuje stejná přerušení (výjimky) (stejně jako na procesoru bez pipeliningu )

° Zpracování komplexních instrukcí v pipeline

NEBO ° Odstranění WAW a WAR hazardů – přejmenování registrů (IBM 360/91) - Každá instrukce dostane přidělen nový cílový fyzický registr, zdrojové registry jsou přejmenovány podle mapovací tabulky Existuje několik odlišných implementací tohoto postupu a je použit ve většině současných superskalárních procesorů (Pentium Pro a pozdější x86, Alpha 21264, MIPS R10K, R12K, IBM Power4, Power5 HP PA RISC 8600 a další, ...)

° Problém přerušení u proudově pracujícího procesoru ° Dynamické plánování instrukcí ° Spekulativní provádění instrukcí ° Skutečné procesory – kombinace těchto technik

- Pokud každá instrukce má unikátní cílový registr, WAW a WAR hazardy nemohou nastat (Vydávání instrukcí je zastaveno až pokud nám dojdou fyzické registry.) Architektura počítačů

Typy spekulativního provádění (v současnosti) ° Řídící spekulace : Instrukce za skokem jsou prováděny před znalostí výsledku skoku (dnes standard)

Spekulace vyžaduje dokončení instrukcí v programovém pořadí (kvůli kontrole na korektnost programu) Pokud dojde k chybné spekulaci => nastává zotavení a restart Zotavení a restart je poměrně nákladnou událostí (až desítky ztracených taktů)

Dvě HW struktury podporující spekulaci a zotavení - fronty - History Buffer HB - M88110 - Reorder Buffer RB – ostatní procesory


Example of Register Renaming with Control Speculation Clock cycle 1

First iteration

LF

F0,0(R1)

Renamed version

Issued

LF pf1, 0 (pi1)

1

Dispatched Finished Graduated


Example of Register Renaming with Control Speculation Clock cycle 2 LOOP:

Next iteration

F0,0(R1)

ADDF F4,F0,F2

SF

SF

0(R1),F4

SUBI R1,R1,#4

LF

Issued


LF pf1, 0 (pi1)

1

2

ADDF pf4, pf1, pf2

2

0(R1),F4

BNEZ R1,LOOP

F0,0(R1)

LOOP:

LF

F0,0(R1)

ADDF F4,F0,F2

ADDF F4,F0,F2

SF

SF

0(R1),F4

SUBI R1,R1,#4

Register map table (initial mapping)

Renamed version

SUBI R1,R1,#4

BNEZ R1,LOOP LOOP:

LF

ADDF F4,F0,F2

0(R1),F4

SUBI R1,R1,#4

BNEZ R1,LOOP

Nový stupeň v pipeline - dokončení (graduování, potvrzení) : Všechny instrukce jsou při dokončení vyjmuty z HB nebo RB v programovém pořadí a je provedena kontrola správnosti spekulace a výjimky jsou obsluhovány => To zároveň řeší problém přesného přerušení (podmínka 2)

Spekulativní provádění = částečné (dočasné) narušení podmínek A a B, při zachování korektnosti provádění programu (1. a 2.)


LOOP:

° Load / Store spekulace (Dynamic Memory Disambiguation) : Load je proveden před tím než je známa adresa předchozích instrukcí store (např. Itanium, Power 5, Core2)

Postačující podmínky pro dosažení korektnosti provádění programu A. Respektujeme datové závislosti (Instrukce čekají na vyřešení datových závislostí) B. Respektujeme řídicí závislosti (instrukce za skokem není provedena dokud není znám výsledek skoku) Řídicí závislosti => podmíněné datové závislosti C. Implementujeme přesné přerušení.

BNEZ R1,LOOP

F0 pf1

F2 pf2

F4 pf3

F0 renamed to pf1 and LF issued Architektura počítačů

R1 pi1

pf … physical FP reg. pi … physical int. reg.

Register map table

F0 pf1

F2 pf2

F4 pf4

F4 renamed to pf4 and LF dispatched Architektura počítačů

R1 pi1


LOOP:

Example of Register Renaming with Control Speculation Clock cycle 4

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

ADDF F4,F0,F2

ADDF pf4, pf1, pf2

2

ADDF F4,F0,F2

SF

SF 0(pi1), pf4

3

SF

LF

F0,0(R1)

0(R1),F4

LOOP:

LF

F0,0(R1)

0(R1),F4

SUBI R1,R1,#4

SUBI R1,R1,#4

BNEZ R1,LOOP

BNEZ R1,LOOP

LF

F0,0(R1)

LOOP:

LF


LF pf1, 0 (pi1)

1

2

ADDF pf4, pf1, pf2

2

ADDF F4,F0,F2

SF 0(pi1), pf4

3

SF

SF 0(pi1), pf4

3

SUBI pi2, pi1,#4

4

SUBI R1,R1,#4

SUBI pi2, pi1,#4

4

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

LOOP:

F0,0(R1)

LOOP:

LF

LF

F0,0(R1)

0(R1),F4

ADDF F4,F0,F2

SF

SF

SF

0(R1),F4

0(R1),F4

SUBI R1,R1,#4

BNEZ R1,LOOP

F2 pf2

F4 pf4

R1 pi1

Register map table

SF issued, LF computes the address

F0,0(R1)

ADDF F4,F0,F2 SF

0(R1),F4

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

ADDF pf4, pf1, pf2

2

F4 pf4

R1 pi2

SF 0(pi1), pf4

3 4

5

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

LF

LF pf5, 0(pi2)

6

Clock cycle 7 LOOP:

LF

F0,0(R1)

LOOP:

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

R1 pi2

SUBI finished, BNEZ dispatched, F0 renamed to pf5, new LF issued Architektura počítačů

BNEZ predicted, SUBI dispatched, LF in progress

ADDF pf4, pf1, pf2

2


LF

F0,0(R1)

ADDF F4,F0,F2

1

Dispatched Finished Graduated 2

ADDF pf4, pf1, pf2

2

8

8

SF 0(pi1), pf4

3

6

SUBI R1,R1,#4

SUBI pi2, pi1,#4

4

5

6

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

7

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

7

LF

LF pf5, 0(pi2)

6

7

LF

LF pf5, 0(pi2)

6

7

ADDF pf6, pf5, pf2

7

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

SF

SF 0(pi2), pf6

8

LOOP:

0(R1),F4

Register map table

0(R1),F4

Issued

LF pf1, 0 (pi1)

5

F0,0(R1)

SF

Renamed version

3

F0,0(R1)

0(R1),F4

SUBI R1,R1,#4

BNEZ R1,LOOP

F4 pf4

R1 pi2


SUBI R1,R1,#4

BNEZ R1,LOOP

F4 pf4

4

SF

SUBI R1,R1,#4

F2 pf2

SF 0(pi1), pf4

ADDF F4,F0,F2

F2 pf2

F0 pf1

SUBI pi2, pi1,#4

0(R1),F4

SF

0(R1),F4

5

SUBI R1,R1,#4

SF 6

ADDF F4,F0,F2

F0 pf5

2

0(R1),F4

Register map table

Example of Register Renaming with Control Speculation

ADDF F4,F0,F2

SUBI pi2, pi1,#4

Register map table

2

ADDF pf4, pf1, pf2


SUBI R1,R1,#4

F0,0(R1)

F2 pf2

R1 renamed to pi2, SUBI issued, L1 Data Cache miss occured (LF)

Example of Register Renaming with Control Speculation LF


1

BNEZ R1,LOOP

F0 pf1


Clock cycle 6

Issued

LF pf1, 0 (pi1)

SUBI R1,R1,#4

BNEZ R1,LOOP

F0 pf1

Renamed version

F0,0(R1)

ADDF F4,F0,F2

Register map table

LOOP:

Clock cycle 5

Issued

ADDF F4,F0,F2

SUBI R1,R1,#4

LOOP:


Renamed version

BNEZ R1,LOOP

F0 pf5

F2 pf2

F4 pf6

R1 pi2

BNEZ finished (prediction OK), LF dispatched, F4 renamed to pf6, Architektura počítačů ADDF issued

Register map table

F0 pf5

F2 pf2

F4 pf6

R1 pi2

1st LF finished (L2 cache hit), ADDF dispatched, 2nd LF calculates addr. Architektura počítačů


LF

F0,0(R1)

ADDF F4,F0,F2

Issued


LF pf1, 0 (pi1)

1

2

ADDF pf4, pf1, pf2

2

8

8

9


LF

F0,0(R1)

ADDF F4,F0,F2

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

ADDF pf4, pf1, pf2

2

8

Clock cycle 11 LOOP:

LF

F0,0(R1)

ADDF F4,F0,F2

1

Dispatched Finished Graduated 2

8

ADDF pf4, pf1, pf2

2

8

11

3

SF 0(pi1), pf4

3

SF 0(pi1), pf4

3

11

5

6

SUBI R1,R1,#4

SUBI pi2, pi1,#4

4

5

6

SUBI R1,R1,#4

SUBI pi2, pi1,#4

4

5

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

7

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

7

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

7

LF

LF pf5, 0(pi2)

6

7

9

LF

LF pf5, 0(pi2)

6

7

9

LF

LF pf5, 0(pi2)

6

7

9

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

9

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

9

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

9

SF

SF 0(pi2), pf6

8

SF

SF 0(pi2), pf6

8

SF

SF 0(pi2), pf6

8

SUBI pi3, pi2, #4

9

SUBI R1,R1,#4

SUBI pi3, pi2, #4

9

SUBI R1,R1,#4

SUBI pi3, pi2, #4

9

10

BNEZ R1,LOOP

BNEZ pi3, LOOP

10

BNEZ R1,LOOP

BNEZ pi3, LOOP

10

11

F0,0(R1)

0(R1),F4

LOOP:

Register map table

F0 pf5

F2 pf2

F4 pf6

R1 pi3

0(R1),F4

F0,0(R1)

0(R1),F4

Register map table

1st LF graduated , 2nd LF finished (Cache hit), etc.

F0 pf5

F0,0(R1)

ADDF F4,F0,F2 SF

0(R1),F4

SUBI R1,R1,#4

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

8

9

ADDF pf4, pf1, pf2

2

8

11

12

SF 0(pi1), pf4

3

11

SUBI pi2, pi1,#4

4

5

BNEZ pi2, LOOP

5

6

7

LF pf5, 0(pi2)

6

7

9

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

9

12

SF

SF 0(pi2), pf6

8

12

SUBI R1,R1,#4

SUBI pi3, pi2, #4

9

10

11

BNEZ R1,LOOP

BNEZ pi3, LOOP

10

11

12

Register map table

F0 pf5

F2 pf2

F4 pf6

2nd ADDF finished, 2nd SF dispatched Architektura počítačů


R1 pi2

LF

F0,0(R1)

ADDF F4,F0,F2 SF

LF

0(R1),F4

0(R1),F4

Register map table

R1 pi2

F0 pf5

0(R1),F4

SUBI R1,R1,#4

LOOP:

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

8

9

ADDF pf4, pf1, pf2

2

8

11

12


LF

F0,0(R1)

ADDF F4,F0,F2

SF 0(pi1), pf4

3

11

13

SF

4

5

6

SUBI R1,R1,#4

BNEZ pi2, LOOP

5

6

7

LF pf5, 0(pi2)

6

7

9

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

9

12

SF

SF 0(pi2), pf6

8

12

SUBI R1,R1,#4

SUBI pi3, pi2, #4

9

10

11

BNEZ R1,LOOP

BNEZ pi3, LOOP

10

11

12

Register map table

F0 pf5

11

R1 pi2


SUBI pi2, pi1,#4

LF

0(R1),F4

F4 pf6

6


BNEZ R1,LOOP F0,0(R1)

F2 pf2

9

1st ADDF finished, 1st SF dispatched, SUBI fin., BNEZ disp.


6

BNEZ R1,LOOP F0,0(R1)

F4 pf6

F0,0(R1)


Example of Register Renaming with Control Speculation LF

10

BNEZ predicted and issued


Clock cycle 12

F2 pf2

LOOP:

0(R1),F4

Issued

LF pf1, 0 (pi1)

4

SF

SF

Renamed version

SF 0(pi1), pf4

BNEZ R1,LOOP

LOOP:

9

SUBI pi2, pi1,#4

0(R1),F4

SUBI R1,R1,#4

LOOP:

8


SUBI R1,R1,#4

SF

LOOP:

Renamed version

F2 pf2

F4 pf6

1st SF finished

R1 pi2

LOOP:

0(R1),F4

Renamed version

Issued

LF pf1, 0 (pi1)

1

2

8

9

ADDF pf4, pf1, pf2

2

8

11

12 14

SF 0(pi1), pf4

3

11

13

SUBI pi2, pi1,#4

4

5

6

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

7

LF

LF pf5, 0(pi2)

6

7

9

ADDF F4,F0,F2

ADDF pf6, pf5, pf2

7

9

12

SF

SF 0(pi2), pf6

8

12

14

SUBI R1,R1,#4

SUBI pi3, pi2, #4

9

10

11

BNEZ R1,LOOP

BNEZ pi3, LOOP

10

11

12

F0,0(R1)

0(R1),F4

Register map table

F0 pf5

F2 pf2

F4 pf6

First two iterations finished within 14 cycles Architektura počítačů



R1 pi2

Same Example on 4-way Dynamic Superscalar


LOOP:

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

8

9

ADDF F4,F0,F2

ADDF pf4, pf1, pf2

2

8

11

12

SF

SF 0(pi1), pf4

3

11

13

SUBI R1,R1,#4

SUBI pi2, pi1,#4

4

5

BNEZ R1,LOOP

BNEZ pi2, LOOP

5

6

LF

LF

F0,0(R1)

0(R1),F4

F0,0(R1)

ADDF F4,F0,F2

Renamed version

Issued


LF pf1, 0 (pi1)

1

2

8

9

ADDF F4,F0,F2

ADDF pf4, pf1, pf2

1

8

11

12

14

SF

SF 0(pi1), pf4

1

11

13

14

6

15

SUBI R1,R1,#4

SUBI pi2, pi1,#4

1

2

3

14

7

16

BNEZ R1,LOOP

BNEZ pi2, LOOP

2

3

4

14

LOOP:

LF

F0,0(R1)

0(R1),F4

LF pf5, 0(pi2)

6

7

9

17

ADDF pf6, pf5, pf2

7

9

12

18

ADDF F4,F0,F2

LOOP:

LF

F0,0(R1)

2

3

9

14

2

9

12

15

SF 0(pi2), pf6

8

12

14

19

SF

SF 0(pi2), pf6

2

12

14

15

SUBI pi3, pi2, #4

9

10

11

20

SUBI R1,R1,#4

SUBI pi3, pi2, #4

3

4

5

15

BNEZ R1,LOOP

BNEZ pi3, LOOP

10

11

12

21

BNEZ R1,LOOP

BNEZ pi3, LOOP

3

5

6

15

0(R1),F4

Register map table

F0 --

F2 --

F4 --

R1 --

First two iterations graduated within 21 cycles. Architektura počítačů

0(R1),F4

LF pf5, 0(pi2) ADDF pf6, pf5, pf2

SUBI R1,R1,#4

SF

Shrnutí příkladu ° Každá iterace použivá odlišné fyzické registry pro F0, F4 a R1

Note: Simple instruction finished within 6 cycles. Time between prediction of 2nd BNEZ and branch evaluation is 3 cycles (up to 12 instructions issued)

° Provádění iterací se překrývá => de-facto rozbalení cyklu v HW ° Krátké instrukce dokončeny v průběhu 12 taktů (10 instrukcí) ° Provádění instrukcí s dlouhou latencí se překrývá s instrukcemi s krátkou latencí i vzájemně ° Spekulativní provádění : Ulož mapu registrů v době zahájení spekulace (v průběhu vydání instrukce BNEZ), obnov tuto mapu zpět v případě chybné spekulace (je k dispozici např. 4-6 map umožňující spekulovat až do hloubky 4-6 skoků...) ° Délka překryté latence závisí na počtu fyzických registrů a velikosti reorder bufferu (instrukce je v reorder bufferu mezi issue a graduate) ° Výkonnost je výrazně zlepšena načítáním, vydáváním a dokončením více instrukcí => superscalar out-of-order CPU



Závěry

Současné procesory – kombinace těchto technik ° 1st generation superscalar : static scheduling, static prediction

° Byl prezentován přehled technik využívajících ILP ke zvýšení výkonnosti procesoru

° 2nd generation superscalar : dynamic scheduling, dynamic prediction

° Superscalar, Superpipeline, VLIW

° 3rd generation superscalar : dynamic scheduling, dynamic prediction, speculation, superpipeline

° Dynamická predikce skoku ° Dynamické plánování = provádění instrukcí mimo pořadí

° Současné superskalární CPU (Pentium 4, MIPS R12K, Power4, PowerPC 620, Alpha 21264...) jsou nejčastěji Superscalar / Superpipeline (SUPER -SUPER) dynamicky plánované spekulativní procesory

° Spekulativní provádění instrukcí

° Staticky plánované a nespekulativní procesory a VLIWy jsou používány v aplikacích méně náročných na výpočetní výkon, zejména ve vestavných aplikacích. Dynamické plánování a spekulace jsou velmi náročné na plochu čipu a spotřebu !

° Moderní procesory jsou kombinací těchto technik a dalších specifických optimalizací pro danou ISA. ° Zdá se, že současné procesory se blíží limitu HW rozpoznatelného a využitelného ILP

° Při čtení popisu soudobých komerčních procesorů je důležité se neztratit v odlišné terminologii se spoustou výrazů, které jsou jen marketingem. ° Nové techniky využití ILP jsou stále ve vývoji (trace caches, value speculations) ale zdá se, že jsme blízko limitu paralelismu rozpoznatelného za běhu pomocí HW. Architektura počítačů


° Budoucnost může přát více kooperaci HW a SW na využití ILP IA-64 (EPIC) nebo využití paralelismu na úrovni vláken na jednom čipu buď formou multithreadingu (Pentium 4 with HT) nebo implementaci multiprocesorů na čipu (IBM Power 4, Opteron, Sun Gemini) nebo obou těchto přístupů (Power 5)… Architektura počítačů

Osnova přednášky Procesory využívající ILP. Dynamická predikce skoku. Zpracování komplexních instrukcí v pipeline

Recommend Documents