Warning

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 MipsPipeS
4. Dynamická predikce skoků - příklad

// C program for implementation of selection sort
#include <stdio.h>

#define ARRAY_SIZE 4096

long long int arr[ARRAY_SIZE];

void selectionSort(long long int arr[], int n) {
int i, j, min_idx;
long long int tmp;

// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++) {
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}

// Swap the found minimum element with the first element
tmp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = tmp;
}
}

/* Function to print an array */
void printArray(long long int arr[], int n) {
int i;
for (i=0; i < n; i++)
printf("%lli ", arr[i]);
printf("\n");
}

// Driver program to test above functions
int main() {
int i;
for (i=0; i<ARRAY_SIZE; i++) {
arr[i]=ARRAY_SIZE-i;
}

selectionSort(arr, ARRAY_SIZE);
printArray(arr, ARRAY_SIZE);
printf("Sorted array %lu - %lu: \n", sizeof(long long int), sizeof(arr));
return 0;
}

// C program for implementation of selection sort
#include <stdio.h>

#define ARRAY_SIZE 4096

long long int arr[ARRAY_SIZE];

void selectionSort(long long int arr[], int n) {
int i, j, min_idx;
long long int tmp;

// One by one move boundary of unsorted subarray
for (i = 0; i < n; i++) {
for (j = 0; j < (n-1-i); j++) {
if (arr[j] > arr[j+1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
}

/* Function to print an array */
void printArray(long long int arr[], int n) {
int i;
for (i=0; i < n; i++)
printf("%lli ", arr[i]);
printf("\n");
}

// Driver program to test above functions
int main() {
int i;
for (i=0; i<ARRAY_SIZE; i++) {
arr[i]=ARRAY_SIZE-i;
}

selectionSort(arr, ARRAY_SIZE);
printArray(arr, ARRAY_SIZE);
printf("Sorted array %lu - %lu: \n", sizeof(long long int), sizeof(arr));
return 0;
}


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 následující instr. následující instr. + 1 ——— ——— ——— ——— ——— ——— ——— ——— ——— ——— IF ID EX MEM WB IF(flush) stall stall IF ID EX MEM WB 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 následující instr. následující instr. + 1 —— —— —— —— —— —— —— IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB

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

 skoková instrukce následující instr. cílová instrukce cílová instrukce +1 —— —— —— —— —— —— —— —— IF ID EX MEM WB IF idle idle idle idle IF ID EX MEM WB 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 následující instr. (slot) následující instr. + 1 následující instr. + 2 —— —— —— —— —— —— —— —— IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB

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

 skoková instrukce následující instr. (slot) cílová instr. cílová instr. + 1 —— —— —— —— —— —— —— —— IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB 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 bne$t0, $0, 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): 1. 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 2. Výpočet realizujeme na procesoru dle simulátoru MipsPipeXL , tzn. mezivýsledky se přeposílají, skoky se predikují jako nerealizované (not taken) 3. 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: .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:
break
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