Français
Menu

Hiérarchie mémoire

Parcourir le tableau à deux dimensions a[i][j] du langage C avec j dans la boucle interne, comme ci-dessus, est généralement plus rapide qu’avec i dans la boucle interne. Pour quelle raison ?

for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
        sum += a[i][j];
  1. ALe stockage étant en ordre ligne par ligne, des adresses contiguës sont lues successivement et les lignes de cache sont exploitées efficacement
  2. BLe compilateur supprime en bloc les additions de la boucle et omet le calcul lui-même à l’exécution
  3. CAvec j dans la boucle interne, le TLB n’est plus du tout consulté et la traduction d’adresse virtuelle en adresse physique devient inutile
Afficher la réponse et l'explication

Réponse : A. Le stockage étant en ordre ligne par ligne, des adresses contiguës sont lues successivement et les lignes de cache sont exploitées efficacement

Un tableau à deux dimensions en C est stocké ligne par ligne (row-major) : a[i][0], a[i][1]… sont adjacents en mémoire. Avec j dans la boucle interne, les adresses contiguës sont lues dans l’ordre, si bien que le reste de la ligne de cache de 64 octets chargée lors d’un défaut est utilisé immédiatement. Avec i dans la boucle interne, la lecture saute d’une ligne entière à chaque accès, et la ligne de cache tend à être évincée alors qu’une infime partie seulement a été utilisée. Le TLB reste sollicité ; la traduction d’adresse n’est pas supprimée.

S'entraîner sur ce thème Retour au thème

Autres questions sur Hiérarchie mémoire

  1. Pour un cache à correspondance directe avec des adresses de 32 bits, une capacité de 32 KB et des lignes de 64 octets, combien de bits comporte l’étiquette ?
  2. Combien d’ensembles comporte un cache associatif à 4 voies avec des adresses de 32 bits, une capacité de 32 KB et des lignes de 64 octets ?
  3. Dans un cache totalement associatif, combien de bits de l’adresse sont utilisés pour l’index (partie qui sélectionne l’ensemble) ?
  4. Avec un temps de succès L1 de 1 ns, un taux de défauts L1 de 5%, un temps de succès L2 de 10 ns, un taux de défauts local L2 de 20% et un temps d’accès à la mémoire principale de 100 ns, quel est le temps moyen d’accès mémoire ?
  5. Dans un cache à correspondance directe, les éléments de deux tableaux correspondent au même emplacement du cache et s’évincent mutuellement à chaque accès alterné. Dans quelle catégorie se classe ce défaut ?

Comparatifs sur ce thème