Expériences avec le cache (3)

Publié par cpb
Avr 29 2011

Pour continuer nos expériences précédentes (voir les articles 1 et 2), je vous propose d’examiner les variations de temps d’accès en fonction de la saturation du TLB.

Le TLB (Translation Look-Aside Buffer) est une zone de mémoire cache utilisée pour accélérer l’accès à la MMU. Rappelons que la MMU (Memory Managment Unit) sert à convertir les adresses des pages de mémoire virtuelle en adresses de mémoire physique. Le contenu de la MMU étant potentiellement assez grand (plus d’un million d’entrées sur un processeur 32 bits dont les pages mémoires mesurent 4096 octets, chaque entrée occupant 4 octets), on l’organise généralement sous forme de tables imbriquées, occupant un volume mémoire plus petit. Toutefois la traduction d’une adresse de page mémoire virtuelle en page physique prend plus de temps en raison de la consultation successive de plusieurs tables. Pour accélérer cette traversée de la MMU, on utilise une mémoire cache, le TLB, qui conserve une liste des dernières traductions réalisées.

Lorsqu’on accède à une page dont la traduction en adresse physique est présente dans le TLB, le temps de traversée de la MMU est très court. Au contraire, lorsqu’un échec du cache TLB se produit, nous verrons notre temps de traduction s’allonger. Pour mettre ceci en évidence, nous allons réaliser des accès aléatoires sur un nombre variable de pages, et nous observerons le temps moyen d’accès à une page en fonction du nombre total de pages allouées. Le programme ci-dessous est construit sur le même principe que celui décrit dans le premier article de cette série. On peut le télécharger dans cette archive.

Le programme alloue systématique des structures mesurant 64 octets (chacune sur une page spécifique obtenue avec mmap()) afin d’occuper à coup sûr une ligne de cache L1 complète et éviter que deux entrées consécutives se retrouvent dans la même ligne – ceci surtout pour le second exemple plus bas.

depassement-tlb.c :
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/time.h>

typedef struct {
    int valeur;
    char padding[62]; // 64 - sizeof(int)
} entree_t;

int main(int argc, char * argv[])
{
    register int i, n;

    int nb_entrees;
    int nb_parcours;

    volatile entree_t ** entrees = NULL;

    struct timeval tv_debut;
    struct timeval tv_fin;
    long long int duree;

    if ((argc != 3)
     || (sscanf(argv[1], "%d", & nb_entrees) != 1)
     || (sscanf(argv[2], "%d", & nb_parcours) != 1)) {
        fprintf(stderr,"usage: %s nb_entrees nb_parcoursn", argv[0]);
        exit(EXIT_FAILURE);
    }

    // On alloue une table de N pointeurs sur les entrees
    entrees = calloc(nb_entrees, sizeof(entree_t *));
    if (entrees == NULL) {
        perror("calloc");
        exit(1);
    }
    // Puis on alloue chaque entree sur une page specifique
    for (i = 0; i < nb_entrees; i ++) {
        entrees[i] = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
        if (entrees[i] == MAP_FAILED) {
            perror("mmap");
            exit(1);
        }
    }
    // La table est initialisee avec des -1
    for (i = 0; i < nb_entrees; i ++) {
        entrees[i]->valeur = -1;
    }
    n = 0;
    i = 0;
    // Remplir N-1 entrees (la derniere sert d'arret)
    while (n < nb_entrees-1) {
        // Remplir de maniere aleatoire avec le numero
        // d'une autre entree actuellement a -1.
        entrees[i]->valeur = rand() % nb_entrees;
        // Si elle n'est pas vide, rechercher la premiere
        // entree a -1
        while (entrees[entrees[i]->valeur]->valeur != -1) {
            entrees[i]->valeur ++;
            if (entrees[i]->valeur == nb_entrees)
                entrees[i]->valeur = 0;
        }
        i = entrees[i]->valeur;
        n++;
    }
    // La derniere entree contient toujours -1

    gettimeofday(& tv_debut, NULL);
    for (n = 0; n < nb_parcours; n ++) {
        i = 0;
        while(i != -1) {
            i=entrees[i]->valeur;
        }
    }
    gettimeofday(& tv_fin, NULL);
    duree  = tv_fin.tv_sec - tv_debut.tv_sec;
    duree *= 1000000;
    duree += tv_fin.tv_usec - tv_debut.tv_usec;

    // Duree en centiemes de nanosecondes
    duree  = duree  * 100000 / (nb_entrees * nb_parcours);

    fprintf(stdout, "%3lld.%02lldn", duree/100, duree%100);
    return 0;