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


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

  - Fibonacciho posloupost 
  - Přepis programu z jazyka C do assembleru
  - Simulace a ladění programu pro nezřetězený procesor (simulátor Mips)
  - Simulace a ladění programu pro zřetězený procesor (simulátor MipsPipeS)

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

  - Rozumět předchozí přednášce

===== Náplň cvičení =====

Napište program pro výpočet N-tého Fibonacciho čísla pro N>2. Fibonacciho posloupost je definována nasledovně:
F(n) = F(n-1) + F(n-2), pro n>2,
přičemž F(0) = 0 a F(1) = 1.
Prvních několik členů této posloupnosti je: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...

K vypočtenému číslu pak přičtěte konstantu 15. Hodnotu N zvolte 5. K dispozici máte tyto instrukce:
  * add, addi, bne, beq.

\\ 

Bližší popis instrukcí:
^ Instrukce ^ Syntax ^ Operace ^ Význam ^
| Add   | <nowiki>add \$d, \$s, \$t</nowiki>   | <nowiki>\$d = \$s + \$t;</nowiki>   | Sečte dva registry <nowiki>\$s + \$t</nowiki> a výsledek uloží do registru <nowiki>\$d</nowiki> |
| Addi   | <nowiki>addi \$t, \$s, imm</nowiki>   | <nowiki>\$t = \$s + imm;</nowiki>   | Sečte hodnotu v <nowiki>\$s</nowiki> a znaménkově rozšířenou přímou hodnotu, a výsledek uloží do <nowiki>\$t</nowiki> |
| Bne   | <nowiki>bne \$s, \$t, offset</nowiki>   | <nowiki>if \$s != \$t go to PC+4+4*offset; else go to PC+4</nowiki>   | Skáče pokud si registry <nowiki>\$s</nowiki> a <nowiki>\$t</nowiki> nejsou rovny |
| Beq   | <nowiki>beq \$s, \$t, offset</nowiki>   | <nowiki>if \$s == \$t go to PC+4+4*offset; else go to PC+4</nowiki>   | Skáče pokud si registry <nowiki>\$s</nowiki> a <nowiki>\$t</nowiki> jsou rovny |

\\ 
\\ 
Poznámka: Nepoužívejte instrukci j (jump). V zřetězeném procesoru (MipsPipelineS) není podporována!
\\
\\

Možný přepis problému do jazyka C:
<code C>
t0 = 5;  //  Nastaveni hodnoty N
s0 = 0;  //  F(0)
s1 = 1;  //  F(1)

for(t1 = 2; t1 <= t0; t1++)
{
	t2 = s0 + s1;
	s0 = s1;
	s1 = t2;
}
s1 += 15;

while(1)
	;   // Nekonečná smyčka
</code>

\\ 
Pro přepis programu z jazyka C do assembleru můžete využít následující šablonu:
<code>
#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:
// Zde je místo pro Váš vlastní kód...

nop
.end start
</code>


\\ 
Pracujte nejdřív se simulátorem Mips, pak MipsPipeS.
\\ 
\\ 

Všimětě si, že o standardní vyplňování delay slotů za instrukcemi
skoků se stará přímo assembler. Když není před předchozí
instrukcí přítomné návěští, posune ji ve výsledném binárním
kódu za instrukci skoku. Jinak doplní NOP. Toto chování
assembleru lze vypnout pseudoinstrukcí

<code>
.set noreorder
</code>

Zkuste se zamyslet nad pravidly pro kompilátor, který by připravoval
kód pro procesor MipsPipeS tak, aby vykonával pro předložený kód
funkci stejnou jako standardní Mips.

===== Když zůstane čas, aneb pro ty, kteří by se začínali nudit =====

Modifikujte předchozí program tak, aby se výsledek (tedy F(N)+15) zapsal do datové paměti na adresu 0x02 (instrukce sw) a následně tuto hodnotu přečtěte (instrukce lw). Vykonávání programu sledujte v simulátoru MipsPipeS, případně i v MipsPipeXL.


=== 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 vykonani programu v simulatoru **MipsPipeXL**. Ten najdete v **/opt/mipsit/bin/MipsPipeXL.exe**. Je potreba vybrat program pro otevreni souboru "wine". Wine se nachazi v **/opt/wine-2.3/bin/wine**

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

Adresář s Makefile naleznete na cestě
<code>
/opt/apo/pipe-test
</code>

Testovací příklad

<code>
#define zero	$0
#define AT	$1
#define v0 	$2
#define v1	$3
#define a0	$4
#define a1	$5
#define a2	$6
#define	a3	$7

#define t0	$8
#define t1	$9
#define t2	$10
#define t3	$11
#define t4	$12
#define t5	$13
#define t6	$14
#define t7	$15
#define t8	$24
#define t9	$25
#define k0	$26
#define k1	$27

#define s0	$16
#define s1	$17
#define s2	$18
#define s3	$19
#define s4	$20
#define s5	$21
#define s6	$22
#define s7	$23

#define gp	$28
#define sp	$29
#define fp	$30
#define ra	$31

.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
</code>