====== 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.
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 QtRVSim, v nastavení simulace zvolte v základním nastavení nejdříve procesor
bez vyrovnávací paměti (No pipline no cache).
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 QtRVSim 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 QtRVSim:
S=počet setů totožné;
B=délka bloku se v QtRVSim zadává ve 32-bitových slovech;
E-počet řádků v setu odpovídá v QtRVSim=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ů?
// Simple sorting algorithm - selection sort
// Directives to make interesting windows visible
#pragma qtrvsim show registers
#pragma qtrvsim show memory
.option norelax
.globl array
.globl _start
.text
_start:
la a0, array
addi s0, zero, 0 //Minimum value from the rest of the array will be placed here. (Offset in the array, increasing by 4 bytes).
addi s1, zero, 60 // Maximal index/offset value. Used for cycle termination = number of values in array * 4.
add s2, zero, s0 //Working position (offset)
// s3 - offset of the smallest value found so far in given run
// s4 - value of the smallest value found so far in given run
// s5 - temporary
main_cycle:
beq s0, s1, main_cycle_end
add t0, a0, s0
lw s4, 0(t0) // lw s4, array(s0)
add s3, s0, zero
add s2, s0, zero
inner_cycle:
beq s2, s1, inner_cycle_end
add t0, a0, s2
lw s5, 0(t0) // lw s5, array(s2)
// expand bgt s5, s4, not_minimum
slt t0, s4, s5
bne t0, zero, not_minimum
addi s3, s2, 0
addi s4, s5, 0
not_minimum:
addi s2, s2, 4
j inner_cycle
inner_cycle_end:
add t0, a0, s0
lw s5, 0(t0) // lw s5, array(s0)
sw s4, 0(t0) // sw s4, array(s0)
add t0, a0, s3
sw s5, 0(t0) // sw s5, array(s3)
addi s0, s0, 4
j main_cycle
main_cycle_end:
//Final infinite loop
end_loop:
fence // flush cache memory
ebreak // stop the simulator
j end_loop
.org 0x400
.data
// .align 2 // not supported by QtRVSsim
array:
.word 5, 3, 4, 1, 15, 8, 9, 2, 10, 6, 11, 1, 6, 9, 12
// Specify location to show in memory window
#pragma qtrvsim focus memory array
**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í ebreak, 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 RISC-V 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 RISC-V 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)