7. Predikce skoků, optimalizace kódu

pro vyučující

Osnova cvičení

Predikce skoků - úvod
Statická predikce skoků - příklad
Fibonacciho posloupost - optimalizace kódu pro MipsPipeS
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..

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 MipsPipeS 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 - viz simulátor MipsPipeXL ().

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 - viz MipsPipeXL .

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	idle	idle	idle	idle
cílová instrukce			IF	ID	EX	MEM	WB
cílová instrukce +1				IF	ID	EX	MEM	WB

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!

Opožděný skok (Delayed Branch) - představuje další metodu vypořádání se se skokovými instrukcemi. Bezprostředně za skokovou instrukcí vznikají tzv. branch-delay sloty, tzn. instrukce, které se vždy vykonají bez ohledu na výsledek skokové instrukce.

Běh programu pokud se nemělo skákat (delay slot jenom pro jednu instrukci):

	——	——	——	——	——	——	——	——
skoková instrukce	IF	ID	EX	MEM	WB
následující instr. (slot)		IF	ID	EX	MEM	WB
následující instr. + 1			IF	ID	EX	MEM	WB
následující instr. + 2				IF	ID	EX	MEM	WB

Běh programu pokud se má skákat:

	——	——	——	——	——	——	——	——
skoková instrukce	IF	ID	EX	MEM	WB
následující instr. (slot)		IF	ID	EX	MEM	WB
cílová instr.			IF	ID	EX	MEM	WB
cílová instr. + 1				IF	ID	EX	MEM	WB

Úkolem kompilátoru je zabezpečit, že následující instrukce nacházející se v slotu budou platné a užitečné. Na níže uvedených obrázcích jsou ilustrovány tři alternativy jak je možné plnit delay slot.

V obrázku nalevo je delay slot naplněn nezávislou instrukcí nacházející se před instrukcí skoku. Strategie naznačené na obrázcích uprostřed a vpravo jsou použity v případě, že není možné použit tuto alternativu. V obou případech brání použití registru R1 ve vyhodnocovací podmínce (datová závislost). Přitom je nutno zabezpečit, že vložení instrukce do delay slotu nepovede k nekorektnímu chování programu - modifikovaný program a program původní nejsou ekvivalentní!

Důležitým rysem všech metod statické predikce je, že chování programu nezávisí na historii chování skokových instrukcí.

2. Statická predikce skoků - příklad

Uvažujte níže uvedený programový fragment a předpokládejte, že hodnota s2=s1+800, přičmež s1 určuje bázovou adresu nějaké buňky datové paměti.

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
  bnez  t0, loop      // if (t0 != 0) goto loop

Úkol: Určete počet cyklů pro vykonání tohoto fragmentu pro tyto případy (za předpokladu, že přístupy do paměti se realizují přes cache jako cache hit):

Bez uvažování možnosti přeposílání (forwarding) avšak s možností zápisu do souboru registrů a čtení zapsaných dat v témže cyklu, přičemž skoková instrukce je ošetřena vyprázdněním pipeline. Adresa větvení je určena ve stupni EX dle simulátoru MipsPipeS
Výpočet realizujeme na procesoru dle simulátoru MipsPipeXL , tzn. mezivýsledky se přeposílají, skoky se predikují jako nerealizované (not taken)
Výpočet realizujeme na procesoru dle simulátoru MipsPipeXL s tím rozdílem, že můžeme rozvrhnout pořadí instrukcí tak, aby se vyplnil jednocyklový delay slot skokové instrukce (single-cycle delayed branch).

3. 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ý” MIPS procesor, pak jste tento program modifikovali povkládáním instrukcí nop tak, aby byl správně vykonán i na zřetězenému procesoru neřešícím hazardy (simulátor MipsPipeS). Pravděpodobně jste dospěli k následujícímu programu:

#define t0 $8
#define t1 $9
#define t2 $10
 
#define s0 $16
#define s1 $17
#define s2 $18
 
.globl start
.set noat
.set noreorder
.ent start
 
start:
addi t0, $0, 0x5     //  t0 = 5;  //  Nastaveni hodnoty N
addi s0, $0, 0x0     //  F(0)
addi s1, $0, 0x1     //  F(1)
                     
addi t1, $0, 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:
beq $0,$0, inf_loop  
 
nop
.end start

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

Pracujte se simulátorem MipsPipeS!

Poznámka: Nejpohodlnější způsob zjištění počtu vykonaných instrukcí při simulaci je spočtení “Hit count” a “Miss count” v instrukční cache.

4. 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 s1, $0, 0     // c = 0;
  addi t0, $0, 500   // t0 = 500;
  addi t1, $0, 4     // t1 = 4;
  
  addi s0, $0, 0     // i = 0;
L1:
  addi s1, $0, 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, $0, L2
  addi s0, s0, 1     // i++;
  slt  t3, s0, t0    // t3 = (s0 < t0) ? 1 : 0;
  bne  t3, $0, L1

Table of Contents