====== 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 =====

**Úkol na cvičení** - cache zjistěte vlastnosti Selection sort a Bubble sort, v němž použijete stejné pole jako v Select sort. 
Pozor, Bubble sort nesmí obsahovat .set noreorder, aby využíval delay slot stejně jako Select sort. Vždy nastavte Replacement Policy = LRU a Writeback policy [Write through No-allocate] a vyplňte tabulku dole pro různé hodnoty počtu setů a stupňů asociativity. 

^Nastaveni cache ^^^Bubble sort ^^^Selection sort ^^^
| Numb.sets | Block size | D.Assoc. | Hit | Miss | Improved | Hit | Miss | Improved |
| 4 | 1 | 1 | | | | | | | |
| 1 | 1 | 4 | | | | | | | |
| 2 | 1 | 2 | | | | | | | |
| 16 | 1 | 1 | | | | | | | | 

==== 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 QtMips, v nastavení simulace zvolte v základním nastavení nejdříve procesor
bez vyrovnávací paměti (No pipline no cache). Kompilovat program již budeme v režimu
kompatibilním s reálnou procesorovou architekturou MIPS, to je s využitým delay-slotem,
jeho plnění vhodnou instrukcí nebo NOP necháme na assembleru (vynecháme volbu .set noreorder).

Nahrajeme přeložený následující program (je k dispozici v adresáři /opt/apo/selection-sort), který řadí 15 čísel (algoritmem známým jako [[https://en.wikipedia.org/wiki/Selection_sort|Selection sort]]). Nahrajte program do simulátoru QtMips a zobrazte okénka se statistikou přístupů do paměti (Window -> Program cache a Window -> Data cache) a poznamenejte si počty přístupů do paměti instrukcí a počet čtení a zápisů do paměti dat a kolik cyklů musel procesor čekat na data z paměti.

V dalším kroku nakonfigurujte simulátor se čtyřmi slovy přímo mapované vyrovnávací paměti pro program a data.

Velikost 4 čtyři slova = počet setů 4 x počet slov v bloku 1 x počet bloků v setu (asociativita) 1.

Označení v přednášce versus QtMips: 
S=počet setů totožné;
B=délka bloku se v QtMips zadává ve 32-bitových slovech;
E-počet řádků v setu odpovídá v QtMips=Degree of Associativity 

{{.:qtmips-newdialog-direct-4-words.png|}}

Vyzkoušejte co nejvíce různých kombinací konfiguračních parametrů při zachování velikosti vyrovnávacích pamětí 4 slova (součin počtu sad, velikosti bloku a úrovně asociativity).
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 a 16 záznamů?

<code>
// Jednoduchy tridici algoritmus - selection sort

.globl    pole
.data
.align    2

// Pro spusteni je nutne nastavit jadro s delay-slotem

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:

//Koncova nekonecna smycka
end_loop:
	cache 9, 0  // vyprazdneni pameti cache
	break       // zastaveni simulatoru
	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 a rychlost simulace Max.

Aby byly výsledky reprodukovatelné, je program zakončený instrukcí, která vyprázdní vyrovnávací paměť a dále instrukcí break, na které se simulace zastaví.
</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, velikost 4 slova = počet setů 1 x počet slov v bloku 1 x počet bloků v setu (asociativita) 4.

{{.:qtmips-newdialog-fully-associtive-4-words.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, velikost 4 slova = počet setů 2 x počet slov v bloku 1 x počet bloků v setu (asociativita) 2.

{{.:qtmips-newdialog-2-way-4-words.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ů?
  - Jaký vliv má volba politiky pro výběr bloku v setu (zkuste politiku LRU a Random)