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

En parcourant l’excellent texte d’Ulrich Drepper \u00ab\u00a0What Every Programmer Should Know About Memory<\/a>\u00a0\u00bb j’ai eu envie de v\u00e9rifier si j’obtenais exp\u00e9rimentalement des r\u00e9sultats similaires \u00e0 ceux qu’il pr\u00e9sente. J’ai construit une s\u00e9rie de petits programmes, qui acc\u00e8dent de diff\u00e9rentes mani\u00e8res \u00e0 la m\u00e9moire et nous pr\u00e9sentent des statistiques sur leurs temps d’ex\u00e9cution. Ils sont disponibles dans cette archive<\/a>.<\/p>\n

\n\n<\/p>\n

Le premier programme qui cr\u00e9\u00e9 une table d’entiers dont la taille N est indiqu\u00e9e en premier argument sur la ligne de commandes. La table est remplie de mani\u00e8re s\u00e9quentielle, chaque case contient le num\u00e9ro d’indice de la case suivante.<\/p>\n

Nous chronom\u00e9trons ensuite une s\u00e9rie de P parcours de cette table (P \u00e9tant fourni en second argument sur la ligne de commande) durant lesquels nous consultons simplement le contenu de chaque case.\u00a0Puis une seconde s\u00e9rie de P parcours chronom\u00e9tr\u00e9s durant lesquels on va modifier la table (un parcours avec incr\u00e9mentation du contenu de chaque case, suivi d’un parcours avec d\u00e9cr\u00e9mentation des contenus).<\/p>\n

acces-sequentiels-memoire.c :<\/strong>\n#include <stdio.h>\n#include <stdlib.h>\n#include <unistd.h>\n#include <sys\/time.h>\n\nint main(int argc, char * argv[])\n{\n\tregister int i, n;\n\n\tint nb_entrees;\n\tint nb_parcours;\n\tint * bloc;\n\tstruct timeval tv_debut;\n\tstruct timeval tv_fin;\n\tlong long int duree_lectures;\n\tlong long int duree_ecritures;\n\n\tif ((argc != 3)\n\t || (sscanf(argv[1], \"%d\", & nb_entrees) != 1)\n\t || (sscanf(argv[2], \"%d\", & nb_parcours) != 1)) {\n\t\tfprintf(stderr,\"usage: %s nb_entrees nb_parcoursn\", argv[0]);\n\t\texit(EXIT_FAILURE);\n\t}\n\n\tfprintf(stderr, \"Preparation de la table des donnees...n\");\n\tbloc = calloc(nb_entrees, sizeof(int));\n\n\t\/\/ Chaque entree contient le numero de la case suivante\n\tfor (i = 0; i < nb_entrees-1; i ++)\n\t\tbloc[i] = i+1;\n\t\/\/ La derniere entree est indiquee par -1\n\tbloc[i] = -1;\n\n\tfprintf(stderr, \"Table prete...n\");\n\n\tfprintf(stderr, \"Parcours en lecture...n\");\n\tgettimeofday(& tv_debut, NULL);\n\tfor (n = 0; n < nb_parcours; n ++) {\n\t\ti = 0;\n\t\twhile(i != -1) {\n\t\t\ti=bloc[i];\n\t\t}\n\t}\n\tgettimeofday(& tv_fin, NULL);\n\tduree_lectures  = tv_fin.tv_sec - tv_debut.tv_sec;\n\tduree_lectures *= 1000000;\n\tduree_lectures += tv_fin.tv_usec - tv_debut.tv_usec;\n\n\tfprintf(stderr, \"Parcours en ecriture...n\");\n\tgettimeofday(& tv_debut, NULL);\n\tfor (n = 0; n < nb_parcours; n ++) {\n\t\ti = 0;\n\t\t\/\/ On decremente chaque entree sauf la derniere\n\t\twhile(i != -1) {\n\t\t\ti=(bloc[i]--);\n\t\t}\n\t\ti = 0;\n\t\t\/\/ On incremente chaque entree sauf la derniere\n\t\twhile(i != -1)\n\t\t\ti=(++bloc[i]);\n\t}\n\tgettimeofday(& tv_fin, NULL);\n\tduree_ecritures  = tv_fin.tv_sec - tv_debut.tv_sec;\n\tduree_ecritures*= 1000000;\n\tduree_ecritures += tv_fin.tv_usec - tv_debut.tv_usec;\n\tduree_ecritures \/= 2; \/\/ Deux parcours complets\n\n\tfprintf(stderr, \"Parcours termines...n\");\n\n\t\/\/ Durees en centiemes de nanosecondes\n\tduree_lectures  = duree_lectures  * 100000 \/ (nb_entrees * nb_parcours);\n\tduree_ecritures = duree_ecritures * 100000 \/ (nb_entrees * nb_parcours);\n\n\tfprintf(stdout, \"Duree par acces lecture  : %lld.%lld nsn\", duree_lectures\/100, duree_lectures%100);\n\tfprintf(stdout, \"Duree par acces ecriture : %lld.%lld nsn\", duree_ecritures\/100, duree_ecritures%100);\n\treturn 0;\n}<\/pre>\n
Nous allons tester ce programme avec diff\u00e9rentes valeurs de N et P. Pour \u00e9quilibrer grosso-modo le temps de fonctionnement de l’application, nous allons multiplier N (le nombre de valeurs dans la table) par deux \u00e0 chaque nouvelle ex\u00e9cution, tandis que nous diviserons P (le nombre parcours) par deux. Pour cela, le petit script suivant nous sera utile :<\/p>\n
serie-acces-sequentiels.sh :<\/strong>\n#! \/bin\/sh\n\nFIC_RESULTATS=\"resultats\/sequentiels.txt\"\nFIC_DATA_READ=\"resultats\/read-sequentiels.txt\"\nFIC_DATA_WRITE=\"resultats\/write-sequentiels.txt\"\nFIC_GRAPHIQUE=\"resultats\/graph-sequentiel.gif\"\n\n> \"$FIC_RESULTATS\"\n\nN=1<\/strong>\nP=$((512*1024*1024))<\/strong>\n\ntaskset -pc 0 $$\n\nwhile [ \"$P\" -ge 1 ]\ndo\n        echo \"$N \/ $P \" >&2\n        echo \"taille bloc : $N, nb_cycles : $P\" >> \"$FIC_RESULTATS\"\n        .\/acces-sequentiels-memoire \"$N\" \"$P\" >> \"$FIC_RESULTATS\"\n        N=$((N<<1))\n        P=$((P>>1))\ndone\ngrep ecriture < \"$FIC_RESULTATS\" | awk '{print $6}' > \"$FIC_DATA_WRITE\"\ngrep lecture  < \"$FIC_RESULTATS\" | awk '{print $6}' > \"$FIC_DATA_READ\"\n\necho \"set terminal gif giant size 1600,1200; set output '$FIC_GRAPHIQUE'; set multiplot layout 2,1; \" \n     \"set xlabel 'log2(nombre de blocs)'; set ylabel 'duree boucle (ns)'; \"\n     \"plot   '$FIC_DATA_WRITE' with line lc rgb '#FF0000'; \" \n     \"replot '$FIC_DATA_READ'  with line lc rgb '#0000FF';\" \n | gnuplot<\/pre>\n
Pour \u00e9viter toute migration intempestive du processus, on le fixe (avec taskset<\/code>) sur le processeur 0<\/code>.<\/p>\n
On remarquera l’initialisation des variables N et P : nous allons commencer par un bloc de 1 entier, acc\u00e9d\u00e9 512 millions de fois, pour terminer par un bloc de 512 millions d’entr\u00e9es enti\u00e8res (occupant donc 2Go) acc\u00e9d\u00e9 une seule fois. On peut naturellement jouer sur ces valeurs en fonction de la taille m\u00e9moire et de la vitesse de traitement du syst\u00e8me. On notera \u00e9galement que les derni\u00e8res lignes du script invoquent l’utilitaire gnuplot<\/code> pour cr\u00e9er un fichier graphique avec les r\u00e9sultats.<\/p>\n
Voici une premi\u00e8re ex\u00e9cution :<\/p>\n
$ .\/series-acces-sequentiels.sh <\/strong>\npid 6971's current affinity list: 0-3\npid 6971's new affinity list: 0\n1 \/ 536870912\nPreparation de la table des donnees...\nTable prete...\nParcours en lecture...\nParcours en ecriture...\nParcours termines...\n2 \/ 268435456\n[...]\n536870912 \/ 1\nPreparation de la table des donnees...\nTable prete...\nParcours en lecture...\nParcours en ecriture...\nParcours termines...\n$<\/pre>\n
Et le r\u00e9sultat se pr\u00e9sente sur les figures suivantes :<\/p>\n
 <\/p>\n
\"Acc\u00e8s<\/a>
Acc\u00e8s s\u00e9quentiels sur une zone m\u00e9moire<\/p><\/div>\n
Pour pouvoir comprendre l’int\u00e9r\u00eat de ce graphique, il nous faut le comparer \u00e0 un autre type d’acc\u00e8s m\u00e9moire : l’acc\u00e8s al\u00e9atoire. Nous reprenons notre programme pr\u00e9c\u00e9dent en modifiant simplement l’initialisation du bloc : chaque case va contenir le num\u00e9ro d’indice d’une autre case du tableau choisie al\u00e9atoirement. Pour s’assurer que nous ayons un parcours complet du tableau en N \u00e9tapes, lorsque nous d\u00e9terminons le num\u00e9ro d’indice de la case vis\u00e9e, nous nous assurons que cette derni\u00e8re soit vide (sinon on prend la suivante dans le tableau et on recommence la v\u00e9rification).<\/p>\n
acces-aleatoires-memoire.c :<\/strong>\n[...]\n\t\/\/ On alloue une table de N entrees, initialisees a -1\n\tbloc = calloc(nb_entrees, sizeof(int));\n\tfor (i = 0; i < nb_entrees; i ++)\n\t\tbloc[i] = -1;\n\tn = 0;\n\ti = 0;\n\t\/\/ Remplir N-1 entrees (la derniere sert d'arret)\n\twhile (n < nb_entrees-1) {\n\t\t\/\/ Remplir de maniere aleatoire avec le numero\n\t\t\/\/ d'une autre entree actuellement vide.\n\t\tbloc[i] = rand() % nb_entrees;\n\t\t\/\/ Si elle n'est pas vide, rechercher la premiere\n\t\t\/\/ entree vide a la suite.\n\t\twhile (bloc[bloc[i]] != -1) {\n\t\t\tbloc[i] ++;\n\t\t\tif (bloc[i] == nb_entrees)\n\t\t\t\tbloc[i] = 0;\n\t\t}\n\t\ti = bloc[i];\n\t\tn++;\n\t}\n\t\/\/ La derniere entree contient toujours -1\n[...]<\/pre>\n
Bien s\u00fbr, un script nomm\u00e9 series-acces-aleatoires.sh<\/code> permet d’ex\u00e9cuter ce programme avec les m\u00eames arguments que pr\u00e9c\u00e9demment. Le temps d’ex\u00e9cution du script est nettement plus long, ne serait-ce qu’\u00e0 cause de l’initialisation des tables qui demandent des calculs importants pour l’obtention des valeurs al\u00e9atoires.<\/p>\n
$ .\/series-acces-aleatoires.sh <\/strong>\npid 8003's current affinity list: 0-3\npid 8003's new affinity list: 0\n1 \/ 536870912\nPreparation de la table des donnees...\nTable prete...\nParcours en lecture...\nParcours en ecriture...\nParcours termines...\n2 \/ 268435456\n[...]\n\n$<\/pre>\n
Voici le graphique correspondant \u00e0 cette ex\u00e9cution.<\/p>\n
 <\/p>\n
\"Acc\u00e8s<\/a>
Acc\u00e8s al\u00e9atoires sur une zone m\u00e9moire<\/p><\/div>\n
Nous pouvons remarquer que le temps d’acc\u00e8s, en op\u00e9rant de mani\u00e8re al\u00e9atoire sur les donn\u00e9es, est sensiblement plus long d\u00e8s que l’on d\u00e9passe une table de 2^13 entiers. Cette valeur correspond \u00e0 8192 entiers, soient 32Ko ce qui repr\u00e9sente la taille du cache de premier niveau (L1d). Tant que les donn\u00e9es manipul\u00e9es arrivent \u00e0 tenir dans ce cache, le mode de parcours importe peu, nous avons un comportement optimal pour l’acc\u00e8s aux donn\u00e9es m\u00e9moire.<\/p>\n
Une fois que l’on d\u00e9passe le cache L1, les parcours al\u00e9atoires n\u00e9cessitent de charger fr\u00e9quemment des lignes de m\u00e9moire depuis le cache L2, avec un temps d’acc\u00e8s un peu plus long. Les parcours s\u00e9quentiels ne pr\u00e9sentent pas beaucoup de diff\u00e9rences d’ex\u00e9cution car le processeur utilise une \u00ab\u00a0fen\u00eatre\u00a0\u00bb m\u00e9moire de la taille de L1 qu’il d\u00e9place sur l’ensemble des donn\u00e9es.<\/p>\n
Ensuite, nous remarquons \u00e0 nouveau une envol\u00e9e des temps d’acc\u00e8s al\u00e9atoire \u00e0 partir de 2^19 entiers, soient 2 Mo de donn\u00e9es. Cette fois c’est le cache de second niveau qui est d\u00e9bord\u00e9. Celui-ci contient environ 4Mo de donn\u00e9es, mais il est partag\u00e9 entre les diff\u00e9rents c\u0153urs du processeur et d\u00e8s que le jeu de donn\u00e9es manipul\u00e9 d\u00e9passe 2Mo environ, le processeur doit aller chercher ses informations dans la m\u00e9moire dynamique du syst\u00e8me, dont l’acc\u00e8s est beaucoup plus long que celui de la m\u00e9moire statique du cache.<\/p>\n
Ces exp\u00e9riences nous montrent bien que l’utilisation d’ensembles de travail de tailles inf\u00e9rieures \u00e0 32 Ko est optimale, qu’une premi\u00e8re d\u00e9gradation intervient lorsqu’on d\u00e9passe cette limite sauf si les acc\u00e8s m\u00e9moire se font de mani\u00e8re tr\u00e8s localis\u00e9e (comparable \u00e0 nos parcours s\u00e9quentiels). Au-del\u00e0 de 4Mo de donn\u00e9es, les performances s’effondreront si nous ne sommes pas capables – en organisant et en structurant correctement nos variables – de garantir des acc\u00e8s les plus localis\u00e9s aux donn\u00e9es. Bien s\u00fbr ces valeurs d\u00e9pendent du processeur et de son niveau de cache. Rappelons que le nom et le type de processeur sont visibles avec une commande :<\/p>\n
$ cat \/proc\/cpuinfo<\/strong><\/pre>\n
Les informations techniques sur le cache d’un processeur donn\u00e9 se trouvent assez facilement sur le site de son fabricant ou sur Wikipedia.<\/p>\n
 <\/p>","protected":false},"excerpt":{"rendered":"
En parcourant l’excellent texte d’Ulrich Drepper « What Every Programmer Should Know About Memory » j’ai eu envie de vérifier si j’obtenais expérimentalement des résultats similaires à ceux qu’il présente. J’ai construit une série de petits programmes, qui accèdent de différentes manières à la mémoire et nous présentent des statistiques sur leurs temps d’exécution. Ils sont disponibles […]<\/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-468","post","type-post","status-publish","format-standard","hentry","category-microprocesseur"],"_links":{"self":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/468","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=468"}],"version-history":[{"count":0,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/468\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/media?parent=468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/categories?post=468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/tags?post=468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}