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

===== Náplň cvičení =====
Cílem tohoto cvičení je prohloubit znalosti o cache, ujasnit a na příkladu ukázat principy časové a prostorové lokality, a zamyslet se nad otázkou optimalizace parametrů cache.
===== Úkol A =====
Uvažujte níže uvedený program.
<code>
#define s0 $16
#define s1 $17
#define s2 $18

.globl    pole
.data
.align    2

pole:
.word    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
.text
.globl start
.ent start

start:

la   s0, pole       // adresa zacateku pole do registru s0
addi s1, $0, 3      // Pocet pruchodu cyklem (pocet iteraci)
nop                 // Proc je zde nop? Zkuste jej odranit.. Zmeni se hit rate?

loop:
    beq s1,$0, konec
    lw s2, 0(s0)      // Cteni 0-teho prvku pole
    lw s2, 4(s0)      // Cteni 1. prvku (4/4=1)

    lw s2, 36(s0)     // Cteni 9. prvku (36/4=9)
    lw s2, 40(s0)     // Cteni 10.prvku (40/4=10)
   
    addi s1, s1, -1
    j loop

konec:
nop  

end_loop:           //Koncova nekonecna smycka
    j end_loop
    nop

.end start
</code>

Dále uvažujte instrukční a datovou slovně zarovnanou cache, každou **o velikosti 8 slov** (1 slovo = 4B), strategie nahrazování (Replacement policy) LRU. Vyplňte následující tabulku pro instrukční a pro datovou cache. **Detailně sledujte vykonávání programu a přístupy do cache. **\\  \\
** Datová cache: **
^ ^  Přímo mapovaná  ^^^  Se sníženým \\ stupňem \\ asociativity  ^  Plně asociativní  ^^^^
^  Size/Block size/Blocks in sets: ^  8/1/1  ^  8/2/1  ^  8/8/1  ^  8/2/2  ^  8/4/2  ^  8/2/4  ^  8/1/8  ^
| Hit Count:  | | | | | | | |
| Miss Count:  | | | | | | | |
| Hit Rate:  | | | | | | | |
\\

** Instrukční cache: **
^ ^  Přímo mapovaná  ^^^  Se sníženým \\ stupňem \\ asociativity  ^  Plně asociativní  ^^^^
^  Size/Block size/Blocks in sets: ^  8/1/1  ^  8/2/1  ^  8/8/1  ^  8/2/2  ^  8/4/2  ^  8/2/4  ^  8/1/8  ^
| Hit Count:  | | | | | | | |
| Miss Count:  | | | | | | | |
| Hit Rate:  | | | | | | | |
\\

===== Kontrolní otázky =====
  * K jakému závěru jste přišli? Která cache je nejlepší?
  * Je plně asociativní cache vždy nejlepší?
  * Závisí Hit rate od vykonávaného programu, nebo je to parametr cache?
  * Můžou být v cache data, která procesor nikdy nevyužije? (data, které nežádá, nebo instrukce, které nikdy nevykoná)
  * Jaká je ideální velikost bloku? Od čeho se tento parametr odvíjí?
  * Která cache je pro danou velikost nejlevnější?
  * Co všechno se do cache ukládá?
  * Jakou instrukční a datovou cache má procesor Vašeho počítače? Uveďte parametry velikost cache, počet cest a velikost bloku.
<note>
Přímo mapovaná cache má právě jeden blok v jednom set-u. Plně asociativní cache má právě tolik cest (ways), kolik obsahuje bloků.
</note>

===== Úkol B =====
Uvažujte program z minulého cvičení (insert sort) a cache o velikosti 8 slov. Pro jakou strategii nahrazování (Replacement policy) lze očekávat dosažení nejlepších výsledků? Uvažujte i pro datovou i pro instrukční cache. **Ověřte simulací.**

===== Kontrolní otázky =====
  * Bude cache dosahovat nejlepší Hit rate pro ty samé parametry (Size/Block size/Blocks in sets) jako v předchozím příkladu?
  * Znáte i jiné strategie nahrazování než ty, které jsou k dispozici v simulátoru Mips? Najděte na internetu nebo v přednáškách. 
  * Pro jakou strategii zápisu (Write policy) lze očekávat, že datová cache nebude zbytečně zaťežovat sběrnici?

===== Úkol C  - Virtuální paměť =====
Doplňující otázky:
  *  Jak funguje překlad virtuální adresy na adresu fyzickou?
  * K čemu slouží "page directory base register"?
  * Jaké informace jsou uloženy v položce tabulky stránek?
  * Pokud jednotka pro správu paměti 32-bit procesoru s 32-bit virtuální i fyzickou adresou používá pro mapování fyzické paměti do virtuálních adresních prostorů systém stránkování a velikost jedné stránky je 4 kB, kolik úrovní tabulek bude využito, pokud je požadované, aby se části stránkovací tabulky každé úrovně vešly právě do jedné stránky paměti a jak bude virtuální adresa rozdělena?




===== Úkol D   =====
Napište program v C/C++, který zjistí a na obrazovku vypíše parametry cache pamětí Vašeho procesoru (procesoru, na kterém program běží) a velikost stránky virtuální paměti.

===== Úkol E   =====

Prepiste program insert sort z minuleho cviceni do jazyka C/C++. Zmerte hit rate instrukcni a datove cache prvni urovne, a dale hit rate cache posledni urovne -- pokud program spustite na Vasem pocitaci (ucebna KN:2). Kolik pristupu do datove pameti se realizovalo? Kolik se vykonalo instrukci celkem? Zkuste menit uroven optimalizaci pri kompilaci.


Napoveda:Vyhodnotit jak program pracuje s cahce lze pomocí nástroje cachegrind.
<code> 
valgrind --tool=cachegrind ./a.out
</code>
kde a.out je Vas program. Pokud chcete program analyzovat detailněji, můžete využít nástroje cg_annotate. Příklad: 
<code>
cg_annotate filename ~/main.cpp
</code>
kde filename je jméno souboru vygenerovaného pomocí cachegrind. Cestu k Vašemu zdrojovému souboru (main.cpp) uvádějte absolutní. Pozor, program kompilujte s priznakem g (debug info). 

Pozn.: Pri nedostatku casu muzete pouzit bubble sort z cviceni c.3.

Priklad vystupu po anotaci je zde:

{{anotace.png?500|}}