5. Hierarchický koncept pamětí, cache - 2. část

• pro vyučující: cvičení 5

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.

Do jaké množiny (setu) se umístí data z adresy 0x123458, pokud použijeme cache o velikosti 512 bajtů, která má blok o velikosti 4 slov (16 bajtů) a má stupeň asociativity 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í)?

Jak by se změnilo umístění, pokud budeme mít cache 4096 bajtů, stupeň asociativity 2, velikost bloku 16 slov (64 bajtů)?

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:

• 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.

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í (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.

• 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?

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.

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.

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.