====== 7. Predikce skoků, optimalizace kódu ======
/*
* [[courses:b35apo:solutions:07:start]]*/
* pro vyučující [[..:..:internal:tutorials:07:start|cvičení 7]]
===== Osnova cvičení =====
- Predikce skoků - úvod
- Statická predikce skoků - příklad
- Fibonacciho posloupost - optimalizace kódu pro QtRVSim bez HU
- Dynamická predikce skoků - příklad
===== Co bych si měl na cvičení zopakovat/připravit =====
- Rozumět předchozímu cvičení
\\
===== Náplň cvičení =====
\\
==== 1. Predikce skoků - úvod ====
Motivace - proč je dobré umět správně odhadnout zda a kam se bude skákat..
{{..:branch.png|}}
\\
Jak je vidět na obrázku, při některých typech skoků dokážeme vyhodnotit podmínku a určit místo skoku až relativně hluboko uvnitř pipeline. Kdybychom dokázali správně odhadnout kam bude skoková instrukce skákat a začali vykonávat patřičný kód od daného místa, mohli bychom získat k dobru rozpracování hned několika instrukcí. Protože jsou skokové instrukce v programech relativně časté, sehrává predikce skoků významnou roli v zvyšování programové propustosti systému jako celku.
\\
\\
Predikce větvení se skládá ze dvou fundamentálních složek:
* branch target speculation (kde),
* branch condition speculation (zda vůbec).
\\
K predikci cíle větvení slouží BTB (Branch Target Buffer) – asociativní cache obsahující dvě položky: BIA (Branch Instruction Address) a BTA (Branch Target Adress) – přistupuje se do ní současně při výběru instrukce hodnotou PC. Pokud se BIA shoduje s PC, je vybrána BTA a v případě, že se skok predikuje mění PC touto hodnotou.
\\
\\
Predikovat splnění podmínky větvení můžeme: staticky, dynamicky, nebo hybridně. Nejjednodušší statickou predikcí je předpoklad, že skoková instrukce se nevykoná (nebude se skákat) a program bude pokračovat v normálním sekvenčním sledu dál. O něco pokročilejší predikcí je tzv. BTFNT (Backwards Taken / Forwards Not-Taken) predikce.
\\
\\
Uvažujme zřetězený procesor podle následujícího schématu:
{{..:pipeline_simple.png|}}
\\
\\
Nejjednodušší metodou vypořádání se se skokovými instrukcemi (nejedná se o predikci) je zahození následující rozpracované instrukce (flush) a pozastavení (stall) pipeline, jakmile je skoková instrukce detekována, až do doby než dosáhne stupeň MEM, kdy je známa nová hodnota PC. Průchod instrukcí přes pipeline můžeme vyjádřit nasledovně:
\\
| | --------- | --------- | --------- | --------- | --------- | --------- | --------- | --------- | --------- |--------- |
^ skoková instrukce | IF | ID | EX | MEM | WB | | | | | |
^ následující instr. | | IF(flush) | stall | stall | IF | ID | EX | MEM | WB | |
^ následující instr. + 1 | | | | | | IF | ID | EX | MEM | WB |
\\
Pozastavení práce pipeline se objeví až ve stupni ID (kdy jsme zjistili, že se jedná o skokovou instrukci) a trvá 3 cykly. Pozastavení pipeline na 3 cykly představuje významnou stratu. Kdybychom předpokládali 30% pravděpodobnost skokové instrukce a ideální CPI (CPI=1), pak bychom dosáhli pouze poloviční zrychlení (2,63) oproti ideálnímu 5 násobnému zrychlení zavedením 5-stupňové pipeline. Všimněte si, že v důsledku skokové instrukce je nutno vykonat stupeň IF znovu - restart stupně IF - nemůžeme implicitně pokračovat přinesenou instrukcí v druhém taktu (mohlo dojít k skoku).
.
\\
\\
Simulovat pozastavení pipeline v simulátoru QtRVSim bez HU můžeme povkládáním tří instrukcí nop za každou skokovou instrukci. Přesunutím testovací podmínky do stupně ID a vypočtením cílové adresy skoku do tohoto stupně můžeme redukovat penalizaci ze tří cyklů pouze na jeden - to je ukázané v simulátoru QtMips, kde lze ovšem při skocích testovat registry pouze na rovnost.
\\
\\
__**Statická predikce:**__
\\
Další již zmíněnou metodou vypořádání se se skokovými instrukcemi je predikce, že skoková instrukce se nevykoná (**Predict Not Taken**). V tomto případě se pokračuje jakoby se skoková instrukce nevykonala - pokračuje se následující instrukcí. Důležité však je, že nesmí být změněn stav procesoru (zapsání nových hodnot do registrů a pod.) dokud není výsledek skokové instrukce definitivně znám. Nyní již předpokládejme, že adresu větvení dokážeme určit již ve stupni ID.
\\
\\
Běh programu pokud se nemělo skákat:
\\
| | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
^ skoková instrukce | IF | ID | EX | MEM | WB | | |
^ následující instr. | | IF | ID | EX | MEM | WB | |
^ následující instr. + 1 | | | IF | ID | EX | MEM | WB |
\\
Běh programu pokud se má skákat:
\\
| | ------ | ------ | ------ | ------ | ------ | ------ | ------ | ------ |
^ skoková instrukce | IF | ID | EX | MEM | WB | | | |
^ následující instr. | | IF | ID | EX | | | | |
^ následující instr.+1 | | | IF | ID | | | | |
^ následující instr.+2 | | | | IF | | | | |
^ cílová instrukce | | | | | IF | ID | EX | MEM |
^ cílová instrukce +1 | | | | | | IF | ID | EX |
\\
Pokud skoková instrukce nezpůsobuje skok, určeno ve stupni ID, můžeme pokračovat v běhu programu beze změny. Pokud se má skákat, restartuje se stupeň ID s novou cílovou adresou. Toto způsobí pozastavení všech instrukcí následujícími za skokovou na jeden cyklus. Důležitým rozdílem oproti předchozímu případu (bez predikce), krom dřívějšího zjištění adresy větvení, je fakt, že k zahození rozpracované následující instrukce dojde jenom v případě pokud dochází ke skoku!
\\
==== 2. Statická predikce skoků - příklad ====
Uvažujte níže uvedený program:
la s1, array
addi s2, s1, 5*4 // 5*sizeof(int)
addi t1, zero, 2
loop:
lw s0, 0(s1) // s0 <- Mem[s1]
addi s0, s0, 0x1 // s0++
sw s0, 0(s1) // Mem[s1] <- s0
addi s1, s1, 0x4 // s1 = s1 + 4
sub t0, s2, s1 // t0 = s2 - s1
bne t0, zero, loop // if (t0 != 0) goto loop
la s0,array
addi t1, t1, -1
ebreak
.data
.org 0x1000
array:
.word 0,1,2,3,4
\\
\\
__Úkol:__ Určete počet cyklů pro vykonání tohoto programu:
- Odkrokujte si tento program v QtRvSim s vypnutým a se zapnutým pipeliningem s Hazard Unit s forwardingem. Vysvětlete chování simulátoru.
- Kolik cyklů trvá výpočet s jednocyklovým procesorem a kolik cyklů s pipeliningem s Hazard Unit se s vypnutým a zapnutým forwardingem.
\\
\\
==== Dynamická predikce skoků - příklad ====
Představme si, že při provádění programu přijdeme na skokovou instrukci. Naše rozhodnutí zda se bude/nebude skákat učiníme podle toho zda se skákalo/neskákalo když se tato instrukce vykonala naposled. Pro tento účel nechť máme k dispozici tabulku (branch history table), kde si můžeme poznamenat jak dopadlo chování té které skokové instrukce naposled. Každá doposud vykonaná skoková instrukce má v této tabulce jeden záznam. Takto popsanou predikci můžeme znázornit následujícím stavovým diagramem (automat typu Moore):
{{..:dynamicka_predikce_1bit.png|}}
Vidíme, že pro jeden záznam v tabulce postačuje 1 bit. Na počátku se nacházíme v stavu "Not taken" - kdy předpovídáme, že se skákat nebude. Když se tato předpověď potvrdí (hrana "Not taken"), pak zůstáváme v tomto stavu, v opačném případě přecházíme do stavu "Taken". Když pak přídeme na tuto skokovou instrukci opět, budeme nyní předpovídat, že se skákat bude.
O něco pokročilejším způsobem predikce je predikce zohledňující o něco delší historii chování dané skokové instrukce - jak můžeme vidět na obrázku níže. Na počátku se nacházíme v stavu "Strongly not taken". Pro stavy "Strongly not taken" a "Weakly not taken" předpovídáme, že se skákat nebude. V tomto případě potřebujeme pro jeden záznam 2 bity - pro rozlišení 4 možných stavů. Na tyto záznamy se také můžeme dívat jako na saturující počítadla, které buď inkrementujeme nebo dekrementujeme v závislosti na skutečném chování skokové instrukce.
{{..:dynamicka_predikce_2bity.png|}}
__Úkol:__ Uvažujte níže uvedený programový fragment. Určete počet špatných predikcí pro tyto dva případy:
* pro BHT (branch history table) s 1-bitovým počítadlem
* pro BHT (branch history table) s 2-bitovým počítadlem
\\
int i, j, c=0;
for (i=0; i<500; i++) {
for (j=0; j<4; j++) {
c++;
}
}
Přepis programového fragmentu:
// i = s0, j = s1, c = s2, t0 = limit vnejsi smycky, t1 = limit vnitrni smycky, t3 - pomocna promenna
addi s2, zero, 0 // c = 0;
addi t0, zero, 500 // t0 = 500;
addi t1, zero, 4 // t1 = 4;
addi s0, zero, 0 // i = 0;
L1:
addi s1, zero, 0 // j = 0;
L2:
addi s2, s2, 1 // c++;
addi s1, s1, 1 // j++;
slt t3, s1, t1 // t3 = (s1 < t1) ? 1 : 0;
bne t3, zero, L2
addi s0, s0, 1 // i++;
slt t3, s0, t0 // t3 = (s0 < t0) ? 1 : 0;
bne t3, zero, L1
Alternativní příklad:
C program
int i, j;
int pole[20];
for (i=0; i<5; i++) {
for (j=0; j<20; j++) {
pole[j]++;
}
}
je přepsán do assembleru takto:
la s3, pole
addi t1, zero, 5
addi s2, s3, 20*4
l2:
add s1, s3, zero
loop:
lw t0, 0(s1) // t0 <- pole[j]
addi t0, t0, 1 // s0++
sw t0, 0(s1) // pole[j] <- s0
addi s1, s1, 4 // j++
bne s1, s2, loop // pole[j]!=pole[20]
addi t1, t1, -1
bne t1, zero, l2
ebreak
nop
.data
.org 0x4000
pole:
.word 0,1,2,3,4,5,6,7,8,9
.word 10,11,12,13,14,15,16,17,18,19
1) Kolikrát se celkem vyhodnoti prikaz bne
2) Kolik chyb udělá 1-bitový prediktor s počátečním nastavením Not Taken
3) Kolik chyb udělá 2-bitový prediktor s počátečním nastavením Weakly Not Taken a kolik chyb udělá s počátečním nastavením Weakly Taken
4) Kolik bude cache hit a cache miss datové cache při velikost bloku 4 slova, počet množin 4, stupeň asociativity 1, když pole začíná v paměti na adrese 0x4000.
5) Změní se počet cache hit a cache miss při velikost bloku 4 slova, počet množin 2, stupeň asociativity 2.
==== Fibonacciho posloupnost - optimalizace kódu ====
Na předchozím cvičení jste si napsali nejdřív program pro výpočet členů Fibonacciho posloupnosti pro "klasický" RISC-V procesor, pak jste tento program modifikovali vkládáním instrukcí nop tak, aby byl správně vykonán i na zřetězenému procesoru neřešícím hazardy (QtRVSim s vypnutou HU). Pravděpodobně jste dospěli k následujícímu programu:
.globl _start
.option norelax
_start:
addi t0, zero, 0x5 // t0 = 5; // Nastaveni hodnoty N
addi s0, zero, 0x0 // F(0)
addi s1, zero, 0x1 // F(1)
addi t1, zero, 0x2 // t1 = 2;
nop
loop: // {
add t2, s0, s1 // t2 = s0 + s1;
addi s0, s1, 0x0 // s0 = s1;
nop //
addi s1, t2, 0x0 // s1 = t2;
addi t1, t1, 0x1 // t1++;
nop //
nop // }
bne t0, t1, loop // test t1 < t0
nop
nop
nop
addi s1, s1, 15 // s1 += 15;
inf_loop:
ebreak
beq zero,zero, inf_loop
Abychom vypočetli N-té Fibonacciho číslo dojde celkem k 6*(N-2)+1 vykonání instukce nop. V našem případě, kdy N=5, to činí 19 prázdných instrukcí, celkem 43 instrukcí než je znám výsledek (zapsán do registru s1). \\
\\
__Úkol:__ Vašim úkolem bude tento program optimalizovat "proházením" instrukcí tak, abychom získali správný výsledek vykonáním co nejméně instrukcí. Jako pomůcku můžete využít schématu uvedeného výše (při popisu Delayed branch), který ukazuje, jak je možné zaplnit prostor bezprostrědně za skokovou instrukcí. Další metodou jak eliminovat prázdné instrukce je proházet instrukce mimo původní programové pořadí tak, aby se od sebe dostatečně vzdálily instrukce způsobující datové hazardy, ale přitom se zachovala korektnost programu (program bude dávat stejné výsledky).
Počet dokončených instrukcí zjistíte v okně **Control and Status Registers** v položce **minstret**.
Počet načtených instrukcí můžete zjistit v **Program Cache** sečtením **Hit+Miss**