Esercizio - Località dei riferimenti, scorrere una matrice per righe o per colonne (laboratorio 7)

Parte 1: i fault con un solo frame

data[20][1024] di byte, con righe da 1024 byte, occupa 20 pagine da 1024 byte: ogni riga è esattamente una pagina. Il C salva le matrici per righe: data[0][0], data[0][1], …, data[0][1023], data[1][0], ….

Programma 1 (for i … for j …): scorre in ordine di indirizzo. Tutta la riga $i$ sta nella pagina $i$: si riferisce la pagina 0 per 1024 volte, poi la 1 per 1024 volte, e così via. Con un solo frame: un fault a ogni cambio di pagina,

$$20\ \text{page fault}.$$

Programma 2 (for j … for i …): per ogni colonna $j$ si visitano le 20 righe, cioè le pagine $0,1,\ldots,19$, e poi si torna alla pagina 0 per la colonna successiva. Con un solo frame ogni accesso cambia pagina: un fault a ogni scrittura,

$$1024\cdot20=20\,480\ \text{page fault}.$$

Lo stesso lavoro, con una differenza di 1024 volte: dipende solo dall'ordine dei cicli (dalla località dei riferimenti).

Parte 2: i due programmi del laboratorio

Con la RAM reale e senza vincolo di un frame, il sistema ha abbastanza memoria: ogni pagina viene caricata (con un page fault) la prima volta che la si tocca e poi resta. La matrice di interi $1024\times1024$ occupa $1024\cdot1024\cdot4=4\text{ MB}$, cioè $4\,\text{MB}/4\,\text{KB}=1024$ pagine da 4 KB. Quindi:

Il commento della slide: con il sistema che assegna abbastanza frame, i TLB e le cache sono "precaricati", quindi il numero di page fault non cambia, cambiano il numero di TLB miss e di cache miss. In generale, il tempo di esecuzione di pagetest2 è molto maggiore di quello di pagetest1.

Il programma completo (in versione con la matrice come variabile statica, per evitare il limite dello stack da 8 MB; in pagetest1.c del corso la matrice è locale: per questo serve ulimit -s unlimited):

/* localita.c - scorrere una matrice per righe o per colonne.
 * Compilare:  gcc -O0 -Wall -Wextra -o localita localita.c
 * Usare:      ./localita righe     oppure     ./localita colonne
 * Misurare:   perf stat -e cache-misses,dTLB-load-misses,dTLB-store-misses,page-faults ./localita righe
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define RIGHE 1024
#define COLONNE 1024

static int dati[RIGHE][COLONNE]; /* 4 MB, nei dati statici: niente problema con lo stack da 8 MB */

int main(int argc, char **argv) {
    if (argc != 2) { fprintf(stderr, "uso: %s righe|colonne\n", argv[0]); return 1; }
    srand(1);
    if (strcmp(argv[1], "righe") == 0) {
        for (int i = 0; i < RIGHE; i++)           /* indirizzi consecutivi: 1 pagina ogni 1024 scritture */
            for (int j = 0; j < COLONNE; j++)
                dati[i][j] = rand();
    } else {
        for (int j = 0; j < COLONNE; j++)         /* salto di 4096 byte a ogni scrittura */
            for (int i = 0; i < RIGHE; i++)
                dati[i][j] = rand();
    }
    printf("%d\n", dati[RIGHE / 2][COLONNE / 2]); /* evita che il compilatore elimini il ciclo */
    return 0;
}

(Compilato qui con zig cc per Linux, senza avvisi; non eseguito: le misure con perf richiedono una macchina Linux, per cui i valori della tabella sono stime ragionate, non misure.)

Parte 3: variare le colonne

Con ROWS = 1024 e COLS $\in\{256,512,1024,2048,4096\}$ la matrice è di $4\cdot1024\cdot\text{COLS}$ byte: 1, 2, 4, 8, 16 MB, cioè 256, 512, 1024, 2048, 4096 pagine. I page fault crescono in modo proporzionale (uno per pagina). I cache miss:

• scorrendo per righe crescono linearmente con $\text{ROWS}\cdot\text{COLS}/16$ (un miss ogni 16 interi consecutivi): è il minimo possibile;
• scorrendo per colonne, il salto fra due accessi è di $4\cdot\text{COLS}$ byte: quando le righe di cache toccate in una colonna (una per riga della matrice, 1024 righe di cache $=64$ KB) non stanno nella cache, ogni accesso è un miss, e il numero cresce come $\text{ROWS}\cdot\text{COLS}$, fino a 16 volte più dei cache miss per righe.

Procedura per la parte di misura: compilare ogni coppia ($\text{ROWS},\text{COLS}$), eseguire 10 volte perf stat, calcolare la media dei cache-misses e fare il grafico (COLS in ascissa, media in ordinata, una curva per ciascun programma). Si può automatizzare con uno script di shell che ripete l'esecuzione e usa perf stat -x, per estrarre il valore. Il grafico atteso: la curva "righe" cresce con pendenza piccola, quella "colonne" con pendenza molto maggiore.

Errori tipici

• Dire che i page fault cambiano molto fra i due programmi quando c'è RAM sufficiente: cambiano TLB e cache.
• Credere che il C salvi le matrici per colonne (è per righe, row-major).
• Confondere pagina del sistema operativo (4096 byte) con riga di cache (64 byte).
• Calcolare i fault con un frame senza accorgersi che ogni riga è una pagina (1024 byte).
• Dimenticare ulimit -s unlimited quando la matrice da 4 MB è una variabile locale.