Expériences avec le cache (2)

Publié par cpb
Avr 15 2011

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 cette archive.

Cette fois, nous allons examiner comment le cache L1 est réparti entre les différents cœurs du processeur. Le CPU accède aux données dans le cache par lignes. Ceci signifie le cache est constitué par des blocs de mémoire (nommés lignes) dont la taille est de 64 octets sur la plupart des processeurs modernes. Une ligne est chargée depuis la mémoire centrale (via le cache de niveau 2) dès que le processeur tente d’accéder à l’un des octets de la ligne. Le cache contient un nombre de lignes qui dépend de la construction du processeur, une valeur de 512 lignes (32 ko) est assez fréquente de nos jours.

Suivant la conception du processeur, le cache de niveau 1 peut être partagé ou non entre les cœurs du processeur. Lorsque le cache est partagé, l’accès simultané aux données de la même ligne est simple. Même lorsque deux cœurs veulent écrire simultanément à deux adresses se trouvant dans la même ligne, la synchronisation est relativement simple.

Lorsque le cache L1 n’est pas partagé les choses sont plus compliquées. Tant que les deux cœurs ne font que de la lecture sur les données, la même ligne peut être chargée dans les deux caches. Lorsqu’un des deux cœurs désire écrire des données dans cette ligne, il doit la verrouiller pour s’assurer qu’elle ne soit pas modifiée pendant le même temps par l’autre cœur. Ceci est réalisé par l’intermédiaire de messages RFO (Request For Ownership) émis par le cœur demandant l’accès exclusif. Naturellement le temps d’accès est plus long dans cette seconde situation.

Suivant l’organisation du processeur, nous pourrons donc observer des comportements différents. Nous allons réaliser une première expérience consistant à faire accéder simultanément par deux threads distincts – sur deux cœurs différents – à deux variables se trouvant dans la même ligne de mémoire.

Dans ce premier programme, les threads en parallèle exécutent chacun une boucle chronométrée de 2^32 itérations. Ils affichent en se terminant leur durée d’exécution (en micro-secondes). La synchronisation des démarrages des threads est assurée par une barrière pthread_barrier_t.

acces-meme-ligne-multithreads.c :
#define _GNU_SOURCE    // necessaire pour setaffinity_np()

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/time.h>

pthread_barrier_t barriere;

void * fonction_thread(void * arg)
{
	volatile unsigned int * i = arg;
	struct timeval tv_debut;
	struct timeval tv_fin;
	long long int duree;

	// synchronisation des demarrages des threads
	pthread_barrier_wait(& barriere);

	(* i) = 0xFFFFFFFF; // 2^32 -1
	gettimeofday(& tv_debut, NULL);
	while ((*i) != 0)
		(*i) --;
	gettimeofday(& tv_fin, NULL);

	duree  = tv_fin.tv_sec - tv_debut.tv_sec;
	duree *= 1000000;
	duree += tv_fin.tv_usec - tv_debut.tv_usec;
	fprintf(stdout, "Duree execution : %lldn", duree);
	return NULL;
}

int main(int argc, char * argv[])
{
	pthread_attr_t attr;
	pthread_t thr[2];
	int * ptr[2];
	cpu_set_t cpuset;
	int cpu[2] = {0, 1};

	if (argc > 1) {
		if (sscanf(argv[1], "%d", & (cpu[0])) != 1) {
			fprintf(stderr, "usage: %s [CPU] [CPU]n", argv[0]);
			exit(EXIT_FAILURE);
		}
	}
	if (argc > 2) {
		if (sscanf(argv[2], "%d", & (cpu[1])) != 1) {
			fprintf(stderr, "usage: %s [CPU] [CPU]n", argv[0]);
			exit(EXIT_FAILURE);
		}
	}

	ptr[0] = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
	if (ptr[0] == MAP_FAILED) {
		perror("mmap");
		exit(EXIT_FAILURE);
	}
	ptr[1] = ptr[0] + sizeof(int);

	pthread_barrier_init(& barriere, NULL, 2);
	pthread_attr_init(& attr);

	CPU_ZERO(& cpuset);
	CPU_SET(cpu[0], & cpuset);
	pthread_attr_setaffinity_np (& attr, sizeof(cpuset), & cpuset);
	pthread_create(& thr[0], & attr, fonction_thread, ptr[0]);

	CPU_ZERO(& cpuset);
	CPU_SET(cpu[1], & cpuset);
	pthread_attr_setaffinity_np (& attr, sizeof(cpuset), & cpuset);
	pthread_create(& thr[1], & attr, fonction_thread, ptr[1]);

	pthread_join(thr[0], NULL);
	pthread_join(thr[1], NULL);

	return 0;
}

Nous allons exécuter ce programme sur un processeur Intel Core 2 Quad CPU. Celui-ci possède donc quatre cœurs, et nous allons mettre successivement en concurrence chaque cœur avec chacun des trois autres pour l’accès en écriture sur la même ligne de cache, et comparer les résultats d’exécution :

$ ./acces-meme-ligne-multithreads 0 1
Duree execution : 13458508
Duree execution : 13463652
$ ./acces-meme-ligne-multithreads 0 2
Duree execution : 16580434
Duree execution : 16582678
$ ./acces-meme-ligne-multithreads 0 3
Duree execution : 16507888
Duree execution : 16508028
$ ./acces-meme-ligne-multithreads 1 2
Duree execution : 16177846
Duree execution : 16179444
$ ./acces-meme-ligne-multithreads 1 3
Duree execution : 16599132
Duree execution : 16603046
$ ./acces-meme-ligne-multithreads 2 3
Duree execution : 13451863
Duree execution : 13460000
$

Nous voyons que l’accès simultané aux données de la même ligne de cache par les cœurs (C0, C1) ou les cœurs (C2, C3) est sensiblement plus rapide (13 secondes contre 16 secondes) que l’accès simultané par les cœurs (C0, C2),  (C0, C3),  (C1, C2), ou (C1, C3).

Nous pouvons en conclure que sur ce processeur, il existe deux caches L1, chacun étant partagé par une paire (C0, C1) ou (C2, C3).

Pour compléter cette expérience, nous allons vérifier le comportement lorsque les données accédées simultanément se trouvent dans deux lignes de caches différentes, et ne présentent donc pas de collisions entre les cœurs. Pour cela, nous reprenons le même principe de programme, seules les lignes d’allocation mémoire diffèrent, nous prenons nos deux pointeurs dans deux pages séparées, donc a fortiori dans deux lignes de cache différentes.

Ainsi, au lieu de la ligne :

        ptr[1] = ptr[0] + sizeof(int);

de notre premier programme, nous utilisons l’allocation d’une nouvelle page avec :

acces-differentes-lignes-multithreads.c :
[...]
	ptr[1] = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, 0, 0);
	if (ptr[1] == MAP_FAILED) {
		perror("mmap");
		exit(EXIT_FAILURE);
	}
[...]

L’exécution cette fois, ne présente pas de différences suivant les paires de cœurs utilisées :

$ ./acces-differentes-lignes-multithreads 0 1
Duree execution : 12588085
Duree execution : 12606074
$ ./acces-differentes-lignes-multithreads 0 2
Duree execution : 12588740
Duree execution : 12591586
$ ./acces-differentes-lignes-multithreads 0 3
Duree execution : 12590018
Duree execution : 12591842
$ ./acces-differentes-lignes-multithreads 1 2
Duree execution : 12588323
Duree execution : 12591253
$ ./acces-differentes-lignes-multithreads 1 3
Duree execution : 12590367
Duree execution : 12594167
$ ./acces-differentes-lignes-multithreads 2 3
Duree execution : 12590264
Duree execution : 12601760
$

La différence de temps entre l’accès sur des lignes différentes (12,6 secondes environ dans cet exemple) contre l’accès sur la même ligne dans le même cache (13,5 secondes dans l’expérience précédente) est due au mécanisme de synchronisation inter-cœurs pour l’accès sur la même ligne.

En conclusion, je soulignerai que le placement des threads sur les cœurs du processeur lors de l’utilisation de données aux adresses “proches en mémoire” (deux champs de la même structure par exemple) n’est pas anodin au regard des performances du système global. Dans le cas d’une application critique (temps-réel strict par exemple) il est important de prendre en compte l’architecture du processeur cible (éventuellement en vérifiant à l’aide du programme ci-dessus l’organisation du cache L1)  pour décider de l’emplacement de chaque thread.

URL de trackback pour cette page