6. Pipeline a hazardy

• pro vyučující cvičení 6

1. Fibonacciho posloupost na pipeline
2. Bubble sort na pipeline

1. Porozumět přednášce o pipeline procesoru a datových hazardech

.globl _start
.set noat
.set noreorder

.text
_start:

main:

    addi  $2,  $0, 10
    add   $11, $0, $2   // A : $11<-$2
    add   $12, $0, $2   // B : $12<-$2
    add   $13, $0, $2   // C : $13<-$2

    la $5, varx  // $5 = (byte*) &varx; 
    // The macro-instruction la is compiled as two following instructions:
    //lui   $5, %hi(varx) // load the upper part of address
    //ori   $5, $5, %lo(varx) // append the lower part of address

    lw    $1, 0($5)     // $1 = *((int*)$5);
    add   $15, $0, $1   // D : $15<-$1
    add   $16, $0, $1   // E : $16<-$1
    add   $17, $0, $1   // F : $17<-$1
loop:
    break
    beq    $0, $0, loop
    nop

.data

varx:
	.word  1

Odkrokujte si ho:

1. napřed s vypnutým pipeline,
2. poté si aktivujte pipeline, ale bez hazard unit.
3. 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 QtMips zobrazuje dole v okně procesoru.

Otázka k zamyšlení: Pokud QtMips 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?

Na 3. cvičení byl zadaný příklad na výpočet N-tého Fibonacciho čísla s ukládáním posloupnosti do paměti. Pro zopakování, předpis funkce

 F(n) = F(n-1) + F(n-2), for n > 2, and F(0) = 0, F(1) = 1.

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:

.globl start
.set noat
.set noreorder
.ent start

start:
// Zde je misto pro Vas vlastni kod...

nop
.end start

Program odlaďte:

1. Nejdříve na simulátoru QtMips nakonfigurovaným na jednoduchý procesor bez vyrovnávací paměti a zřetězeného zpracování instrukcí (pipeline). Volba delay slot musí ale být zapnutá, pipeline procesor ho vždy používá.
2. 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.
3. Následně vypněně jednotku detekce hazardů. Procesor se tím zjednoduší, ale algoritmus přestane vracet očekávané hodnoty.
4. 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í MIPS. 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.

Pokud je v programu

.set noreorder

Když nezadáte “noreorder”, pak se assembler postará o standardní vyplňování delay slotů, přičemž zkoumá předchozí instrukci. Pokud ta nezapisuje do registru, na kterém závisí skok, a navíc se před ní nenachází návěští, bude ve výsledném binárním kódu posunutá až za instrukci skoku. Není-li to splněné, za skok se vloží NOP.

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

Modifikujte předchozí program pro výpočet členů Fibonacciho posloupnosti, aby jednotlivé členy řady zapsal do datové paměti od návěští fibo_series (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 QtMips.

• 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 QtMips 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.

Adresář s Makefile naleznete na cestě

/opt/apo/pipe-test

Testovací příklad

.globl start
.globl _start
.set noat
.ent start
.set noreorder

start:
_start:
  nop
  nop
  nop
  nop
  nop
  addi $t0,$0,0
  addi $t1,$0,0
  addi $t2,$0,0
  addi $t3,$0,0
  addi $t4,$0,0
  addi $t5,$0,0
  addi $t6,$0,0
  addi $t7,$0,0
  addi $t8,$0,0
  addi $s1,$0,0x1111
  addi $s2,$0,0x2222
  addi $s3,$0,0x3333
  addi $s4,$0,0x4444
  addi $s5,$0,0x5555
  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,$0,$s1    // t1 se nastaví na starou hodnotu 0x1111
  add  $t2,$0,$s1    // t2 bude bez přeposílání také ještě nastaveno na 0x1111
  add  $t3,$0,$s1    // zápis s1 do registru proběhl, t3 bude nastaveno na 0x1133
  beq  $0,$0,skip
  // Jedna instrukce za skokem má být provedena - architekturou definovaný
  // delay slot
  add  $t5,$0,$s1    // Provede se a měla se provést
  add  $t6,$0,$s1    // V MipsPipeS se provede, ale neměla by se provést
  add  $t7,$0,$s1    // t7 se také nastaví na 0x1133
  add  $t8,$0,$s1    // tato instrukce již provedena nebude, pc bylo nastavené na skip
skip:
  nop
.end start

V simulátoru QtMips není varianta zřetězeného zpracování s porovnáním obsahu registrů pro určení podmínky skoku až ve fázi execute implementovaná. Toto chování je možné demonstrovat na simulátoru MipsIt. Tento simulátor lze spustit v požadované variantě příkazem

mipsit-mipspipes

Váš kód zkompilovaný do formátu srec naleznete v simulátoru MipsIt na cestě Z:\home\<login>\..