Search
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.
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:
Instrukční cache:
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.
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í.
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 pole,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.
–i-cache
–d-cache
–burst-time
–dump-cache-stats
break
–dump-range
–help
Uvažujte následující 3 programy. Který z nich poběží nejrychleji? Který bude nejlépe využívat datovou cache?
minmax1.c
#include <stdio.h> #include <stdlib.h> #include <fcntl.h> #include <unistd.h> #define SIZE 8388608 long int pole[SIZE]; int main() { for (int i=0; i<SIZE; i++) { pole[i] = (random()%10000) - 5000; } long int max=pole[0]; long int min=pole[0]; for (int i=1; i<SIZE; i++) { if (max<pole[i]) { max = pole[i]; } } for (int i=1; i<SIZE; i++) { if (min>pole[i]) { min = pole[i]; } } printf("Min %li max %li\n", min, max); return 0; }
minmax2.c
#include <stdio.h> #include <stdlib.h> #include <fcntl.h> #include <unistd.h> #define SIZE 8388608 long int pole[SIZE]; int main() { for (int i=0; i<SIZE; i++) { pole[i] = (random()%10000) - 5000; } long int max=pole[0]; long int min=pole[0]; for (int i=1; i<SIZE; i++) { if (max<pole[i]) { max = pole[i]; } if (min>pole[i]) { min = pole[i]; } } printf("Min %li max %li\n", min, max); return 0; }
minmax3.c
#include <stdio.h> #include <stdlib.h> #include <fcntl.h> #include <unistd.h> #define SIZE 8388608 #define SIZE2 4096 long int pole[SIZE]; int main() { int i=0, ii=0; for (; i<SIZE2;) { pole[i++] = (random()%10000) - 5000; } long int max=pole[0]; long int min=pole[0]; for (; ii<SIZE;) { for (int j=0; j<SIZE2; j++, ii++) { if (max<pole[ii]) { max = pole[ii]; } if (min>pole[ii]) { min = pole[ii]; } } if (ii<SIZE) { for (int j=0; j<SIZE2; j++) { pole[i++] = (random()%10000) - 5000; } } } printf("Min %li max %li\n", min, max); return 0; }
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
cg_annotate cachegrind.out.XXXX ~/minmax1.cpp
Priklad vystupu po anotaci je zde:
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 sysconf, parametry _SC_PAGESIZE, _SC_LEVEL1_DCACHE_LINESIZE atd. Seznam parametrů, které knihovna GNU C library (GLIBC) nabízí lze najít v jejích zdrojových kódech bits/confname.h. Dokumentace k parametrům Constants for Sysconf.
_SC_PAGESIZE
_SC_LEVEL1_DCACHE_LINESIZE
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.
lscpu
sudo dmidecode
Nebude ve zkoušce APO.
Doplňující otázky: