Cache-Speicheroptimierung Array-Transponierung: C

Question

typedef int array[2][2]; 

void transpose(array dst, array src) { 
    int i, j; 
    for (j = 0; j < 2; j++) { 
     for (i = 0; i < 2; i++) { 
      dst[i][j] = src[j][i]; 
     } 
    } 
} 

Das src-Array beginnt an der Adresse 0 und das dst-Array beginnt an der Adresse 0x10.

L1 Datencache, direkte Zuordnung, Schreibzuweisung, 8 Byte Blockgröße.

Cache-Gesamtgröße ist 16 Datenbytes.

Was ist der Treffer oder Fehlschlag bei jedem Eintrag von src und dst array?

Die Antwort lautet:

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 

Wenn die Cache Gesamtgröße 32 Daten-Bytes ist, lautet die Antwort:

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 

Ich bin nicht sicher, beiden Ergebnisse. Ich verstehe das Konzept mit Arrays und Caching nicht wirklich.

Answer 1

Also, in erster Instanz haben Sie zwei Cache-Zeilen von jeweils 8 Bytes für insgesamt 16 Bytes. Ich nehme eine int-Datengröße von 4 Bytes an. Aufgrund der Platzierung von Arrays in C und die Versätze Sie diese zur Verfügung gestellt haben, sind die Speicherleitungen, die im Cache gespeichert werden können:

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 

Dann brauchen wir den Zugang, um zu wissen, dass jede Speicheradresse durch das Programm besucht wird. Ich nehme keine Optimierungen an, die Neuordnungen durch den Compiler verursachen könnten.

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 

Welche, denke ich, entspricht Ihrer zweiten Antwort. Dann mit einer Cache-Größe von 32 Bytes (4 Zeilen), unter der Annahme, dass alle anderen Faktoren konstant sind:

Sie sind identisch. Der einzige Unterschied wäre, wenn Sie erneut transponieren. In Fall 1 würden Sie genau das gleiche Verhalten bekommen (nun, Sie fangen mit dem Cache an, der voll mit den falschen Dingen ist, also könnte es auch leer sein). Im Fall des größeren Caches ist jedoch alles, was Sie für den zweiten Aufruf benötigen, bereits zwischengespeichert, so dass es keine Cache-Fehler geben wird.

Der Unterschied zwischen meinen und Ihren Antworten liegt höchstwahrscheinlich in unseren Annahmen über das Verhalten des Compilers für Ihre Schleifenzählregister (i und j). Ich würde annehmen, dass sie beide in Registern gespeichert sind (und so den Datencache nicht beeinflussen würden). Möglicherweise müssen Sie davon ausgehen, dass sie sich irgendwo im Speicher befinden (und daher mit dem Cache interagieren), um die erwarteten Ergebnisse zu erhalten.