====== 5. Hierarchický koncept pamětí, cache - 2. část ======
* pro vyučující: [[..:..:internal:tutorials:05:start|cvičení 5]]
===== 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.
===== Opakování =====
Do jaké množiny (setu) se umístí data z adresy 0x1234, pokud použijeme cache o velikosti 512 bajtů, která má blok o velikosti 4 slov (16 bajtů) a má stupeň asociace 2 (dvě cesty)?
Změní se umístění dat, pokud bude mít cache 1024 bajtů a bude mít stupeň asociativity 4 (velikost bloku se nemění)?
===== Úkol A =====
Uvažujte níže uvedený program read_array.S.
.option norelax
.globl pole
.globl _start
.text
_start:
la s0, pole // adresa zacateku pole do registru s0
addi s1, x0, 3 // Pocet pruchodu cyklem (pocet iteraci)
nop // Proc je zde nop? Zkuste jej odranit.. Zmeni se hit rate?
loop:
beq s1, x0, konec
nop
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
nop
konec:
nop
end_loop: //Koncova nekonecna smycka
fence // flush cache memory
ebreak // stop the simulator
j end_loop
nop
.org 0x2000
.data
pole:
.word 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
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(Associativity): ^ 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(Associativity): ^ 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.
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ů.
===== Úkol B =====
Na druhém cvičení jste měli za úkol připravit program, který počítá součet dvou vektorů o délce čtyř prvků. Upravte program pro délku 16 prvků. Umístěte tři vektory tak, aby na sebe navazovaly. Nastavte parametry na 4 sety s bloky o čtyřech slovech při stupni asociativity 2 (32 = 4 x 4 x 2). Politiku nahrazování volte LRU a pro zápis write-back. Nastavte časování souvislého sledu čtení/zápisů (burst) na 2. Sledujte chování pokud se cílový vektor shoduje s jedním ze vstupních. Dále pokud se jedná o tři různé vektory. Dále vložte mezi druhý a třetí vektor 4 slova. Změňte parametry cache na (32 = 2 x 4 x 4).
Vysvětlete pozorované chování.
Pozn. Jelikož máte write-back, tak nezapomeňte nakonec dát instrukci\\
**fence** \\
která vyprázní cache a zapíše do paměti.
===== Úkol C =====
Uvažujte program z minulého cvičení (selection 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í.**
Pro rychlé získání výsledků můžete s výhodou využít verzi simulátoru určenou pro spouštění z příkazové řádky
qtrvsim_cli --i-cache lru,4,1,1 --d-cache lru,4,2,4,wb --burst-time 2 --dump-cache-stats --dump-range array,60,sorted-data.dat selection-sort
Parametry ''--i-cache'' a ''--d-cache'' určují parametry vyrovnávacích pamětí stejně jako z grafické verze simulátoru. ''--burst-time'' nastavuje dobu sekvenčních přístupů na 2 cykly, ''--dump-cache-stats'' určuje vypsání statistiky po skončení programu (dosažení instrukce ''break''). ''--dump-range'' pak umožňuje uložení určitého rozsahu paměti po slovech (adresa může být zadaná i přes návěští). Veškeré parametry aplikace jsou vypsané po zadání parametru ''--help''.
===== 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?
* Jak procesor pozná, která data mají přistát do instrukční cache a která do datové cache?
===== Úkol D =====
Uvažujte následující 3 programy. Který z nich poběží nejrychleji? Který bude nejlépe využívat datovou cache?
minmax1.c
#include
#include
#include
#include
#define SIZE 8388608
long int pole[SIZE];
int main() {
for (int i=0; ipole[i]) {
min = pole[i];
}
}
printf("Min %li max %li\n", min, max);
return 0;
}
minmax2.c
#include
#include
#include
#include
#define SIZE 8388608
long int pole[SIZE];
int main() {
for (int i=0; ipole[i]) {
min = pole[i];
}
}
printf("Min %li max %li\n", min, max);
return 0;
}
minmax3.c
#include
#include
#include
#include
#define SIZE 8388608
#define SIZE2 4096
long int pole[SIZE];
int main() {
int i=0, ii=0;
for (; ipole[ii]) {
min = pole[ii];
}
}
if (ii
Napoveda:
Programy přeložte příkazem:
gcc -g -O2 minmax1.c -o minmax1
Čas běhu programu změříte příkazem:
time ./minmax1
Vyhodnotit jak program pracuje s cahce lze pomocí nástroje cachegrind.
valgrind --tool=cachegrind ./minmax1
kde minmax1 je testovaný program. Pokud chcete program analyzovat detailněji, můžete využít nástroje cg_annotate. Příklad:
cg_annotate cachegrind.out.XXXX ~/minmax1.cpp
kde cachegrind.out.XXXX je jméno souboru vygenerovaného pomocí cachegrind. Cestu k Vašemu zdrojovému souboru (zde minmax1.cpp) uvádějte absolutní. Pozor, program kompilujte s priznakem g (debug info).
Priklad vystupu po anotaci je zde:
{{..:anotace.png?500|}}
===== Úkol E =====
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. Využijte knihovní funkce [[http://man7.org/linux/man-pages/man3/sysconf.3.html|sysconf]], parametry ''_SC_PAGESIZE'', ''_SC_LEVEL1_DCACHE_LINESIZE'' atd. Seznam parametrů, které knihovna [[https://www.gnu.org/software/libc/libc.html|GNU C library (GLIBC)]] nabízí lze najít v jejích zdrojových kódech [[https://sourceware.org/git/?p=glibc.git;a=blob;f=bits/confname.h|bits/confname.h]]. Dokumentace k parametrům [[https://www.gnu.org/software/libc/manual/html_node/Constants-for-Sysconf.html|Constants for Sysconf]].
Porovnejte výsledky s hodnotami, které získáte čtením virtuálních souborů s informacemi od jádra operačního systému například příkazy
cat /proc/cpuinfo
cat /sys/devices/system/cpu/cpu0/cache/index0/size
find /sys/devices/system/cpu/cpu0/cache/ -type f -maxdepth 2 -print -exec cat '{}' ';'
příkazem ''lscpu'' případně ''sudo dmidecode'' na vlastním počítači, kde máte práva adminiztrátora.
===== Úkol F - Virtuální paměť =====
Nebude ve zkoušce APO.
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? Velikost jedné položky strankovací tabulky je 4B.