====== 4. Hierarchický koncept pamětí, cache - 1. část ======
  * [[..:..:internal:tutorials:04:start|pro vyučující]]

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

  - Motivační příklad
  - Návrh a princip práce cache


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

  - Zopakovat si jak pracuje cache
  - Zopakovat si co znamená 
     - plně asociativní cache
     - cache s omezeným stupněm asociativity
     - přímo mapovaná cache
  - Zopakovat si význam pojmů write-through a write-back.
  - Dokončit program pro Bubble sort z minulého cvičení.


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

=== Motivační příklad ===

A. Za jakou dobu provede procesor s taktovací frekvencí 1GHz 1000 instrukcí za předpokladu, že jednu instrukci provede za jeden takt?

B. Za jak dlouho provede tento procesor 1000 instrukcí za předpokladu, že 20% instrukcí jsou přístupy do paměti. Pro jednoduchost předpokládejme, že jeden přístup do paměti trvá 70 ns.

C. Jak se změní doba potřebná k vykonání instrukcí, když nahradíme procesor 2 GHz verzí, ale paměti zůstanou stejné?

D. Jak se změní doba, když ponechám původní 1 GHz procesor, ale přidám do systému cache? Tato cache má hit rate 80% pro daný program a doba nalezení záznamu v cache je 5ns.


===== Cache =====

V dalším textu budeme pracovat s adresou délky 12 bitů, data jsou 8bitů široká.

==== Přímo mapovaná cache ====

  - Nakreslete přímo mapovanou cache s 4 záznamy.
  - Jak naleznu správný záznam pro uložení dat? Kolik bitů bude obsahovat tag?

== Ukázka ==

Spusťte simulátor Mips, zobrazte datovou cache a v menu Edit > Cache/Mem Config a na záložce Data Cache nastavte parametry podle obrázku:

{{data_cache-direct_mapped.png|}}

Nyní otevře vývojové prostředí MipsIt, přeložte následující program, který řadí 15 čísel (algoritmem známým jako Insertion sort). Nahrajte program do simulátoru Mips a sledujte, jak se mění obsah cache a odpovězte na následující otázky:
  - Kolik je hit count/miss count?
  - Kolik přístupů do paměti se vykoná?
  - Jak se změní tyto počty pokud velikost cache zvýšíte na 8 záznamů?


<code>
#define s0 $16
#define s1 $17
#define s2 $18
#define s3 $19
#define s4 $20
#define s5 $21

.globl    pole
.data
.align    2

pole:
.word    5, 3, 4, 1, 15, 8, 9, 2, 10, 6, 11, 1, 6, 9, 12

.text
.globl start
.ent start

start:

addi s0, $0, 0  //Pozice pro kterou se aktualne hleda minimum (offset do pole, zvysuje se po 4 bajtech)
addi s1, $0, 60 //Maximalni hodnota indexu/offsetu. Slouzi k ukonceni cyklu = pocet prvku v poli * 4 (aktualne 15 * 4)
add  s2, $0, s0 //Pracovni pozice (offset), prvek 
// s3 - offset nejmensiho nalezeneho prvku v aktualnim behu
// s4 - hodnota nejmensiho nalezeneho prvku
// s5 - tmp

hlavni_cyklus:
	beq s0, s1, hlavni_cyklus_end
	
	lw s4, pole(s0)
	add s3, s0, $0
	add s2, s0, $0
	
	vnitrni_cyklus:
	beq s2, s1, vnitrni_cyklus_end
		
		lw s5, pole(s2)
		
		bgt s5, s4, neni_minimum
			addi s3, s2, 0
			addi s4, s5, 0
neni_minimum:
		addi s2, s2, 4
		j vnitrni_cyklus
vnitrni_cyklus_end:
	lw s5, pole(s0)
	sw s4, pole(s0)
	sw s5, pole(s3)
	
	addi s0, s0, 4
	j hlavni_cyklus
hlavni_cyklus_end:

//Koncová nekonečná smycka
end_loop:
	j end_loop

nop
.end start

</code>


<note>
Rada: Pokud potřebujete projít dlouhý program a zajímá vás pouze výsledek na konci běhu programu, můžete použít tlačítko Run, kterým spustíte běh programu. Pro zastavení automatického běhu, použijte tlačítko Stop.

Aby procesor nezačal vykonávat nesmyslné instrukce za koncem vašeho programu, které by mohli ovlivnit výsledek, je potřeba nakonec přidat nekonečnou smyčku. V té procesor uvázne a nezačne vykonávat nesmyslné instrukce, které mohly zůstat v paměti za koncem vašeho programu.
</note>

==== Plně asociativní cache ====

  - Jak se liší plně asociativní cache od přímo mapované cache?
  - Nakreslete plně asociativni cache pro 4 záznamy (12 bitů adresa a 8bitů data).
  - Jak naleznu správné místo pro uložení dat?

== Ukázka ==

V simulátoru Mips nastavte datovou cache podle obrázku (Size 4, Block size 1 a Blocks in sets 4).

{{data_cache-fully_associative.png|}}

Nyní spusťte program znovu a sledujte chování cache. 

  - Kolik je hit count/miss count?
  - Kolik přístupů do paměti se vykoná?
  - Jak se změní tyto počty pokud velikost cache zvýšíte na 8 záznamů?


==== Cache s omezeným stupněm asociativity ====

  - Jak se liší od předchozích variant cache? Je v něčem výhodnější, než předchozí varianty?
  - Nakreslete cache se stupněm asociativity omezeným na 2. Velikost cache jsou 4 záznamy (12 bitů adresa a 8bitů data).
  - Jak naleznu správné místo pro uložení dat?

== Ukázka ==

V simulátoru Mips nastavte datovou cache podle obrázku (Size 4, Block size 1 a Blocks in sets 2).

{{data_cache-reduced_associativity.png|}}

Nyní spusťte program znovu a sledujte chování cache. 

  - Kolik je hit count/miss count?
  - Kolik přístupů do paměti se vykoná?
  - Jak se změní tyto počty pokud velikost cache zvýšíte na 8 záznamů?