Cache miss rate of array

Question

J'essaie de comprendre comment calculer le taux d'échec d'un tableau. J'ai la réponse, mais je ne comprends pas comment la réponse a été trouvée. J'ai le code suivant:

int C[N1][N2]; 
int A[N1][N3]; 
int B[N3][N2]; 

initialize_arrays(A, B, C, N1, N2, N3); 

for(i=0; i<N1; ++i) 
    for(j=0; j<N2; ++j) 
     for(k=0; k<N3, ++k) 
     C[i][j] += A[i][k] * B[k][j]; 

J'ai aussi les informations suivantes: N1=N2=N3=2048 (qu'est-ce que cela veut dire ??). Le processeur a un cache de données L1 de 32 Ko avec une taille de ligne de 64 B (pas de cache L2). (quelle est la taille de la ligne?)

Je sais que le taux d'échec du tableau C est (N^2/16)/N^3. Je sais que la formule est (total misses)/(total accesses). Je vois qu'il y a N^3 accès totaux, mais comment ont-ils obtenu le nombre total d'échecs?

Je connais également le taux d'erreurs du tableau B: (N^3)/(N^3) et A: (N^2/16)/N^3. Est-ce que quelqu'un pourrait m'expliquer comment ils ont eu le total des erreurs ici aussi?

Answer 1

Le cache est toujours accédé/géré avec la granularité d'une ligne. Ici, la taille de la ligne est 64B. Cela signifie que dans une ligne de cache il y aura 16 éléments dans une ligne de cache (64B/4B = 16). La prochaine chose importante ici est que chaque 17ème élément est dans une nouvelle ligne, et qu'une fois qu'une ligne est mise en cache, elle peut donner 15 coups.

Ayant cela à l'écart, regardons le schéma d'accès. A [0] [0], B [0] [0], C [0] [0], A [0] [1], B [1] [0], C [0] [0], A [0] [2], B [2] [0], C [0] [0], ...... A [0] [16], B [16] [0], C [0] [ 0], A [0] [17], B [17] [0], C [0] [0], ...... et ainsi de suite

Maintenant, comme une ligne a 16 éléments et il est Sûr de supposer un placement de rang dans la mémoire A [0] [0] - A [0] [15] appartiendra à l'une de la première ligne de cache (appelons cela AL1) et laisser B [0] [0] - B [0] [15] appartiennent à la ligne BL1. À partir de cette information, nous pouvons écrire le modèle d'accès en termes de lignes de cache. AL1, BL1, CL1, AL1, BL129, CL1, AL1, BL257, CL1, ... AL1, BL2049, CL1, AL2, BL2176, CL1, .... et ainsi de suite.

Maintenant, la taille du cache est de 32 Ko, ce qui signifie que le cache peut contenir 512 lignes. Puisque c'est L1, supposons qu'il s'agit d'un cache associatif bidirectionnel. Par conséquent, il y a 256 ensembles. Cela signifie qu'après toutes les 256 lignes d'un tableau, la 257ème ligne correspond au même ensemble que la première ligne.

Le contenu du cache sur l'accès à la cartographie des lignes pour définir 1 ressemble à ceci

1er Iteration - intérieure

Access to - AL1 - Miss 
AL1 
Access to - BL1 - Miss 
AL1 
BL1 
Access to - CL1 - Miss 
CL1 
BL1 

2ème Iteration - intérieure

Access to - AL1 - Miss 
CL1 
AL1 
Access to - CL1 - Hit 
CL1 
AL1 

3 Iteration - intérieur

Access to - AL1 - Hit 
CL1 
AL1 
Access to - BL257 - Miss 
BL257 
AL1 
Access to - CL1 - Miss 
BL257 
CL1 

4 Iteration - intérieur

Access to - AL1 - Miss 
AL1 
CL1 
Access to - CL1 - Hit 
AL1 
CL1 

5ème Iteration - Inner

Access to - AL1 - Hit 
CL1 
AL1 
Access to - BL513 - Miss 
BL513 
AL1 
Access to - CL1 - Miss 
BL513 
CL1 

. . .

16 Iteration - intérieur

Access to - AL1 - Miss 
AL1 
CL1 
Access to - CL1 - Hit 
AL1 
CL1 

17 Iteration - intérieur

Access to - BL2049 - Miss 
BL2049 
CL1 
Access to - CL1 - Hit 
BL2049 
CL1 

18 Iteration - intérieur

Access to - CL1 - Hit 
BL2049 
CL1 

Pour la 1ère itération de la boucle du milieu. Nous avons pour l'ensemble 1,

A -> M, M, H, M, H, M, H, M, H, M, H, M, H , M, H, M, ~ , ~ , ~ , ~ , ....... 
=> after 2048 iterations - 7 hits 9 misses, 16 accesses 

B -> M, ~ , M, ~ , M, ~ , ........ 
=> after 2048 iterations - 0 Hits, 1024 misses, 1024 accesses 

C -> M, H, M, H, M, H, M, H, M, H, M, H, M, H, M, H, H , H, H , H, ...... 
=> after 2048 iterations - 2040 hits, 8 misses, 2048 accesses 

pour 2ème-16ème itération de la boucle moyenne,

Exact hit/miss/access pattern as before. 

pour 17 - itération 2048e de la boucle moyenne,

A -> same as before 
B -> No accesses 
C -> No accesses 

Pour résumer - pour 1 itération de la boucle externe, nous avons pour le jeu 1,

A -> N*9 misses , N * 16 accesses 
B -> N/2 * 16 Misses , N/2 * 16 accesses 
C -> 8 * 16 Misses , N * 16 accesses 

Dans la boucle externe, nous pouvons voir que chaque itération alternée aura le même pattern hit/miss/access que la première itération (résumé ci-dessus) pour les tableaux C et A. Chaque itération de la boucle externe aura le même hit/modèle manque d'accès/a la 1ère itération pour B. tableau

par conséquent, (enfin!)

pour Set 1, à la fin du programme, nous avons

A -> N^2 * 9/2 misses, N^2 * 8 accesses 
B -> N^2 * 8 misses, N^2 * 8 accesses 
C -> N * 64 misses, N^2 * 8 accesses 

le modèle d'accès sera être similaire sur tous les ensembles. Par conséquent, à la fin du programme, nous avons, dans tous les ensembles

A -> N^2 * 1152 misses, N^3 accesses 
B -> N^3 misses, N^3 accesses 
C -> N^2 * 8 misses, N^3 accesses 

Je sais que ceci est différent de ce qui est indiqué dans la question. Je ne pouvais pas comprendre comment. Je serai heureux d'entendre d'autres réponses.