Warning
This page is located in archive. Go to the latest version of this course pages. Go the latest version of this page.

7. Predikce skoků, optimalizace kódu

Osnova cvičení

  1. Predikce skoků - úvod
  2. Statická predikce skoků - příklad
  3. Fibonacciho posloupost - optimalizace kódu pro QtRVSim bez HU
  4. Dynamická predikce skoků - příklad

Co bych si měl na cvičení zopakovat/připravit

  1. 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..


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:



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:

  1. 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.
  2. 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):

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.

Ú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

courses/b35apo/tutorials/07/start.txt · Last modified: 2023/04/12 14:21 by dupakjak