Come funziona la memoria cache?

Question

Oggi, quando ero in classe di organizzazione informatica, l'insegnante ha parlato di qualcosa di interessante per me. Quando si parla di perché la memoria cache funziona, ha detto che:

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

non è bene cambiare la prima riga con la seconda. Qual è la tua opinione su questo? E perché è così?

Answer 1

Località di riferimento. Poiché i dati sono archiviati per righe, per ogni riga le colonne j si trovano in indirizzi di memoria adiacenti. Il sistema operativo in genere carica un'intera pagina dalla memoria nella cache e i riferimenti di indirizzo adiacenti probabilmente faranno riferimento a quella stessa pagina. Se si incrementa in base all'indice di riga nel ciclo interno, è possibile che queste righe si trovino su pagine diverse (poiché sono separate da j doppie ciascuna) e che la cache potrebbe dover portare costantemente dentro e buttare via pagine di memoria come fa riferimento i dati. Questo si chiama thrashing ed è dannoso per le prestazioni.

In pratica e con cache più grandi e moderne, le dimensioni delle righe / colonne dovrebbero essere ragionevolmente grandi prima che entrino in gioco, ma è comunque una buona pratica.

[EDIT] La risposta sopra è specifica di C e potrebbe differire per altre lingue. L'unica che conosco diversa è FORTRAN. FORTRAN memorizza le cose nell'ordine principale della colonna (quanto sopra è la riga maggiore) e sarebbe corretto cambiare l'ordine delle istruzioni in FORTRAN. Se vuoi / hai bisogno di efficienza, è importante sapere come la tua lingua implementa l'archiviazione dei dati.

Answer 2

C'è un ottimo documento di Ulrich Drepper di Red Hat e la fama di glibc, Che cosa dovrebbe fare ogni programmatore Conoscere la memoria . Una sezione ha discusso delle cache in modo molto dettagliato. Ad esempio, ci sono effetti di cache nei sistemi SMP in cui le CPU possono finire per schiacciare la proprietà di una linea di cache modificata avanti e indietro, danneggiando notevolmente le prestazioni.

Answer 3

È così che causa cache come località. Lo stesso numero di memoria accessibile, ma distanziato ulteriormente, colpirà diverse "linee". di cache o potrebbe addirittura mancare del tutto la cache. È quindi bene, ogni volta che si ha la possibilità di scegliere, organizzare i dati in modo tale che gli accessi che potrebbero avvenire vicini l'uno all'altro nel tempo, lo facciano anche nello spazio. Ciò aumenta la possibilità di un colpo nella cache e ti dà maggiori prestazioni.

Naturalmente sono disponibili molte informazioni su questo argomento, vedere ad esempio questa voce di wikipedia sulla località di riferimento . O, immagino, il tuo libro di testo del corso. :)

Answer 4

In C, le matrici n-dimensionali sono la riga maggiore, il che significa che l'ultimo indice nella matrice rappresenta gli spazi adiacenti nella memoria. Questo è diverso da alcune altre lingue, ad esempio FORTRAN, che sono le colonne principali. In FORTRAN, è più efficiente iterare attraverso una matrice 2D come questa:

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

La memoria cache è una memoria molto veloce e molto costosa che si trova vicino alla CPU. Invece di recuperare ogni volta un piccolo pezzo di dati dalla RAM, la CPU recupera un blocco di dati e lo memorizza nella cache. La scommessa è che se leggi solo un byte, è probabile che il byte successivo che leggi sia subito dopo di esso. In tal caso, può provenire dalla cache.

Disegnando il tuo ciclo così come lo hai, leggi i byte nell'ordine in cui sono memorizzati. Ciò significa che sono nella cache e possono essere letti molto rapidamente dalla CPU. Se scambiassi le righe 1 e 2, allora leggeresti ogni "N" byte ogni volta intorno al ciclo. I byte che stai leggendo non sono più consecutivi in ??memoria e quindi potrebbero non essere presenti nella cache. La CPU deve recuperarli dalla RAM (più lenta) e quindi le prestazioni diminuiscono.