Array di ottimizzazione memoria cache Transpose: C

Question

L'array src inizia all'indirizzo 0 e l'array dst inizia all'indirizzo 0x10.

cache dati L1, mappa diretta, allocazione scrittura, dimensione blocco 8 byte.

la dimensione totale della cache è di 16 byte di dati.

Qual è l'errore su ciascuna voce di src e dst array?

La risposta è:

src: 
[0][0] -> miss, 
[0][1] -> miss, 
[1][0] -> miss, 
[1][1] -> hit 

dst: 
[0][0] -> miss, 
[0][1] -> miss, 
[1][0] -> miss, 
[1][1] -> miss 

Se la dimensione totale della cache è di 32 byte di dati, la risposta è:

src: 
[0][0] -> miss, 
[0][1] -> hit, 
[1][0] -> miss, 
[1][1] -> hit 

dst: 
[0][0] -> miss, 
[0][1] -> hit, 
[1][0] -> miss, 
[1][1] -> hit 

non sono sicuro di entrambi i risultati. Non capisco davvero il concetto con gli array e il caching.

Answer 1

Quindi, nel primo caso si hanno due righe di cache di 8 byte ciascuna per un totale di 16 byte. Assumerò una dimensione di dati int di 4 byte. Dato il posizionamento degli array in C e gli offset hai fornito queste sono le linee di memoria che possono essere memorizzati nella cache:

Cacheable lines: 
#A: &src[0][0] = 0x00, &src[0][1] = 0x04 
#B: &src[1][0] = 0x08, &src[1][1] = 0x0C 
#C: &dst[0][0] = 0x10, &dst[0][1] = 0x14 
#D: &dst[1][0] = 0x18, &dst[1][1] = 0x1C 

allora abbiamo bisogno di conoscere l'ordine di accesso che ogni indirizzo di memoria viene visitato dal programma. Sto assumendo alcuna ottimizzazione che potrebbe causare riordini da parte del compilatore.

Access order and cache behavior (assuming initially empty): 
#1: load src[0][0] --> Miss line A = cache slot 1 
#2: save dst[0][0] --> Miss line C = cache slot 2 
#3: load src[0][1] --> Hit line A = cache slot 1 
#4: save dst[0][1] --> Hit line C = cache slot 2 
#5: load src[1][0] --> Miss line B = cache slot 1 (LRU, replaces line A) 
#6: save dst[1][0] --> Miss line D = cache slot 2 (LRU, replaces line C) 
#7: load src[1][1] --> Hit line B = cache slot 1 
#8: save dst[1][1] --> Hit line D = cache slot 2 

Quale, penso, corrisponde alla seconda risposta. Poi, con una dimensione della cache di 32 byte (4 linee), assumendo tutti gli altri fattori sono costanti:

Access order and cache behavior (assuming initially empty): 
#1: load src[0][0] --> Miss line A = cache slot 1 
#2: save dst[0][0] --> Miss line C = cache slot 2 
#3: load src[0][1] --> Hit line A = cache slot 1 
#4: save dst[0][1] --> Hit line C = cache slot 2 
#5: load src[1][0] --> Miss line B = cache slot 3 
#6: save dst[1][0] --> Miss line D = cache slot 4 
#7: load src[1][1] --> Hit line B = cache slot 3 
#8: save dst[1][1] --> Hit line D = cache slot 4 

Sono identici. L'unica differenza sarebbe se riattivassi di nuovo la trasposizione. Nel caso 1 otterresti lo stesso identico comportamento (beh, avresti iniziato con la cache piena di tutte le cose sbagliate, quindi potrebbe anche essere vuoto). Nel caso di cache più grande, tuttavia, tutto ciò che è necessario per la seconda chiamata è già memorizzato nella cache, quindi non ci saranno errori di cache.

La differenza tra le mie risposte e le tue è molto probabilmente dovuta alle nostre ipotesi sul comportamento del compilatore per i tuoi registri di conteggio del ciclo (i e j). Suppongo che siano entrambi memorizzati nei registri (e quindi non influenzerebbe la cache dei dati). Potrebbe essere necessario assumere che siano in memoria da qualche parte (e quindi interagire con la cache) per ottenere i risultati attesi.