{"id":548,"date":"2011-04-29T15:00:05","date_gmt":"2011-04-29T14:00:05","guid":{"rendered":"http:\/\/www.blaess.fr\/christophe\/?p=548"},"modified":"2011-04-29T15:00:05","modified_gmt":"2011-04-29T14:00:05","slug":"experiences-avec-le-cache-3","status":"publish","type":"post","link":"https:\/\/www.blaess.fr\/christophe\/2011\/04\/29\/experiences-avec-le-cache-3\/","title":{"rendered":"Exp\u00e9riences avec le cache (3)"},"content":{"rendered":"

Pour continuer nos exp\u00e9riences pr\u00e9c\u00e9dentes (voir les articles 1<\/a> et 2<\/a>), je vous propose d’examiner les variations de temps d’acc\u00e8s en fonction de la saturation du TLB.<\/p>\n

\n\n<\/p>\n

Le TLB (Translation Look-Aside Buffer<\/em>) est une zone de m\u00e9moire cache utilis\u00e9e pour acc\u00e9l\u00e9rer l’acc\u00e8s \u00e0 la MMU. Rappelons que la MMU (Memory Managment Unit<\/em>) sert \u00e0 convertir les adresses des pages de m\u00e9moire virtuelle en adresses de m\u00e9moire physique. Le contenu de la MMU \u00e9tant potentiellement assez grand (plus d’un million d’entr\u00e9es sur un processeur 32 bits dont les pages m\u00e9moires mesurent 4096 octets, chaque entr\u00e9e occupant 4 octets), on l’organise g\u00e9n\u00e9ralement sous forme de tables imbriqu\u00e9es, occupant un volume m\u00e9moire plus petit. Toutefois la traduction d’une adresse de page m\u00e9moire virtuelle en page physique prend plus de temps en raison de la consultation successive de plusieurs tables. Pour acc\u00e9l\u00e9rer cette travers\u00e9e de la MMU, on utilise une m\u00e9moire cache, le TLB, qui conserve une liste des derni\u00e8res traductions r\u00e9alis\u00e9es.<\/p>\n

Lorsqu’on acc\u00e8de \u00e0 une page dont la traduction en adresse physique est pr\u00e9sente dans le TLB, le temps de travers\u00e9e de la MMU est tr\u00e8s court. Au contraire, lorsqu’un \u00e9chec du cache TLB se produit, nous verrons notre temps de traduction s’allonger. Pour mettre ceci en \u00e9vidence, nous allons r\u00e9aliser des acc\u00e8s al\u00e9atoires sur un nombre variable de pages, et nous observerons le temps moyen d’acc\u00e8s \u00e0 une page en fonction du nombre total de pages allou\u00e9es. Le programme ci-dessous est construit sur le m\u00eame principe que celui d\u00e9crit dans le premier article<\/a> de cette s\u00e9rie. On peut le t\u00e9l\u00e9charger dans cette archive<\/a>.<\/p>\n

Le programme alloue syst\u00e9matique des structures mesurant 64 octets (chacune sur une page sp\u00e9cifique obtenue avec mmap()<\/code>) afin d’occuper \u00e0 coup s\u00fbr une ligne de cache L1 compl\u00e8te et \u00e9viter que deux entr\u00e9es cons\u00e9cutives se retrouvent dans la m\u00eame ligne – ceci surtout pour le second exemple plus bas.<\/p>\n

depassement-tlb.c\u00a0:<\/strong>\n#include <stdio.h>\n#include <stdlib.h>\n#include <unistd.h>\n#include <sys\/mman.h>\n#include <sys\/time.h>\n\ntypedef struct {\n    int valeur;\n    char padding[62]; \/\/ 64 - sizeof(int)\n} entree_t;\n\nint main(int argc, char * argv[])\n{\n    register int i, n;\n\n    int nb_entrees;\n    int nb_parcours;\n\n    volatile entree_t ** entrees = NULL;\n\n    struct timeval tv_debut;\n    struct timeval tv_fin;\n    long long int duree;\n\n    if ((argc != 3)\n     || (sscanf(argv[1], \"%d\", & nb_entrees) != 1)\n     || (sscanf(argv[2], \"%d\", & nb_parcours) != 1)) {\n        fprintf(stderr,\"usage: %s nb_entrees nb_parcoursn\", argv[0]);\n        exit(EXIT_FAILURE);\n    }\n\n    \/\/ On alloue une table de N pointeurs sur les entrees\n    entrees = calloc(nb_entrees, sizeof(entree_t *));\n    if (entrees == NULL) {\n        perror(\"calloc\");\n        exit(1);\n    }\n    \/\/ Puis on alloue chaque entree sur une page specifique\n    for (i = 0; i < nb_entrees; i ++) {\n        entrees[i] = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);<\/strong>\n        if (entrees[i] == MAP_FAILED) {\n            perror(\"mmap\");\n            exit(1);\n        }\n    }\n    \/\/ La table est initialisee avec des -1\n    for (i = 0; i < nb_entrees; i ++) {\n        entrees[i]->valeur = -1;\n    }\n    n = 0;\n    i = 0;\n    \/\/ Remplir N-1 entrees (la derniere sert d'arret)\n    while (n < nb_entrees-1) {\n        \/\/ Remplir de maniere aleatoire avec le numero\n        \/\/ d'une autre entree actuellement a -1.\n        entrees[i]->valeur = rand() % nb_entrees;\n        \/\/ Si elle n'est pas vide, rechercher la premiere\n        \/\/ entree a -1\n        while (entrees[entrees[i]->valeur]->valeur != -1) {\n            entrees[i]->valeur ++;\n            if (entrees[i]->valeur == nb_entrees)\n                entrees[i]->valeur = 0;\n        }\n        i = entrees[i]->valeur;\n        n++;\n    }\n    \/\/ La derniere entree contient toujours -1\n\n    gettimeofday(& tv_debut, NULL);\n    for (n = 0; n < nb_parcours; n ++) {\n        i = 0;\n        while(i != -1) {\n            i=entrees[i]->valeur;\n        }\n    }\n    gettimeofday(& tv_fin, NULL);\n    duree  = tv_fin.tv_sec - tv_debut.tv_sec;\n    duree *= 1000000;\n    duree += tv_fin.tv_usec - tv_debut.tv_usec;\n\n    \/\/ Duree en centiemes de nanosecondes\n    duree  = duree  * 100000 \/ (nb_entrees * nb_parcours);\n\n    fprintf(stdout, \"%3lld.%02lldn\", duree\/100, duree%100);\n    return 0;\n}<\/pre>\n
Un second programme r\u00e9alise les m\u00eames op\u00e9rations, mais les entr\u00e9es sont allou\u00e9es avec malloc()<\/code> de mani\u00e8re contigu\u00ebs, sur un nombre beaucoup plus restreint de pages, \u00a0donc avec une probabilit\u00e9 de r\u00e9ussite du TLB plus \u00e9lev\u00e9e.<\/p>\n
sans-depassement-tlb.c :<\/strong>\n[...]\n    \/\/ Puis les entrees sont allouees successivement dans le tas\n    for (i = 0; i < nb_entrees; i ++) {\n        entrees[i] = malloc(sizeof(entree_t));<\/strong>\n        if (entrees[i] == NULL) {\n            perror(\"malloc\");\n            exit(1);\n        }\n    }\n[...]<\/pre>\n
Pour r\u00e9aliser des tests en s\u00e9rie, le script suivant permet de r\u00e9aliser des acc\u00e8s sur des listes de 4 \u00e0 1024 entr\u00e9es.<\/p>\n
serie.sh :<\/strong>\n[...]\nfor i in $(seq 4 1024)\ndo\n        printf \"%4d \" $i\n        .\/depassement-tlb $i $((1000000\/$i))\ndone > \"${FIC_RESULT_AVEC}\"\n\nfor i in $(seq 4 1024)\ndo\n        printf \"%4d \" $i\n        .\/sans-depassement-tlb $i $((1000000\/$i))\ndone > \"${FIC_RESULT_SANS}\"\n[...]<\/pre>\n
Un graphique est g\u00e9n\u00e9r\u00e9 automatiquement par le script \u00e0 l’aide de Gnuplot.<\/p>\n
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\u00e9rences li\u00e9es aux migrations du processus entre c\u0153urs en ex\u00e9cutant auparavant la commande<\/p>\n
# taskset -pc 1 $$<\/strong><\/pre>\n
qui bloque le shell (et les programmes qu’il lance par la suite) sur le c\u0153ur 0. En outre j’ai d\u00e9marr\u00e9 le script ci-dessus en ordonnancement temps-r\u00e9el fifo<\/em> avec une haute priorit\u00e9 ainsi :<\/p>\n
# chrt -f 90 .\/serie<\/strong>\n<\/pre>\n
\"Exp\u00e9rience<\/a><\/p>\n
Pour la courbe bleue, le TLB remplit son r\u00f4le jusqu’\u00e0 une valeur de 256 pages (la taille du TLB \u00ab\u00a0donn\u00e9es\u00a0\u00bb sur ce type de processeur). Ensuite la courbe monte rapidement jusqu’\u00e0 un second plateau durant lequel les donn\u00e9es tiennent encore dans le cache L1. Apr\u00e8s avoir d\u00e9pass\u00e9 les 512 entr\u00e9es, la courbe s’envole vers des temps d’acc\u00e8s de plus en plus longs en fonction du nombre de pages concern\u00e9es.<\/p>\n
La courbe rouge montre des temps d’acc\u00e8s beaucoup plus courts, les traductions d’adresses m\u00e9moire \u00e9tant peu nombreuses (les donn\u00e9es sont contigu\u00ebs), le TLB fonctionne de mani\u00e8re optimale. A partir de 512 entr\u00e9es de 64 octets, le cache L1 (mesurant 32 ko sur ce processeur) est d\u00e9bord\u00e9 et les performances commencent seulement \u00e0 se d\u00e9grader.<\/p>\n
Pour le programmeur cela confirme l’optimisation obtenue lorsque les donn\u00e9es sont tr\u00e8s localis\u00e9es. C’est pour cela que la fonction de biblioth\u00e8que\u00a0malloc()<\/code> r\u00e9alise une allocation par tas (les zones sont juxtapos\u00e9es)\u00a0pour allouer dynamiquement des petites zones de donn\u00e9es – quelques kilo-octets. La mise \u00e0 contribution du TLB lors de l’acc\u00e8s successif \u00e0 plusieurs de ces donn\u00e9es est alors tr\u00e8s efficace. Au contraire, les grosses zones de m\u00e9moire (plusieurs m\u00e9ga-octets) sont allou\u00e9es – avec mmap()<\/code> – dans des emplacements nettement distincts de l’espace d’adressage. Ceci leur r\u00e9serve leurs propres pages m\u00e9moires sp\u00e9cifiques, le TLB servant alors \u00e0 optimiser les acc\u00e8s successifs \u00e0 des donn\u00e9es appartenant \u00e0 la m\u00eame zone de m\u00e9moire.<\/p>","protected":false},"excerpt":{"rendered":"
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.<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"class_list":["post-548","post","type-post","status-publish","format-standard","hentry","category-microprocesseur"],"_links":{"self":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/548","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/comments?post=548"}],"version-history":[{"count":0,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/548\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/media?parent=548"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/categories?post=548"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/tags?post=548"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}