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

Nous allons poursuivre nos exp\u00e9riences de la semaine pass\u00e9e pour tenter d’observer des effets macroscopiques dus au comportement de la m\u00e9moire cache int\u00e9gr\u00e9e dans nos processeurs. Ces exp\u00e9riences sont inspir\u00e9es par la lecture du texte d’Ulrich Drepper \u00ab\u00a0What Every Programmer Should Know About Memory<\/a>\u00a0\u00bb que je recommande vivement. Les programmes pr\u00e9sent\u00e9s ci-dessous sont accessibles dans cette archive<\/a>.<\/p>\n

\n\n<\/p>\n

Cette fois, nous allons examiner comment le cache L1 est r\u00e9parti entre les diff\u00e9rents c\u0153urs du processeur. Le CPU acc\u00e8de aux donn\u00e9es dans le cache par lignes. Ceci signifie le cache est constitu\u00e9 par des blocs de m\u00e9moire (nomm\u00e9s lignes<\/em>) dont la taille est de 64 octets sur la plupart des processeurs modernes. Une ligne est charg\u00e9e depuis la m\u00e9moire centrale (via<\/em> le cache de niveau 2) d\u00e8s que le processeur tente d’acc\u00e9der \u00e0 l’un des octets de la ligne. Le cache contient un nombre de lignes qui d\u00e9pend de la construction du processeur, une valeur de 512 lignes (32 ko) est assez fr\u00e9quente de nos jours.<\/p>\n

Suivant la conception du processeur, le cache de niveau 1 peut \u00eatre partag\u00e9 ou non entre les c\u0153urs du processeur. Lorsque le cache est partag\u00e9, l’acc\u00e8s simultan\u00e9 aux donn\u00e9es de la m\u00eame ligne est simple. M\u00eame lorsque deux c\u0153urs veulent \u00e9crire simultan\u00e9ment \u00e0 deux adresses se trouvant dans la m\u00eame ligne, la synchronisation est relativement simple.<\/p>\n

Lorsque le cache L1 n’est pas partag\u00e9 les choses sont plus compliqu\u00e9es. Tant que les deux c\u0153urs ne font que de la lecture sur les donn\u00e9es, la m\u00eame ligne peut \u00eatre charg\u00e9e dans les deux caches. Lorsqu’un des deux c\u0153urs d\u00e9sire \u00e9crire des donn\u00e9es dans cette ligne, il doit la verrouiller pour s’assurer qu’elle ne soit pas modifi\u00e9e pendant le m\u00eame temps par l’autre c\u0153ur. Ceci est r\u00e9alis\u00e9 par l’interm\u00e9diaire de messages RFO (Request For Ownership<\/em>) \u00e9mis par le c\u0153ur demandant l’acc\u00e8s exclusif. Naturellement le temps d’acc\u00e8s est plus long dans cette seconde situation.<\/p>\n

Suivant l’organisation du processeur, nous pourrons donc observer des comportements diff\u00e9rents.\u00a0Nous allons r\u00e9aliser une premi\u00e8re exp\u00e9rience consistant \u00e0 faire acc\u00e9der simultan\u00e9ment par deux threads distincts – sur deux c\u0153urs diff\u00e9rents – \u00e0 deux variables se trouvant dans la m\u00eame ligne de m\u00e9moire.<\/p>\n

Dans ce premier programme, les threads en parall\u00e8le ex\u00e9cutent chacun une boucle chronom\u00e9tr\u00e9e de 2^32 it\u00e9rations. Ils affichent en se terminant leur dur\u00e9e d’ex\u00e9cution (en micro-secondes). La synchronisation des d\u00e9marrages des threads est assur\u00e9e par une barri\u00e8re pthread_barrier_t<\/code>.<\/p>\n

acces-meme-ligne-multithreads.c\u00a0:<\/strong>\n#define _GNU_SOURCE    \/\/ necessaire pour setaffinity_np()\n\n#include <pthread.h>\n#include <stdio.h>\n#include <stdlib.h>\n#include <unistd.h>\n#include <sys\/mman.h>\n#include <sys\/time.h>\n\npthread_barrier_t barriere;\n\nvoid * fonction_thread(void * arg)\n{\n\tvolatile unsigned int * i = arg;\n\tstruct timeval tv_debut;\n\tstruct timeval tv_fin;\n\tlong long int duree;\n\n\t\/\/ synchronisation des demarrages des threads\n\tpthread_barrier_wait(& barriere);\n\n\t(* i) = 0xFFFFFFFF; \/\/ 2^32 -1\n\tgettimeofday(& tv_debut, NULL);\n\twhile ((*i) != 0)\n\t\t(*i) --;\n\tgettimeofday(& tv_fin, NULL);\n\n\tduree  = tv_fin.tv_sec - tv_debut.tv_sec;\n\tduree *= 1000000;\n\tduree += tv_fin.tv_usec - tv_debut.tv_usec;\n\tfprintf(stdout, \"Duree execution : %lldn\", duree);\n\treturn NULL;\n}\n\nint main(int argc, char * argv[])\n{\n\tpthread_attr_t attr;\n\tpthread_t thr[2];\n\tint * ptr[2];\n\tcpu_set_t cpuset;\n\tint cpu[2] = {0, 1};\n\n\tif (argc > 1) {\n\t\tif (sscanf(argv[1], \"%d\", & (cpu[0])) != 1) {\n\t\t\tfprintf(stderr, \"usage: %s [CPU] [CPU]n\", argv[0]);\n\t\t\texit(EXIT_FAILURE);\n\t\t}\n\t}\n\tif (argc > 2) {\n\t\tif (sscanf(argv[2], \"%d\", & (cpu[1])) != 1) {\n\t\t\tfprintf(stderr, \"usage: %s [CPU] [CPU]n\", argv[0]);\n\t\t\texit(EXIT_FAILURE);\n\t\t}\n\t}\n\n\tptr[0] = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);\n\tif (ptr[0] == MAP_FAILED) {\n\t\tperror(\"mmap\");\n\t\texit(EXIT_FAILURE);\n\t}\n\tptr[1] = ptr[0] + sizeof(int);\n\n\tpthread_barrier_init(& barriere, NULL, 2);\n\tpthread_attr_init(& attr);\n\n\tCPU_ZERO(& cpuset);\n\tCPU_SET(cpu[0], & cpuset);\n\tpthread_attr_setaffinity_np (& attr, sizeof(cpuset), & cpuset);\n\tpthread_create(& thr[0], & attr, fonction_thread, ptr[0]);\n\n\tCPU_ZERO(& cpuset);\n\tCPU_SET(cpu[1], & cpuset);\n\tpthread_attr_setaffinity_np (& attr, sizeof(cpuset), & cpuset);\n\tpthread_create(& thr[1], & attr, fonction_thread, ptr[1]);\n\n\tpthread_join(thr[0], NULL);\n\tpthread_join(thr[1], NULL);\n\n\treturn 0;\n}<\/pre>\n
Nous allons ex\u00e9cuter ce programme sur un processeur Intel Core 2 Quad CPU. Celui-ci poss\u00e8de donc quatre c\u0153urs, et nous allons mettre successivement en concurrence chaque c\u0153ur avec chacun des trois autres pour l’acc\u00e8s en \u00e9criture sur la m\u00eame ligne de cache, et comparer les r\u00e9sultats d’ex\u00e9cution :<\/p>\n
$ .\/acces-meme-ligne-multithreads 0 1<\/strong>\nDuree execution : 13458508\nDuree execution : 13463652\n$ .\/acces-meme-ligne-multithreads 0 2<\/strong>\nDuree execution : 16580434\nDuree execution : 16582678\n$ .\/acces-meme-ligne-multithreads 0 3<\/strong>\nDuree execution : 16507888\nDuree execution : 16508028\n$ .\/acces-meme-ligne-multithreads 1 2<\/strong>\nDuree execution : 16177846\nDuree execution : 16179444\n$ .\/acces-meme-ligne-multithreads 1 3<\/strong>\nDuree execution : 16599132\nDuree execution : 16603046\n$ .\/acces-meme-ligne-multithreads 2 3<\/strong>\nDuree execution : 13451863\nDuree execution : 13460000\n$<\/pre>\n
Nous voyons que l’acc\u00e8s simultan\u00e9 aux donn\u00e9es de la m\u00eame ligne de cache par les c\u0153urs (C0, C1) ou les c\u0153urs (C2, C3) est sensiblement plus rapide (13 secondes contre 16 secondes) que l’acc\u00e8s simultan\u00e9 par les c\u0153urs (C0, C2), \u00a0(C0, C3), \u00a0(C1, C2), ou (C1, C3).<\/p>\n
Nous pouvons en conclure que sur ce processeur, il existe deux caches L1, chacun \u00e9tant partag\u00e9 par une paire (C0, C1) ou (C2, C3).<\/p>\n
Pour compl\u00e9ter cette exp\u00e9rience, nous allons v\u00e9rifier le comportement lorsque les donn\u00e9es acc\u00e9d\u00e9es simultan\u00e9ment se trouvent dans deux lignes de caches diff\u00e9rentes, et ne pr\u00e9sentent donc pas de collisions entre les c\u0153urs. Pour cela, nous reprenons le m\u00eame principe de programme, seules les lignes d’allocation m\u00e9moire diff\u00e8rent, nous prenons nos deux pointeurs dans deux pages s\u00e9par\u00e9es, donc a fortiori<\/em> dans deux lignes de cache diff\u00e9rentes.<\/p>\n
Ainsi, au lieu de la ligne\u00a0:<\/p>\n
        ptr[1] = ptr[0] + sizeof(int);<\/pre>\n
de notre premier programme, nous utilisons l’allocation d’une nouvelle page avec :<\/p>\n
acces-differentes-lignes-multithreads.c\u00a0:<\/strong>\n[...]\n\tptr[1] = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);\n\tif (ptr[1] == MAP_FAILED) {\n\t\tperror(\"mmap\");\n\t\texit(EXIT_FAILURE);\n\t}\n[...]<\/pre>\n
L’ex\u00e9cution cette fois, ne pr\u00e9sente pas de diff\u00e9rences suivant les paires de c\u0153urs utilis\u00e9es :<\/p>\n
$ .\/acces-differentes-lignes-multithreads 0 1<\/strong>\nDuree execution : 12588085\nDuree execution : 12606074\n$ .\/acces-differentes-lignes-multithreads 0 2<\/strong>\nDuree execution : 12588740\nDuree execution : 12591586\n$ .\/acces-differentes-lignes-multithreads 0 3<\/strong>\nDuree execution : 12590018\nDuree execution : 12591842\n$ .\/acces-differentes-lignes-multithreads 1 2<\/strong>\nDuree execution : 12588323\nDuree execution : 12591253\n$ .\/acces-differentes-lignes-multithreads 1 3<\/strong>\nDuree execution : 12590367\nDuree execution : 12594167\n$ .\/acces-differentes-lignes-multithreads 2 3<\/strong>\nDuree execution : 12590264\nDuree execution : 12601760\n$<\/pre>\n
La diff\u00e9rence de temps entre l’acc\u00e8s sur des lignes diff\u00e9rentes (12,6 secondes environ dans cet exemple) contre l’acc\u00e8s sur la m\u00eame ligne dans le m\u00eame cache (13,5 secondes dans l’exp\u00e9rience pr\u00e9c\u00e9dente) est due au m\u00e9canisme de synchronisation inter-c\u0153urs pour l’acc\u00e8s sur la m\u00eame ligne.<\/p>\n
En conclusion, je soulignerai que le placement des threads sur les c\u0153urs du processeur lors de l’utilisation de donn\u00e9es aux adresses \u00ab\u00a0proches en m\u00e9moire\u00a0\u00bb (deux champs de la m\u00eame structure par exemple) n’est pas anodin au regard des performances du syst\u00e8me global. Dans le cas d’une application critique (temps-r\u00e9el strict par exemple) il est important de prendre en compte l’architecture du processeur cible (\u00e9ventuellement en v\u00e9rifiant \u00e0 l’aide du programme ci-dessus l’organisation du cache L1) \u00a0pour d\u00e9cider de l’emplacement de chaque thread.<\/p>","protected":false},"excerpt":{"rendered":"
Nous allons poursuivre nos expériences de la semaine passée pour tenter d’observer des effets macroscopiques dus au comportement de la mémoire cache intégrée dans nos processeurs. Ces expériences sont inspirées par la lecture du texte d’Ulrich Drepper « What Every Programmer Should Know About Memory » que je recommande vivement. Les programmes présentés ci-dessous sont accessibles dans […]<\/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-506","post","type-post","status-publish","format-standard","hentry","category-microprocesseur"],"_links":{"self":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/506","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=506"}],"version-history":[{"count":0,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/posts\/506\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/media?parent=506"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/categories?post=506"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.blaess.fr\/christophe\/wp-json\/wp\/v2\/tags?post=506"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}