C - linee di cache e di associazione

Question

Contesto

Leggi articoli sulla ottimizzazioni di cache (associazione con una linea di cache in loop ..)

La domanda è legata a questo contesto: matrice di 1024 numeri interi.

Dimensioni: cpu cache 64k, riga cache 32 byte, dimensioni integer: 4 byte.

intel core 2 duo

Domanda

Secondo la mia cpu, 8 interi stare in una linea di cache.

[0,1,2,3,4,5,6,7,8,9,10,...,1023] 
     ^
If I want to access 4 and go downward, 3,2,1 and 0 will be loaded already. 5,6,7 are loaded uselessly. 

[0,1,2,3,4,5,6,7,8,..,1023] 
      ^
If I want to access 7 and go downward, all the next elements will be in cache already. if I want to go upward, according to my cpu I will have to load another cache line immediatly after the arr[7] read. 

Sono corretto?

Proseguendo

Ma quello che mi dice che arr [4] Non è a un indirizzo che causerà un carico lineare cache invece di arr [7]? Se la mia affermazione è vera, non dovremmo considerare solo l'allineamento in-array, ma l'intero allineamento della memoria del programma per minimizzare lo spreco di cache, giusto?

Answer 1

Per quanto riguarda la tua domanda principale, sì, hai ragione in entrambi i casi.

Nel secondo caso, in cui arr[7] viene caricato e potrebbe desiderare di continuare verso l'alto, si dovrebbe ricordare che probabilmente sia il compilatore o qualche meccanismo di prefetching tiene conto del spatial locality di questo tipo di dati, migliorando così le prestazioni.

Inoltre, la lettura di qualche altro indirizzo nell'array potrebbe causare un carico della linea cache anziché arr[7] se l'array non è allineato correttamente in memoria, ma in questo caso l'allineamento non dipende da te, ma fino a compilatore.

Answer 2

Ma cosa mi dice che arr [4] non è a un indirizzo che causerà un carico di linea della cache invece di arr [7]?

Gli array int sono di solito allineati sui bordi di 4 byte (supponendo che int sia 32 bit e byte 8 bit), quindi non si sa dove sarà il bordo della linea cache.

La lezione da apprendere è che non ci si deve preoccupare della perdita della linea memorizzata nella cache (cioè utilizzando 2 linee di cache anche se i dati necessari sono inferiori a 32 byte), perché questo è per lo più fuori dalle tue mani durante la codifica in C.

Ciò di cui si potrebbe preoccupare, se si verificano problemi di prestazioni, è la scelta di algoritmi che riducano i problemi di cache.

L'esempio tipico è loop:

int array[N][M]; // Assume N * M * sizeof (int) is much larger than the cache. 

// Example 1 
for (i=0; i<N; i++) { 
    for (j=0; j<M; j++) { 
    <do something with array[i][j]> 
    } 
} 

// Example 2 
int array[N][M]; 
for (j=0; j<M; j++) { 
    for (i=0; i<N; i++) { 
    <do something with array[i][j]> 
    } 
} 

Uno degli esempi darà circa 8 volte più cache miss come l'altro perché accede agli elementi nell'ordine sbagliato.