====== 4. Hierarchický koncept pamětí, cache - 1. část ======
* pro vyučující: [[..:..:internal:tutorials:04:start|cvičení 4]]
===== 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ů?
// Jednoduchy tridici algoritmus - selection sort
// pri kompilaci internim assemblerem je nutne
// vypnout pipelining a delay slot nebo za skoky pridat nop
// Pri kompilaci intrenim assemblerem v QtMips zapni zobrazeni oken
#pragma qtmips show registers
#pragma qtmips show memory
.globl pole
.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
// $at - pomocný registr pro kontrukce v assembleru
hlavni_cyklus:
lw $s4, pole($s0)
add $s3, $s0, $0
add $s2, $s0, $0
vnitrni_cyklus:
lw $s5, pole($s2)
slt $at, $s4, $s5
bne $at, $0, neni_minimum
nop
addi $s3, $s2, 0
addi $s4, $s5, 0
neni_minimum:
addi $s2, $s2, 4
bne $s2, $s1, vnitrni_cyklus
nop
vnitrni_cyklus_end:
lw $s5, pole($s0)
sw $s4, pole($s0)
sw $s5, pole($s3)
addi $s0, $s0, 4
bne $s0, $s1, hlavni_cyklus
nop
hlavni_cyklus_end:
//Koncova nekonecna smycka
end_loop:
cache 9, 0($0) // vyprazdneni pameti cache
break // zastaveni simulatoru
j end_loop
nop
.end _start
.org 0x2000
.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
// Nastav pozici na symbol "pole" v okne zobrazeni pameti
#pragma qtmips focus memory pole
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í.
==== 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)