TP 1 - Architectures multi-cœur

Retour à la page de l'UE

Pour ce TP, il est fortement recommandé d'utiliser les machines de la salle de TP. Vous pouvez utiliser votre propre machine si celle-ci a au moins quatre cœurs. Attention cependant, comme ce TP est très dépendant du hard, vous risquez de ne pas obtenir les résultats escomptés avec votre machine !

Le but du ce TP est de voir l'impact qu'ont les caches partagés sur les peformances en programmation multi-cœurs. Il sert aussi de rappel des bases de la programmation concurrente : vous devrez écrire deux programmes simples qui créent des threads en C et en Java en partant de zéro, afin de vous rafraîchir la mémoire !

On vous demande de rendre un compte-rendu du TP dans lequel vous répondrez à chaque question, de façon "intelligente". Par exemple, si on vous pose une question directe, écrivez la réponse dans le compte rendu. S'il faut coder quelque chose, expliquez ce que vous avez fait et/ou les modifications que vous avez apportées pour chaque question, et joignez les fichiers source dans l'état où ils sont à la fin de l'exercice.

Envoyez une archive contenant votre compte-rendu et vos fichiers source avant mardi prochain à 13h30, par e-mail à Jean-Pierre Lozi (vous trouverez l'adresse sur le site de l'UE).

Exercice 1 : the silent killer

On veut étudier la bonne distribution du générateur de nombre aléatoires suivant :

static unsigned long x, y=362436069, z=521288629;

unsigned long xorshf96(void) {
    unsigned long t;

    x ^= x << 16;
    x ^= x >> 5;
    x ^= x << 1;

    t = x;
    x = y;
    y = z;
    z = t ^ x ^ y;

    return z;
}

L'idée va être d'utiliser les quatre cœurs de la machine pour lancer quatre threads qui génèreront de très nombreux nombres aléatoires en utilisant ce générateur. Les threads compteront le nombres de valeurs paires et impaires générées, pour s'assurer qu'on en a à peu près autant.

Question 1.1. Ce générateur de nombres aléatoires ne va pas fonctionner correctement s'il est appelé par plusieurs threads en parallèle. On peut cependant le faire fonctionner en ajoutant un seul mot-clé. Lequel ? Indice : regardez ici.

Créez un fichier exercice1.c contenant cette fonction. Ajoutez un tableau global :

uint64_t results[4];

Ce tableau global stockera les résultats pour chaque thread. Créez une fonction main() qui crée quatre threads, attend leur terminaison, puis affiche les quatre cases du tableau results. Chacun des threads commencera par se placer sur un cœur différent (voir pthread_setaffinity_np()), puis initialisera la racine de son générateur avec un calcul faisant intervenir son identifiant et le compteur de microsecondes de son timestamp courant (voir gettimeofday()). Enfin, pour un nombre fixe d'itérations (10^8, par exemple), il appellera la fonction xorshf96() et ajoutera son résulat modulo 2 à results[thread_id].

Question 1.2. Implémentez le programme présenté ci-dessus, et assurez-vous qu'il fonctionne correctement. Utilisez time dans le terminal pour mesurer son temps d'exécution. Si tout s'est bien passé, l'exécution du programme devrait prendre autour de 4 secondes, et chaque thread devrait produire environ 10^8/2 nombres aléatoires impairs.
Question 1.3. Le programme que vous avez écrit a un important bottleneck, lequel ? Corrigez-le de manière simple. L'amélioration des performances devrait être drastique. Quelle accélération obtenez-vous par rapport à la version précédente ?
Question 1.4. Modifiez votre programme pour permettre de faire varier un paramètre qui vous permettra d'estimer la taille des lignes de cache de votre machine. Si vous utilisez une structure, faites bien attention à ce qu'elle soit packed. Créez un script qui fait varier le paramètre, et tracez les performances correspondantes. Assurez-vous que votre graphe vous permet de déduire de façon évidente la taille des lignes de cache de votre CPU. Insérez le graphe dans votre compte-rendu et expliquez le mieux possible ce que vous y voyez.

Exercice 2 : du false sharing en Java ?

S'il faut faire attention au faux partage en C, on peut se demander s'il y a des raisons de s'en inquiéter en Java. En effet, on ne manipule pas directement des adresses mémoire en Java, qui sait comment la mémoire est gérée à bas niveau ?

On veut créer un programme similaire à celui de l'exercice précédent, la différence étant qu'en plus de renvoyer un résultat, un thread stockera son progrès dans une variable globale volatile pour que le thread de la fonction main() puisse régulièrement afficher l'avancement du calcul.

Question 2.1. Pourquoi le mot-clé volatile est-il nécessaire ici ? Attention, sa signification en Java est un peu différente de celle en C.

Créez une classe Exercice2. Dans celle-ci, créez une classe interne statique ThreadInfo qui contiendra un volatile long progress qui stockera l'avancement d'un thread, et un long result qui stockera le résultat d'un thread. Créez ensuite un tableau de ThreadInfos qui sera un attribut de la classe Exercice2 :

static ThreadInfo[] infos = new ThreadInfo[4];

Le reste de l'implémentation est similaire à celle de l'exercice précédent. Implémentez la fonction xorshf96() en Java, puis créez une fonction main() qui crée quatre threads. Ces threads effectueront chacun 10^8 itérations, dans lesquelles ils appelleront xorshf96(), ajouteront le résultat modulo 2 à result, et incrémenteront progress.

Question 2.2. Une fois le programme décrit ci-dessus implémenté, lancez-le. Quel est le temps d'exécution ? Où se trouve le false sharing potentiel ?
Question 2.3. Ajoutez du padding pour éviter le false sharing potentiel. Observez-vous une amélioration des performances ? Si vous n'en observez pas, faites en sorte que les variables de padding soient utilisées artificiellement quelque part pour vous assurer que Java ne les supprime pas. Les performances sont-elles maintenant améliorées ?
Question 2.4. (optionnelle) Est-il possible de placer les threads Java sur des cœurs bien définis avec l'API standard ? Si cela n'est pas le cas, trouvez un moyen de le faire. Quel impact observez-vous sur les performances ?