====== 6. Pipeline a hazardy ======
  * pro vyučující [[..:..:internal:tutorials:06:start|cvičení 6]]

<note important>**Co bych si měl na cvičení zopakovat/připravit**
  - Struktura single cycle procesoru
  - Struktura pipelined processoru
  - Datových hazardy
</note>


===== Osnova cvičení =====

  - Struktura procesoru
  - Pipeline
  - Fibonacciho posloupost na pipeline 
  - Bubble sort na pipeline


===== Zkuste si program ====
<code>
.globl _start

.option norelax

.text
_start:

main:

    addi  x2,  x0, 10
    add   x11, x0, x2   // A : x11<-x2
    add   x12, x0, x2   // B : x12<-x2
    add   x13, x0, x2   // C : x13<-x2

la_auipc_inst_addr:
    la x5, varx  // $5 = (byte*) &varx; 
    // The macro-instruction la is compiled as two following instructions:
    //auipc x5, %pcrel_hi(varx) // load the upper part of address
    //addi  x5, x5, %pcrel_lo(la_auipc_inst_addr) // append the lower part of address
    // they compute and load address as relative to the PC, absolute load address alternative
    //lui   x5, %hi(varx) // load the upper part of address
    //addi  x5, x5, %lo(varx) // append the lower part of address
    // It can be replaced by simple single addi if varx is located lower than 0x800
    //addi  x5,  x0, varx

    lw    x1, 0(x5)     // x1 = *((int*)$5);
    add   x15, x0, x1   // D : x15<-x1
    add   x16, x0, x1   // E : x16<-x1
    add   x17, x0, x1   // F : x17<-x1
loop:
    ebreak
    beq    x0, x0, loop
    nop

.data
.org 0x400
varx:
	.word  0x1234
</code>

Odkrokujte si ho:
    - napřed s vypnutým pipeline, 
    - poté si aktivujte pipeline, ale bez hazard unit. 
    - nakonec navolte pipeline s hazard unit. 

//Pozn. Datová a instrukční cache jsou zde nepodstatné, můžete je obě deaktivovat.//

Sledujte nejen výsledné hodnoty v registrech, ale i případné stall stavy, 
je-li aktivní hazard unit.
   * Kdy instrukce označené A, B, C, D, E a F dají správné výsledky?
   * Kolik cyklů bude potřebovat celý program?

__Počet cyklů Vašeho programu__ se v QtRVSim zobrazuje vpravo v okně procesoru. 


**Otázka k zamyšlení**: Pokud QtRVSim potřeboval více cyklů hodin se zapnutým pipeline než bez něho, znamená to tedy, že pipeline procesor běží pomaleji, nebo ne? 

**Navrhněte vylepšení**: Popřemýšlejte, jak program upravit, aby více vyhovoval pipeline zpracování. Lze v něm snížit počet stall, či ho modifikovat dokonce tak,
aby běžel i bez hazard unit?


===== Úloha - Kopírování pole =====

<code>
.globl _start
.option norelax

.text
_start:
    addi t0, x0, 5
    lui   s1, 4
    addi s1, s1, 0x400
    lui   s0, 4
loop:
    lw t1, 0(s0)
    sw t1, 0(s1)
    addi s1, s1, 4
    addi s0, s0, 4
    addi t0, t0, -1   
    bne t0, x0, loop
    ebreak
  

.data
.org 0x4000
arr1:
	.word  10,11,12,13,14,15,16
.org 0x4400
arr2:
	.word  1,1,1,1,1,1,1,1,1,1,1
</code>

Zjistěte, co přesně program dělá.

Změnou pořadí instrukcí zajistěte, aby program fungoval správně i pro CPU s pipeliningem bez hazard unit. Kolik musíte vložit instrukcí nop? Najděte řešení, aby těchto nop bylo v těle cyklu co nejméně a aby program fungoval stejně (můžete změnit agrumenty některých instrukcí). Upravený program musí fungovat i na procesorech s hazard unit.

===== Úloha - Fibonacciho čísla =====

Na 3. cvičení byl zadaný příklad na výpočet N-tého [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho čísla]] s ukládáním posloupnosti do paměti. Pro zopakování, předpis funkce
<code>
 F(n) = F(n-1) + F(n-2), for n > 2, and F(0) = 0, F(1) = 1.
</code>
a několik počátečních členů [[https://en.wikipedia.org/wiki/Fibonacci_number|Fibonacciho řady]]: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,… 

Modifikujte svůj program tak, aby správně běžel i na pipeline procesoru. 
Zapište jím 20 prvních členů posloupnosti, tj. hodnoty 0, 1, 1, 2, ..., 4181 (0x1055), 6765 (0x1A6D) do paměti.


Můžete využít následující šablonu asembleru:
<code>
.globl _start
.option norelax

_start:
// Zde je misto pro Vas vlastni kod...
   addi t0, x0, 0x400   //  la t0, fibonacci bez hazardu

    ebreak 

.data
.org 0x400
fibonacci:
	.word  0x1234
</code>


Program odlaďte:

  - Nejdříve na simulátoru QtRVSim nakonfigurovaným na jednoduchý procesor bez vyrovnávací paměti a zřetězeného zpracování instrukcí (pipeline). 
  - Poté přepněte na zřetězené zpracování s jednotkou hazardů. Algoritmus by měl stále vydávat předpokládané výsledky. 
  - Následně vypněně jednotku detekce hazardů. Procesor se tím zjednoduší, ale algoritmus přestane vracet očekávané hodnoty. 
  - Zamyslete se, jak by asi měl kompilátor upravit kód pro zřetězený procesor s vypnutou detekcí hazardů, aby nadále vykonával stejnou funkci jako standardní RISC V. Upravte kód v assembleru tak, aby nedocházelo k nechtěnému vlivu datových hazardů, tj. musíte buď změnit pořadí instrukcí nebo vložit NOP instrukce.

Vaším úkolem bude dosáhnout minima použití NOP.


===== Zápis řady do paměti =====

Modifikujte předchozí program pro výpočet členů Fibonacciho posloupnosti, aby jednotlivé členy řady zapsal do datové paměti od návěští fibonacci (instrukce sw). Pro výpočet dalšího členu tentokrát využívejte předchozí členy načtené z paměti (instrukce lw). Vykonávání programu sledujte v simulátoru QtRVSim.


=== Kontrolní otázky: ===
  * Jak se realizuje instrukce add?
  * Jak se realizuje instrukce addi?
  * Jak se realizuje instrukce lw?
  * Jak se realizuje instrukce sw?
  * Kolik taktů trvá než je známa adresa větvení a jak se zjišťuje? (instrukce beq a bne)
  * Sledujte vykonání programu v simulátoru QtRVSim pro variantu bez pipeline, s pipeline bez a s zapnutou jednotkou řešení hazardů. Sledujte jak se liší doba vykonávání programu pro případ, kdy jsou hazardy řešené pozastavením, a případ, kdy je použitý forward. Pokuste se pro každou variantu navrhnout algoritmus, který je vykonán v nejkratším čase. Především se zaměřte na variantu bez a s řešením hazardů v hardware. Počet potřebných cyklů do dosažení instrukce ''break'' můžete odečíst například z počtu čtení z paměti programu spočítanému v okně programové vyrovnávací paměti.

===== Lineární kód pro sledování postupu instrukcí pipeline =====

<note tip>V laboratoři dispozici na ''/opt/apo/pipe-test''</note>

<code>
.globl _start
.text
.set noat
.set noreorder

_start:
  nop
  nop
  nop
  nop
  nop
  addi t0,x0,0
  addi t1,x0,0
  addi t2,x0,0
  addi t3,x0,0
  addi t4,x0,0
  addi t5,x0,0
  addi t6,x0,0
  addi s1,x0,0x11
  addi s2,x0,0x22
  addi s3,x0,0x33
  addi s4,x0,0x44
  addi s5,x0,0x55
  addi s6,x0,0x66
  addi s7,x0,0x77
  addi s8,x0,0x88
  addi s9,x0,0x99
  nop
  nop
  nop
_test:
  addi t0,s1,0     // registr t0 bude za čtyři takty nastaven na 0x1111
  // registr s1 změní hodnotu na 0x1133, ale v MipsPipeS tato
  // změna trvá ještě tři hodinové takty, následující dvě instrukce
  // vidí předchozí hodnotu registru
  addi s1,s1,0x22
  add  t1,x0,s1    // t1 se nastaví na starou hodnotu 0x1111
  add  t2,x0,s1    // t2 bude bez přeposílání také ještě nastaveno na 0x1111
  add  t3,x0,s1    // zápis s1 do registru proběhl, t3 bude nastaveno na 0x1133
  beq  x0,x0,skip
  // řídicí hazard
  // načtení dalších instrukcí a pak jejich zahození
  add  t5,x0,s1    
  add  t6,x0,s1    
  add  s2,x0,s1    
  add  s3,x0,s1    
skip:
  nop
  nop
  ebreak
</code>