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_parcours\n", 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.%02lld\n", duree/100, duree%100);
return 0;
}
Un second programme réalise les mêmes opérations, mais les entrées sont allouées avec malloc() de manière contiguës, sur un nombre beaucoup plus restreint de pages, donc avec une probabilité de réussite du TLB plus élevée.
sans-depassement-tlb.c :
[...]
// Puis les entrees sont allouees successivement dans le tas
for (i = 0; i < nb_entrees; i ++) {
entrees[i] = malloc(sizeof(entree_t));
if (entrees[i] == NULL) {
perror("malloc");
exit(1);
}
}
[...]
Pour réaliser des tests en série, le script suivant permet de réaliser des accès sur des listes de 4 à 1024 entrées.
serie.sh :
[...]
for i in $(seq 4 1024)
do
printf "%4d " $i
./depassement-tlb $i $((1000000/$i))
done > "${FIC_RESULT_AVEC}"
for i in $(seq 4 1024)
do
printf "%4d " $i
./sans-depassement-tlb $i $((1000000/$i))
done > "${FIC_RESULT_SANS}"
[...]
Un graphique est généré automatiquement par le script à l’aide de Gnuplot.
Voici un exemple, obtenu sur un Intel Core 2 Quad Q6600, sous Linux 2.6.39-rc3 (noyau de test de la prochaine version stable) sur une distribution Fedora 14. Pour avoir un comportement assez reproductible, je me suis affranchi des interférences liées aux migrations du processus entre cœurs en exécutant auparavant la commande
# taskset -pc 1 $$
qui bloque le shell (et les programmes qu’il lance par la suite) sur le cœur 0. En outre j’ai démarré le script ci-dessus en ordonnancement temps-réel fifo avec une haute priorité ainsi :
# chrt -f 90 ./serie
Pour la courbe bleue, le TLB remplit son rôle jusqu’à une valeur de 256 pages (la taille du TLB « données » sur ce type de processeur). Ensuite la courbe monte rapidement jusqu’à un second plateau durant lequel les données tiennent encore dans le cache L1. Après avoir dépassé les 512 entrées, la courbe s’envole vers des temps d’accès de plus en plus longs en fonction du nombre de pages concernées.
La courbe rouge montre des temps d’accès beaucoup plus courts, les traductions d’adresses mémoire étant peu nombreuses (les données sont contiguës), le TLB fonctionne de manière optimale. A partir de 512 entrées de 64 octets, le cache L1 (mesurant 32 ko sur ce processeur) est débordé et les performances commencent seulement à se dégrader.
Pour le programmeur cela confirme l’optimisation obtenue lorsque les données sont très localisées. C’est pour cela que la fonction de bibliothèque malloc() réalise une allocation par tas (les zones sont juxtaposées) pour allouer dynamiquement des petites zones de données – quelques kilo-octets. La mise à contribution du TLB lors de l’accès successif à plusieurs de ces données est alors très efficace. Au contraire, les grosses zones de mémoire (plusieurs méga-octets) sont allouées – avec mmap() – dans des emplacements nettement distincts de l’espace d’adressage. Ceci leur réserve leurs propres pages mémoires spécifiques, le TLB servant alors à optimiser les accès successifs à des données appartenant à la même zone de mémoire.
