Pokročilé architektury počítačů Přednáška 2
Instrukční paralelizmus a jeho limity
Martin Milata
Obsah ●
Instrukční hazardy a datové závislosti (připomenutí)
●
Tomasulo algoritmus a dynamické plánování ●
Základní myšlenka
●
Přesná a nepřesná přerušení
●
Spekulace
●
Re-order buffer
●
CPI < 1 – Paralelní vydávání instrukcí
●
Limity ILP
●
Alternativní přístupy k dynamickému plánování ●
VLIW a EPIC
●
Vektorové procesory a vektorová rozšíření
Hazardy a jejich typy ●
Brání efektivnímu využití zřetězení
●
Strukturální hazardy ●
●
Datové hazardy ●
●
Konflikty sdílených zdrojů procesoru Datové konflikty typu RAW, WAR, WAW
Řídící hazardy ●
Neočekávané či nepredikovatelné změny vykonávání programu
Datové závislosti a hazardy ●
●
●
●
Obojí je nedílnou součástí programů Závislost mezi instrukcemi indikuje možnou přítomnost hazardu. To jestli se a jak daný hazard projeví, je ovšem záležitostí hardwarového uzpůsobení instrukční linky a řazení instrukcí na ni. Problematika datových závislostí ●
Indikace možné přítomnosti datových hazardů
●
Nutnost stanovení pořadí v němž musí být dosaženo výsledků jednotlivých instrukcí
●
Stanovení možných paralelismů pro optimální využití instrukční linky
●
Dnes řešeno s podporou nebo přímo v HW
Kontrolní závislosti ●
●
Případné změny pořadí provádění instrukcí nesmí ovlivnit očekávané chování programu Musí být zachován datový tok. Instrukce vykonávané mimo pořadí nesmí neočekávaně změnit hodnoty datového toku
Dynamické plánování instrukcí ●
●
Výhody dynamického plánování ●
Nezávislost na platformě. Přináší její efektivní využití
●
Jednoduchý kompilátor, mnoho závislostí řešeno až při provádění
Klíčová myšlenka ●
●
Dovolit vykonávání instrukcí mimo pořadí tak aby nezávislé instrukce nebyly omezovány předchozími hazardy
Důsledky ●
Instrukce jsou vydávány v pořadí
●
Provádění instrukcí je umožněno mimo pořadí
●
Dokončování instrukcí nastává mimo pořadí
První krok v dynamickém plánování ●
●
„Přináší možnost vykonávání instrukcí mimo pořadí při zachování jejich vydávání v pořadí“ Pro 5-ti stupňovou zřetězenou linku to znamená rozdělení DI fáze do dvou částí ●
●
●
●
●
Vydání instrukce (II) – její dekódování (in-order) Čtení operandů (RO) – příprava požadovaných dat operandů pro další zpracování (out-of-order)
Strukturální závislosti se řeší při vydávání instrukce Datové závislosti ve fázi čtení operandů v rámci vydaných instrukcí (issue window) Issue window reprezentuje plovoucí okénko, obvykle pevné délky, které se posouvá po vydávaných instrukcích. ●
●
Instrukce, které se v něm nacházejí, jsou vydány, mohou být zpracovávány nebo čekají na operandy. K posunu okénka dojde až v okamžiku, kdy první vydaná instrukce zapíše svůj výsledek.
Tomasulo Algoritmus ●
Klíčový algoritmus používaný při dynamickém plánování instrukcí ●
●
Alpha 21264, MIPS10000/R12000, Pentium II/III/4, Core, Core2, Nehalem, AMD K5, K6, Athlon, Opteron, Phenom, PowerPC ...
Jak Tomasulo pracuje? (1) ●
●
Reservační stanice (RS) přidružené k funkčním jednotkám (FU) –
Místo pro uložení omezeného počtu dekódovaných instrukcí určených pro danou FU
–
V RS distribuováno řízení a dočasné ukládání (ukládá operandy i výsledky instrukcí)
V instrukcích používané registry jsou nahrazeny ukazatelem nebo přímo jejich hodnotou v RS (register renaming) –
Předchází se tak WAR, WAW
–
V RS může být uloženo více různých hodnot než je skutečný počet registrů. Program není možné optimalizovat při kompilaci
Tomasulo Algoritmus ●
Jak Tomasulo pracuje? (2) ●
Common Data Bus (CDB) – sběrnice propojující všechny RS – –
●
zaslaná data obsahují navíc identifikátor zdroje (ID RS, která instrukci vydala) data jsou doručena na všechny RS (broadcast) kde jsou aktualizovány položky, které na data čekaly (plná asociativita v rámci RS je nutná)
Každá instrukce se může nacházet v jednom z následujících stavů –
–
–
vydaná – instrukce je načtená a dekódovaná (II) pokud je k dispozici místo v RS (strukturální hazardy) a jsou splněny kontrolní závislosti, pak je instrukce s dostupnými hodnotami operandů zaslána do RS provádí se – probíhá vlastní výpočet nad operandy (EX) podmíněno dostupností všech zdrojových operandů, pokud dostupné nejsou vyčkává se a provádí se kontrola CDB ukládá se výsledek – dokončení výpočtu (WB) výsledek je zaslán na CDB (tím je předán všem čekajícím položkám v RSs současně), použité místo v RS je uvolněno
Tomasulo Algoritmus
Tomasulo Algoritmus ●
Vydávání instrukce ● ●
●
●
instrukce jsou vydávány v pořadí vždy jsou stanoveny zdroje operandů a to buď registry nebo odkazy na RS, které se o výsledek produkující instrukce starají výsledek je doprovázen hodnotou tagu RS, která instrukci k výpočtu předala.
Zápis výsledků ●
instrukce budou pravděpodobně dokončovány mimo pořadí
●
jejich výsledek je rozšiřován pomocí CDB
●
●
spolu s výsledkem je zasílána informace o RS (tag), která se o instrukci starala RS a registry musí monitorovat CDB, na základě shody tagu aktualizovat hodnoty operandů instrukcí –
po aktualizaci hodnot se kompletní instrukce předají z RS funkční jednotce
Rezervační stanice ●
●
Rezervační stanice může být v procesoru zastoupena ●
jen jednou jako společná pro všechny funkční jednoty
●
několikrát s tím, že některé funkční jednotky RS sdílejí
●
samostatně pro každou funkční jednotku
Obsah RS je závislý na tom, zda obsahuje hodnoty operandů instrukcí nebo pouze ukazatele na zdrojové registry ●
●
●
●
Op. - operační kód instrukce Vj, Vk – hodnoty zdrojových operandů (případně ukazatelé na zdrojové registry) Qj, Qk – ukazatele na RS,která se stará o instrukci, jenž má vypočíst požadovanou hodnotu (pokud je nastaveno na 0 pak je hodnota k dispozici) Busy – Indikuje platnost pozice v RS (zpracovávání instrukce ještě nebylo dokončeno)
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Dokon- Zápis Vydaná čeno výsled.
Časování událostí
Tok instrukcí
Busy Op. Vj Vk Qj No Počet taktů kNo dokončení instrukce No No No Záznamy v rezervačních stanicích
Busy Load1 No Load2 No Load3 No
Address
Jednotky pro práci s pamětí
Rezervační stanice Taktů na FU FU
Přístup do paměti
Qk
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Tag Hodnota
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
Dokon- Zápis Vydaná čeno výsled. k r6 1 r7 r8 r3 r5 r3
Rezervační stanice Taktů na FU FU
Busy Op. No No No No No
Vj
Vk
Qj
Qk
Clock 1 Přístup do paměti Busy Load1 Yes Load2 No Load3 No
Address 34 + r6
Registry Tag Hodnota r0 r1 r2 r3 r4 r5 Load1 r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
Dokon- Zápis Vydaná čeno výsled. j k 34 r6 1 45 r7 2 r3 r8 r5 r3 r0 r5 r1 r3
Rezervační stanice Taktů na FU FU
Busy Op. No No No No No
Vj
Vk
Qj
Qk
Clock 2 Přístup do paměti Busy Load1 Yes Load2 Yes Load3 No
Address 34 + r6 45 + r7
Registry Tag Hodnota r0 r1 r2 r3 Load2 r4 r5 Load1 r6 r7 r8
Tomasulo Algoritmus Stav instrukcí
Dokon- Zápis Vydaná čeno výsled. Instrukce j k Ld r5 34 r6 1 3 Ld r3 45 r7 2 Mul r0 r3 r8 3 Sub r1 r5 r3 Div r2 r0 r5 Add r5 r1 r3
Rezervační stanice Taktů na FU FU Busy Op. mul1 yes Mul No No No No
Vj
Vk Qj Qk R(r8) Load2
Clock 3 Přístup do paměti Busy Load1 Yes Load2 Yes Load3 No
Address 34 + r6 45 + r7
Registry Tag Hodnota r0 mul1 r1 r2 r3 Load2 r4 r5 Load1 r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 3 4
Rezervační stanice Taktů na FU FU Busy Op. mul1 yes Mul add1 yes Sub No No No
Vj
Vk Qj Qk R(r8) Load2 M(L1) Load2
Clock 4 Přístup do paměti Busy Load1 No Load2 Yes Load3 No
Address 45 + r7
Registry Tag Hodnota r0 mul1 r1 add1 r2 r3 Load2 r4 r5 M(L1) r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 5
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU 10 mul1 2 add1 div1
Busy yes yes yes No No
Op. Vj Vk Qj Mul M(L2) R(r8) Sub M(L1) M(L2) Div M(L1) mul1
Clock 5
Qk
Address
Registry Tag Hodnota r0 mul1 r1 add1 r2 div1 r3 M(L2) r4 r5 M(L1) r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 5 6
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU 9 mul1 1 add1 div1 add2
Busy yes yes yes yes No
Op. Vj Vk Qj Mul M(L2) R(r8) Sub M(L1) M(L2) Div M(L1) mul1 Add M(L2) add1
Clock 6
Qk
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Address
Tag Hodnota mul1 add1 div1 M(L2) add2
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 5 6
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU 8 mul1 0 add1 div1 add2
Busy yes yes yes yes No
Op. Vj Vk Qj Mul M(L2) R(r8) Sub M(L1) M(L2) Div M(L1) mul1 Add M(L2) add1
Clock 7
Qk
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Address
Tag Hodnota mul1 add1 div1 M(L2) add2
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. Vj Vk Qj 7 mul1 yes Mul M(L2) R(r8) No div1 yes Div M(L1) mul1 2 add2 yes Add sub M(L2) No
Clock 8
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add2 r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. Vj Vk Qj 6 mul1 yes Mul M(L2) R(r8) No div1 yes Div M(L1) mul1 1 add2 yes Add sub M(L2) No
Clock 9
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add2 r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6 10
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. Vj Vk Qj 5 mul1 yes Mul M(L2) R(r8) No div1 yes Div M(L1) mul1 0 add2 yes Add sub M(L2) No
Clock 10
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add2 r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. 4 mul1 yes Mul No div1 yes Div No No
Vj Vk M(L2) R(r8)
Qj
M(L1) mul1
Clock 11
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. 3 mul1 yes Mul No div1 yes Div No No
Vj Vk M(L2) R(r8)
Qj
M(L1) mul1
Clock 12
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. 2 mul1 yes Mul No div1 yes Div No No
Vj Vk M(L2) R(r8)
Qj
M(L1) mul1
Clock 13
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. 1 mul1 yes Mul No div1 yes Div No No
Vj Vk M(L2) R(r8)
Qj
M(L1) mul1
Clock 14
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 15 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU Busy Op. 0 mul1 yes Mul No div1 yes Div No No
Vj Vk M(L2) R(r8)
Qj
M(L1) mul1
Clock 15
Qk
Address
Registry Tag Hodnota r0 mul1 r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 15 16 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU
40
Busy Op. No No div1 yes Div No No
Vj
Vk
mul
M(L1)
Qj
Clock 16
Qk
Address
Registry Tag Hodnota r0 mul r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 15 16 4 7 8 5 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU
1
Busy Op. No No div1 yes Div No No
Vj
Vk
mul
M(L1)
Qj
Clock 55
Qk
Address
Registry Tag Hodnota r0 mul r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 15 16 4 7 8 5 56 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU
0
Busy Op. No No div1 yes Div No No
Vj
Vk
mul
M(L1)
Qj
Clock 56
Qk
Address
Registry Tag Hodnota r0 mul r1 sub r2 div1 r3 M(L2) r4 r5 add r6 r7 r8
Tomasulo Algoritmus Stav instrukcí Instrukce Ld r5 Ld r3 Mul r0 Sub r1 Div r2 Add r5
j 34 45 r3 r5 r0 r1
k r6 r7 r8 r3 r5 r3
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled. 1 3 4 2 4 5 3 15 16 4 7 8 5 56 57 6 10 11
Busy Load1 No Load2 No Load3 No
Rezervační stanice Taktů na FU FU
Busy Op. No No No No No
Vj
Vk
Qj
Clock 57
Qk
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Address
Tag Hodnota mul sub div M(L2) add
Tomasulo alg. - výhody ●
Distribuovaná logika pro detekci a řešení hazardních stavů ● ●
●
Hromadná aktualizace (dodání hodnoty) operandů všem instrukcím, které na něj čekají pomocí CDB
Eliminace pozastavení linky z důvodu WAW a WAR ●
Přejmenovávání registrů v RS
●
Data nemusí vždy procházet cílovým registrem
●
●
Distribuovanost v RS a CDB
Použití CDB k distribuci výsledků (do registru je vždy uložena v data flow poslední hodnota – správný výsledek)
„Automatické rozmotávání“ smyček ● ●
Tomasulo dynamicky za běhu vytváří a sleduje plán datových závislostí. Překryv a vykonávání instrukcí mimo pořadí z rozdílných iterací smyček je řešen s pomocí přejmenovávání registrů a sledování toku dat mezi iteracemi, tak aby žádný z výsledků neporušil datový tok jiné iterace.
Tomasulo alg. - nevýhody ●
●
Složitost a cena ●
distribuovaná logika vykonávání a nároky na zpoždění
●
RS musí být pro CDB plně asociativní (rychlá aktualizace výsledků)
Výkon je kriticky ovlivňován šířkou CDB ● ●
CDB obsluhuje všechny FU, tvoří jedinou cestu jak předat výsledek Počet CDB (šířka) limituje počat FU, které mohou současně předávat výsledek při paralelním dokončení výpočtu –
●
Více CDB přináší složitější logiku pří výběru jedné pro zápis a komplikují asociativní část používanou při aktualizaci
Nepřesná přerušení (non-precise interrupts) ●
●
Při přerušení provádění programu není jasné pořadí instrukcí, které té, jenž přerušení vyvolala, předcházely nebo byly počítány mimo pořadí. Bude probíráno později
Tomasulo Algoritmus - Smyčky Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
j
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r0 0 r1 r4 r0 r2 r4 0 r1 r1 r1 8 r1 r2 L: r0 Iterace 0 r1 smyčky r4 r0 r2 r4 0 r1
Busy
Časování událostí Tok instrukcí
Busy Op. Vj Vk No Počet taktů kNo dokončení instrukce No No No Záznamy v rezervačních stanicích
Fu
No No No No No No
Jednotky pro práci s pamětí
Rezervační stanice Taktů na FU FU
Load1 Load2 Load3 Store1 Store2 Store3
Address
Qj
Qk
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Tag Hodnota
Tomasulo Algoritmus - Smyčky Clock 1
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r2 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
Busy Load1 Load2 Load3 Store1 Store2 Store3
1
Rezervační stanice Taktů na FU FU
Busy No No No No No
Op.
Vj
Vk
Qj
Qk
Yes No No No No No
Address 80
Registry Tag Hodnota r0 load1 r1 r2 r3 r4 r5 r6 r7 r8
Fu
Tomasulo Algoritmus - Smyčky Clock 2
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
Busy Load1 Load2 Load3 Store1 Store2 Store3
1 2
Rezervační stanice Taktů na FU FU Busy mul1 yes No No No No
Op. Mul
Vj
Vk Qj R(r2) load1
Qk
Yes No No No No No
Address 80
Registry Tag Hodnota r0 load1 r1 r2 r3 r4 mul1 r5 r6 r7 r8
Fu
Tomasulo Algoritmus - Smyčky Clock 3
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
Busy Load1 Load2 Load3 Store1 Store2 Store3
1 2 3
Rezervační stanice Taktů na FU FU Busy mul1 yes No No No No
Op. Mul
Vj
Vk Qj R(r2) load1
Qk
Yes No No Yes No No
Address
Fu
80 80
mul1
Registry Tag Hodnota r0 load1 r1 r2 r3 r4 mul1 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 4
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
Busy Load1 Load2 Load3 Store1 Store2 Store3
1 2 3 4
Rezervační stanice Taktů na FU FU Busy mul1 yes 1 sub1 yes No No No
Op. Mul Sub
Vj
Vk Qj R(r2) load1 R(r1) #8
Qk
Yes No No Yes No No
Address
Fu
80 80
mul1
Registry Tag Hodnota r0 load1 r1 sub1 r2 r3 r4 mul1 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 5
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5
Busy Load1 Load2 Load3 Store1 Store2 Store3
5
Rezervační stanice Taktů na FU FU mul1 0 sub1 bne1
Busy yes yes yes No No
Op. Mul Sub Bne
Vj
Vk Qj R(r2) load1 R(r1) #8 R(r6) sub1
Qk
Yes No No Yes No No
Address
Fu
80 80
mul1
Registry Tag Hodnota r0 load1 r1 sub1 r2 r3 r4 mul1 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 6
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5
5 6
Busy Load1 Load2 Load3 Store1 Store2 Store3
6 6
Rezervační stanice Taktů na FU FU Busy mul1 yes No 0 bne1 yes No No
Op. Mul Bne
Vj
Vk Qj R(r2) load1
sub1 R(r6)
Qk
Yes No No Yes No No
Address
Fu
80 80
mul1
Registry Tag Hodnota r0 load1 r1 sub1 r2 r3 r4 mul1 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 7
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7
5 6
Busy Load1 Load2 Load3 Store1 Store2 Store3
6 6
Rezervační stanice Taktů na FU FU Busy mul1 yes No No No No
Op. Mul
Vj
Vk Qj R(r2) load1
Qk
Yes Yes No Yes No No
Address
Fu
80 72 80
mul1
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul1 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 8
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8
5 6
Busy Load1 Load2 Load3 Store1 Store2 Store3
6 6
Rezervační stanice Taktů na FU FU Busy mul1 yes mul2 yes No No No
Op. Mul Mul
Vj
Vk Qj R(r2) load1 R(r2) load2
Qk
Yes Yes No Yes No No
Address
Fu
80 72 80
mul1
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 9
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
Busy Load1 Load2 Load3 Store1 Store2 Store3
9 5 6
6 6
Rezervační stanice Taktů na FU FU Busy mul1 yes mul2 yes No No No
Op. Mul Mul
Vj
Vk Qj R(r2) load1 R(r2) load2
Qk
Yes Yes No Yes Yes No
Address
Fu
80 72 80 72
mul1 mul2
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 10
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9
10
5 6 10
6 6
Busy Load1 Load2 Load3 Store1 Store2 Store3
Rezervační stanice Taktů na FU FU Busy 3 mul1 yes mul2 yes No No No
Op. Mul Mul
Vj Vk Qj load1 R(r2) R(r2) load2
Qk
No Yes No Yes Yes No
Address
Fu
72 80 72
mul1 mul2
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 11
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9
10
5 6 10
6 6 11
Busy Load1 Load2 Load3 Store1 Store2 Store3
Rezervační stanice Taktů na FU FU Busy 2 mul1 yes 3 mul2 yes No No No
Op. Mul Mul
Vj Vk load1 R(r2) load2 R(r2)
Qj
Qk
No No No Yes Yes No
Address
80 72
Fu
mul1 mul2
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 12
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9
10
5 6 10
6 6 11
Busy Load1 Load2 Load3 Store1 Store2 Store3
Rezervační stanice Taktů na FU FU Busy 1 mul1 yes 2 mul2 yes No No No
Op. Mul Mul
Vj Vk load1 R(r2) load2 R(r2)
Qj
Qk
No No No Yes Yes No
Address
80 72
Fu
mul1 mul2
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 13
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9 13
10
5 6 10
6 6 11
Busy Load1 Load2 Load3 Store1 Store2 Store3
Rezervační stanice Taktů na FU FU Busy 0 mul1 yes 1 mul2 yes No No No
Op. Mul Mul
Vj Vk load1 R(r2) load2 R(r2)
Qj
Qk
No No No Yes Yes No
Address
80 72
Fu
mul1 mul2
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 14
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9 13
10 14
5 6 10 14
6 6 11
Busy Load1 Load2 Load3 Store1 Store2 Store3
Rezervační stanice Taktů na FU FU 0
Busy No mul2 yes No No No
Op. Mul
Vj
Vk
load2 R(r2)
Qj
Qk
No No No Yes Yes No
Address
80 72
Fu
[mul1] mul2
Registry Tag Hodnota r0 load2 r1 sub1 r2 r3 r4 mul2 r5 r6 r7 r8
Tomasulo Algoritmus - Smyčky Clock 15
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9 13
10 14
5 6 10 14
6 6 11 15
Busy Load1 Load2 Load3 Store1 Store2 Store3
Rezervační stanice Taktů na FU FU
Busy No No No No No
Op.
Vj
Vk
Qj
Qk
No No No Yes Yes No
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Address
80 72
Fu
[mul1] [mul2]
Tag Hodnota load2 sub1 mul2
Tomasulo Algoritmus - Smyčky Clock 16
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9 13 16 5 6 10 14
Busy Load1 Load2 Load3 Store1 Store2 Store3
10 14 6 6 11 15
Rezervační stanice Taktů na FU FU
Busy No No No No No
Op.
Vj
Vk
Qj
Qk
No No No Yes Yes No
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Address
80 72
Fu
[mul1] [mul2]
Tag Hodnota load2 sub1 mul2
Tomasulo Algoritmus - Smyčky Clock 17
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9 13 16 5 6 10 14 17
Busy Load1 Load2 Load3 Store1 Store2 Store3
10 14 17 6 6 11 15
Rezervační stanice Taktů na FU FU
Busy No No No No No
Op.
Vj
Vk
Qj
Qk
No No No No Yes No
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Address
72
Fu
[mul2]
Tag Hodnota load2 sub1 mul2
Tomasulo Algoritmus - Smyčky Clock 18
Stav instrukcí Instrukce L: 1 Ld 1 Mul 1 Sd Sub Bne 2 Ld 2 Mul 2 Sd
r0 r4 r4 r1 r1 r0 r4 r4
j 0 r0 0 r1 r6 0 r0 0
k
Přístup do paměti
Dokon- Zápis Vydaná čeno výsled.
r1 r2 r1 8 L: r1 r2 r1
1 2 3 4 5 7 8 9
9 13 16 5 6 10 14 17
Busy Load1 Load2 Load3 Store1 Store2 Store3
10 14 17 6 6 11 15 18
Rezervační stanice Taktů na FU FU
Busy No No No No No
Op.
Vj
Vk
Qj
Qk
Address
No No No No No No
Registry r0 r1 r2 r3 r4 r5 r6 r7 r8
Tag Hodnota load2 sub1 mul2
Fu
Přesné přerušení ●
Přesné přerušení (precise interrupt) ●
Umožňuje přesné přerušení s tím, že všechny instrukce, které mu předcházely jsou vypočteny a výsledky, které by za ním následovaly, nejsou uloženy
●
Dokončování instrukcí mimo pořadí přesné přerušení komplikuje
●
Implementace dodatečných mechanizmů, které jej umožní (HW podpora) –
●
dokončování in-order nebo in-order commit výsledků
Přerušení ●
Co může způsobit přerušení –
●
Breakpoint (programová přerušení), porušení ochrany paměti, Page fault, požadavky na I/O zařízení, abnormality při aritmetických operacích (dělení 0), použití nedefinované instrukce, selhání HW nebo napájení, …
Typy přerušení –
synchronní versus asynchronní, uživatelská versus vynucená, maskovatelná versus nemaskovatelná, přerušení v instrukci versus mezi instrukcemi, přerušení se zotavením versus s ukončením programu
Přesné přerušení a spekulace ●
Spekulace ●
●
Spekulaci lze chápat jako formu „hádání“ provádění instrukcí při běhu programu Dnes je klíčová při řešení větvení programu –
●
Pokud dochází ke spekulativnímu vykonávání instrukcí, může dojít k jejich nechtěnému provádění. –
●
Spolu s komplexní predikcí větvení dnes hrají klíčovou úlohu při efektivním zpracování instrukcí větvení programu.
Vzniká potřeba mít možnost se vrátit (odstranit neplatné výsledky) a navázat na správný průchod programu, tedy jistá forma přerušení.
Přesná přerušení jako řešení? ●
Díky přesnému přerušení lze navázat na místo odkud bylo spekulativně provedeno chybné větvení programu.
HW podpora pro přesná přerušení ●
Re-order buffer (ROB) ●
●
●
●
Paměť dočasně uchovávající výsledky před jejich uložením do registrů Obvykle pole označující pořadí, cílový registr, hodnotu k uložení, platnost položky, přítomnost výjimky či přerušení, a hodnotu PC Položky jsou vkládány v okamžiku zápisu výsledku instrukce, tedy out-oforder
●
Zápis do registrů je prováděn nespekulativně a in-order
●
Snadné rušení instrukcí neuložením jejich výsledků do registrů
Commit fáze vykonávání instrukce ●
●
Provádí se zápis výsledků z ROB do registrů a to vždy v pořadí vydávání instrukcí (in-order) Pokud dojde k chybné spekulaci či jiné formě přerušení, pak je v pořadí dokončen zápis výsledků všech přerušení předešlých instrukcí. Zbylý obsah je zahozen (graduation).
Re-order buffer a Tomasulo algoritmus ●
Vydávání instrukcí ●
Postup vydávání instrukcí se liší pouze v nutnosti alokovat pro každou z nich záznam v ROB –
●
záznam obsahuje cílový registr, tag označení zdrojové FU, pořadí záznamů reprezentuje pořadí instrukcí
Zápis výsledků ●
●
Výsledek je pomoci CDB propagován mezi ostatní FU (ROB nemá vliv na out-of-order zpracovávání instrukcí) a aktualizován u záznamu v ROB Často dvojí „pohled“ na sadu registrů. –
pohled na registry s perspektivy vydávaných instrukcí, který je aktualizován mimo pořadí
–
pohled na registry ze strany ROB resp. commit jednotky, jenž je aktualizován vždy v pořadí
Re-order buffer a Tomasulo algoritmus ●
Commit výsledků ●
●
Z ROB jsou commit jednotkou v pořadí vložení záznamu zpracovávány vypočtené výsledky. V případě chybné spekulace či přerušení jsou nežádoucí výsledky v ROB stornovány a stav registrů z pohledu vydávání obnoven hodnotami z commit pohledu. –
v případě chybné spekulace se program vydává správnou cestou
–
v případech přerušení vlivem výjimky, zotavení nemusí být možné (záleží na druhu výjimky)
–
rozpracované instrukce (v ostatních FU) musejí být obvykle dopočteny. Není možné je z FU stornovat. Na jejich výsledek vlivem změny provádění programu však nikdo nečeká.
Architektura Tomasulo + ROB
Složitost ROB řešení ●
Problém vyhledávání aktuálních hodnot ● ●
●
●
Vyhledávání musí být extrémně rychlé (úroveň práce s registry) – mnohonásobně asociativní, počet cest do ROB by měl být teoreticky roven počtu registrů Rozhodnutí co je pro danou instrukci, která data požaduje, aktuální informace (nepotvrzená hodnota nebo potvrzený stav registrů)
Provádění Store instrukcí ●
●
●
ROB může sloužit jako zdroj dalšího paměťového prostoru
Provedení zápisu do paměti musí být pozastaveno až do okamžiku potvrzení dané instrukce Load instrukce mířící na neuloženou adresu musí být obslouženy hodnotou z ROB
Paralelní vydávání více instrukcí ●
Větší propustnost ROB, vyšší asociativita, ...
Jak zvýšit počet instrukcí za cyklus? CPI < 1 ●
●
Cílem je dosáhnout zvýšení průměrného počtu v jednom cyklu dokončených instrukcí na hodnotu větší než jedna. Vektorové procesory a vektorové instrukce ●
●
Superskalární procesory s dynamickým plánováním ●
●
multimediální vektorové instrukce jsou dnes zastoupeny na mnoha typech procesorech počet vydávaných instrukcí na cyklus je obvykle v mezích 1 až 8, je proměnný
Superskalární procesory s převážně statickým plánováním ●
●
obvykle fixní počet vydávaných instrukcí (4 až 16), jsou plánovány kompilátorem Intel Architecture-64 (IA-64) –
Explicitly Parallel Instruction Computer (EPIC)
Paralelní vydávání více instrukcí ●
Dynamické řešení přineslo jako první vydávání dvou instrukcí paralelně pro 5-ti stupňovou pipeline ● ●
●
instrukce musely být jedna celočíselná a jedna s řádovou čárkou eliminace závislostí až na instrukce čtení a zápisu do paměti (výpočet adres je prováděn na čísti procesoru určené pro celočíselnou aritmetiku)
Dopady paralelního vydávání více instrukcí ●
„Balíčkování“ instrukcí v podobě skupin instrukcí, které mohou být vydány v jednom cyklu –
●
vydávání může omezit přítomnost strukturních a datových hazardů na dříve vydané instrukce (nemusí být vydána ani jedna instrukce)
Náročné vyhledávání nezávislých instrukcí z „balíčku“ – – –
Je potřeba provést velké množství komparací (složitost O(n2-n)) Přináší limity na rychlost CPU (pomalý clock) Vlivem toho často dělení fáze vydávání instrukcí: 1. stanovení počtu paralelně proveditelných instrukcí, 2. prohledávání na hazardy
Důsledky paralelního vydávání ●
●
Pokud chceme dosáhnout dokončování dvou instrukcí v jednom cyklu, pak musí být v kódu rovnoměrně rozloženy celočíselné a FP instrukce. Paralelní vydávání přináší značnou složitost a HW náročnost ●
Paralelní přístup do instrukční cache
●
Možnost 6-ti přístupů do pole registrů v jednom taktu (4x read, 2x write)
●
●
●
Rychlé a účinné rozhodování o možném počtu vydávaných instrukcí se značnou složitostí vzhledem k nutnému počtu srovnání (O(n2 – n)) Nutnost přejmenování až dvou registrů v jednom cyklu pro předcházení WAR a WAW. Větší šířka sběrnic pro zápis výsledků (CDB), častěji se schází požadavky na paralelní zápisy
Virtuální registry a ROB ●
Virtuální registry lze chápat jako rozsáhlou kolekci registrů na něž jsou při vydávání instrukce původní přejmenovávány ●
●
●
●
●
Slouží spolu s procesem přejmenovávání jako náhrada ROB Musejí uchovávat dvojí hodnoty - architekturní a dočasné pohledy (spekulativní vykonávání instrukcí) Jednoznačný proces mapování registrů ve fázi vydávání instrukcí Zjednodušení fáze commit – uložení spekulativního dočasného pohledu do architekturního Nutnost dostatečného množství registrové paměti na čipu CPU –
přináší limity (40 – 80 registrů navíc)
–
použito např. v procesorech Pentium nebo Alpha
Limity instrukčního paralelizmu ●
S čím srovnávat aneb ideální procesor ●
Dopady přítomnosti HW limitů reálných procesorů budou srovnávány s ideálním procesorem, který – – – –
má vždy dostatek virtuálních registrů pro realizaci přejmenování a tím předcházení WAW a WAR konfliktů (Register Renaming) má dokonalou predikci skoků a větvení programů tím, že se při predikci nikdy nesplete (Branch and Jump Prediction) dovede vždy dokonale analyzovat přístupy do paměti tak, že je vždy zřejmé pořadí provádění operací čtení a zápisu (Memory address alias analysis) přístup do datové a instrukční cache realizuje s zpožděním jednoho cyklu
●
Procesor není reálné zkonstruovat
●
Jakým způsobem bude dopad limitů měřen? –
Sledování průměrného počtu vydaných instrukcí pro 6 SPEC testů výkonnosti (benchmarks)
Ideální procesor – výsledky testů Prováděných 6 testů lze rozdělit do dvou skupin ●
●
●
●
160
140
Testy gcc, espresso, li – zaměřeny na práci v celočíselné aritmetice Testy fpppp, doduc, tomcatv – zaměřeny na operace s plovoucí řádovou čárkou
Dále uvedené výsledky vždy reprezentují dopad konkrétního omezení s kumulativní aplikací předešlých omezení. Uváděná data převzata z knihy: John L. Hennessy & David A. Patterson, Computer Architecture - A Quantitative Approach - 4th Edition
120
Instruction issues per cycle
●
100
gcc espresso li fpppp doduc tomcatv
80
60
40
20
0 SPEC benchmarks
Omezení velikosti vydávacího okénka (window size) Patrný dopad velikosti vydávacího okénka ●
●
●
●
●
●
140
S jeho zmenšující se velikostí se srovnává počet nalezených paralelismů přes všechny testy Pro dnešní procesory není jeho velikost přímo rozhodující (ostatní limity mají tvrdší dopad) Dnes velikost 64 až ~250 instrukcí
Velikost vydávacího okna také nepřímo ovlivní výpadky cache. ●
160
120
Instruction issues per cycle
●
100
60
Při výpadku cache je potřeba držet instrukci ve vydávacím okně
40
Obsazená pozice instrukcí blokovanou čekáním na paměť
20
Dále je předpokládána velikost okna 2000 záznamů s maximálně 64 vydanými instrukcemi
Infinita 2k 512 128 32
80
0 gcc
espresso
li
fpppp
SPEC benchmarks
doduc
tomcatv
Realistická predikce větvení a skoků ●
Vzhledem k množství instrukcí větvení a skoků přináší další významný dopad jejich predikce. ●
●
●
nejlepší výsledek přináší kombinovaná predikce tournamentovým prediktorem nejvýznamnější dopad na int testech způsobený množstvím špatně predikovatelných větvení (nedostatek cyklů)
Pro další výsledky předpokládáme dvouúrovňový tournament prediktor s 8k záznamy
70
60
50
40 Perfect Tournament predictor 2-bit predictor Profile-based None
30
20
10
0 gcc
espresso
li
fpppp
doduc
tomcatv
Omezení počtu virtuálních registrů ●
Počet virtuálních registrů má drastický dopad především na výpočty se silnou spekulací nebo překryvy prováděných smyček (FP testy) ●
●
dnešní procesory běžně disponují 128 až 256 registry
Dále se bude předpokládat přítomnost dvou sad registru (int a FP registry), každá o 256 registrech
70
60
50
40
Infinite 256 int + 256 FP 128 int + 128 FP 64 int + 64 FP 32 int + 32 FP None
30
20
10
0 gcc
espresso
li
fpppp
doduc
tomcatv
Analýza konfliktů při přístupu do paměti ●
Cílem je analyzovat přístupy do paměti a umožnit co nejefektivnější uspořádání load a store instrukcí z hlediska možných paralelismů ●
●
Perfektní analýza přístupů ke globálním proměnným a na stack dnes dosažitelná s pomocí kompilátoru Další schémata můžou vylučovat konflikty na základě analýzy offsetu a bázového registru
60
50
40
Perfect Global-stack perfect Inspection None
30
20
10
0 gcc
espresso
li
fpppp
doduc
tomcatv
Instrukční paralelizmus na realistickém procesoru ●
Předpoklady pro měření ●
●
●
●
●
vydání až 64 instrukcí za takt (řádově více než dnešní CPU) tournamentův prediktor s 1k položkami a 16 záznamy pro návratovou predikci téměř perfektní analýza závislostí přístupu do paměti dvě nezávisle sady registru (int a FP) o 64 registrech pro přejmenovávání
Uvedený graf reprezentuje potenciální množství vydaných instrukci za takt vzhledem k uvedené velikosti vydávacího okna
60
50
40
Infinite 256 128 64 32
30
20
10
0 gcc
espresso
li
fpppp
doduc
tomcatv
Alternativní přístupy Statické plánování ●
Přesun zodpovědnosti za ILP z HW procesoru na stranu kompilátoru ●
● ●
● ●
Přináší zjednodušení procesoru a tím jeho potenciálně rychlejší strojový cyklus Použití VLIW instrukcí HW neprování explicitní kontroly hazardů mezi dílčími instrukcemi v VLIW Více prostoru pro registry na čipu procesoru Možnost provádění spekulací na základě celkového chování programu
●
Silně závislé na použité platformě
●
Obtížnější predikce větvení
●
Nárůst velikosti kódu
VLIW a problémy první generace ●
Nárůst velikosti kódu ●
●
●
VLIW instrukce často nevyužívaly všechny jednotky procesoru. Nepoužitá jednotka nemohla být z VLIW instrukce vyřazena (pevná poloha dílčích částí instrukce pro FU)
Problém procesoru bez detekce hazardů ●
●
●
Nezvládnuté náročné rozmotávání smyček často vedlo k neefektivnímu kódu (přímočaré vykonávání plně rozmotané smyčky)
Zastavení jedné jednotky vlivem závislostí vede k zastavení celého procesoru (ostatní jednotky nemohou pokračovat – synchronizace na jedné VLIW instrukci) Řazení instrukcí kompilátorem nezohledňuje délku výpočtu na různých FU
Binární kompatibilita ●
Každá verze procesoru vyžaduje vlastní kompilát kódu
VLIW a EPIC procesory ●
Více procesorové systémy ●
●
Jednočipové procesory ●
●
Intel iWarp
Multimediální jednočipy ●
●
Multiflow TRACE /500, Cydrome Cydra 5, IBM Yorktown VLIW Computer (výzkumný procesor)
Trimedia, Chromatic, Micro-Unity, DSP procesory
Hybridní architektury ●
Intel/HP EPIC IA-64 (Explicitly Parallel Instruction Computer)
Intel/HP EPIC IA-64 ●
Je považováno za VLIW druhé generace
●
Intel Itanium
●
●
první implementace IA-64
●
vysoce paralelní deseti stupňová instrukční linka
●
průměrný výkon, nepříliš úspěšný
Intel Itanium 2 ●
zaznamenalo 7 vývojových cyklů, končí v roce 2010 na procesoru Itanium 9300 (Tukwila)
●
přejímá odzkoušené technologie z jiných procesorů
●
2 až 4 jádra na čipu (propoje QPI – představeno v Nehalem)
●
30 funkčních jednotek na každé jádro
●
dvě sady registrů pro int a FP, každá 128 registrů (64/82 bit registry)
●
použití v serverových řešeních
IA-64 Itanium 2 ●
●
Optimalizace provádění kódu v HW ●
Predikce průchodu výpočtu kódem
●
Podpora spekulací, non-faulting čtení
●
Softwarově asistovaná predikce větvení
●
Softwarově asistovaná hierarchická organizace paměti
Instrukční skupiny ●
●
Skupinu instrukcí tvoří nezávislé instrukce, které mohou být prováděny paralelně za předpokladu volných HW prostředků Skupiny jsou tvořeny obvykle několika slovy, která jsou 128 bitů dlouhá. Nepoužití jednotky nemusí být zastoupeny – úspora místa.
IA-64 Itanium 2
http://en.wikipedia.org/wiki/File:Itanium_arch.png
Vektorové procesory ●
●
Cílem návrhu vektorových procesorů je zefektivnit provádění výpočtů nad lineárními poli čísel ●
původně provádění ve smyčce
●
vektorová instrukce zastoupí smyčku (cyklus)
Vlastnosti vektorových instrukcí ●
nezávislost dílčích výsledků –
●
zvýšení rychlosti provádění, lepší zřetězení
přístup do paměti se známým vzorem (známá vzdálenost mezi jednotlivými prvky) –
méně výpadků cache, snadnější predikce přístupu a příprava dat, datová cache není potřeba
●
redukuje se počet větvení (tím také problém s jeho predikci) v instrukční lince
●
jedna vektorová instrukce vykoná práci mnoho instrukcí nevektorového cyklu –
vydávání méně instrukcí (menší pravděpodobnost výpadku cache)
Vektorové procesory ●
Vektorové operace nejsou prováděny v jednom cyklu ●
●
po inicializaci výpočtu následuje N cyklů pro získání výsledků N prvkového vektoru
Typy vektorových procesorů ●
memory-memory vector processors –
●
operace jsou prováděny přímo nad pamětí (bez použití registrů)
vectore-register processors –
vektorové operace jsou prováděny nad vektorovými registry (kromě load and store)
Komponenty vektorových procesorů ●
Vektorová část ●
vektorové registry pevné délky (vector registers VR) – –
●
Vektorové FU – – –
●
typická délka 64 – 128 64 bitových prvků, 8-32 registrů limitován počet portů pro čtení a zápis (2x r + 1x w) FU pro provádění add, mul, reciprocal (1/x) operací FU pro práci s pamětí (Load-Store Units – LSU) všechny jednotky jsou zřetězené
Skalární část ●
skalární registry
●
FU pro celočíselné operace a operace v plovoucí řádové čárce
Přístupy do paměti ●
Využívá se vektorových instrukcí Load a Store ●
●
slouží k přesunu bloku dat mezi pamětí a vektorovým registrem
Vzhledem k adresování jednotlivých prvků rozlišujeme tři přístupy ●
prvky jsou v paměti uloženy jeden za druhým (Unit stride) –
●
mezi prvky je vždy konstantní úsek paměti, který s čtenými daty nesouvisí (non-unit constant stride) –
●
nejrychlejší možný přístup – sekvenční čtení bloků paměti
práce se sloupci matice (mezi prvky vektoru jsou vždy data ostatních sloupců)
indexovaný přístup –
nepřímý přístup k vektoru
–
používá se při práci s řídkými poli
–
vektorová komprese a expanze
Jak na dlouhé vektory ●
Použití registru délky vektoru (vector-length register VLR) ●
Řídí všechny vektorové operace
●
Hodnota slouží k omezení délky vektoru na jeho skutečnou délku
●
●
Délka vektoru často nemůže být stanovena při překladu programu - dynamická velikost vektoru.
Dlouhé vektory ●
●
low = 0 VL = n mod MVL Výpočet je prováděn ve více for ( j=0; j<=(n/MVL); j++ ){ for (i=low, i
obalovací smyčka s minimálním počtem opakování efektivnější než práce bez vektorové instrukce
Výběr prvků a vektorová maska ●
Maska vektoru ●
●
●
definuje pro které prvky se provádí vektorová operace (dovoluje ponechat prvek cílového vektoru nezměněn) obvykle pro každou pozici vektoru uložen 1bit (0 neaktualizuj, 1 aktualizuj)
instrukce, která provádí srovnání prvků a aktualizaci masky podle zadané podmínky for (i=0; i
●
má stejný počet prvků jako vektorové registry
Řetězení vektorových operací ●
Vektorové instrukce je možno provádět ●
bez překryvu –
●
dokončení jedné operace předá celý modifikovaný vektor ke zpracovávání další instrukci
s překryvem –
instrukce jsou vzájemně překryty s tím, že nedochází k předání celého vektoru ale již dílčích výsledků
Metriky pro srovnávání vektorových procesorů ●
Srovnávání výkonu pro referenční vektory ●
●
R∞ výkon procesoru pro nekonečně dlouhé vektory –
idealizovaný vektor
–
nekonečně dlouhý vektor nezohledňuje inicializační čas potřebný při startu výpočtu
–
doprovází se reálnějším srovnáním Rn – výkonem procesoru pro vektory délky n
N1/2 poloviční velikost vektorů –
●
využívá se při sledování dopadu inicializačního času
NV délka vektorů, při které je vektorová instrukce již rychlejší než klasická skalární smyčka –
sleduje výkon vektorových operací jak ve vztahu k inicializačnímu času tak k vlastnímu výkonu vektorové jednotky
Vektorové operace pro multimédia ●
Rozšíření instrukčního soubory Intel MMX/SSE ●
●
●
podobná rozšíření potkaly instrukční soubor většiny procesorů
Cílem je provést požadovanou operaci nad skupinou krátkých operandů a zrychlit tak multimediální operace ●
●
nejedná se o vektorové instrukce ve předchozím prezentovaném smyslu
128bit registr je dělen na 2x 64bits, 4x 32bits, 8x 16bits, 16x 8bits
Provádí se obvykle ve specializované aritmetice právě pro multimediální operace ●
saturovaná aritmetika
Závěr ●
● ●
●
Představení Tomasulo algoritmu a princip jeho použití v moderních porocesorech Problematika paralelního vydávání instrukcí Dopady „nedokonalostí“ dnešních procesorů na úroveň ILP Alternativy k dynamickému plánování ●
Vývoj VLIW procesorů
●
Vektorové procesory a princip jejich činnosti
Dotazy?
Literatura ●
●
●
John L. Hennessy, David A. Patterson, Computer Architecture: A Quantitative Approach (4th Edition) Paul H. J. Kelly, Advanced Computer Architecture Lecture notes 332 Andrew S. Tanenbaum, Operating Systems: Design and Implementation
88