Se familiariser avec les threads POSIX sur un problème simple et mesurer le gain en performance en utilisant plusieurs threads.
Les ensembles de Julia (du mathématicien français Gaston Julia, 1893-1978) sont des objets fractals du plan complexe. Dans ce contexte, le mot fractal signifie que ces objets ont une dimension fractionnaire et présentent des invariances d’échelle. Pour définir les ensembles de Julia, on considère la famille de fonctions complexes \[\begin{align} P_c:&\mathbb{C}\rightarrow\mathbb{C},\\ &z\rightarrow z^2+c, \end{align}\] où \(c\in\mathbb{C}\).
On dénote \(K_c\), l’ensemble des points \(z\in\mathbb{C}\), tels que la suites des itérés \(P^{n}_c(z)\) est bornée: \[ K_c=\{z\in\mathbb{C}\ |\ \sup\left|P_c^n(z)\right| < \infty \}, \qquad(2.1)\] où \(P^n_c(z)\) est défini par \[ P^n_c(z)=P_c(P_c(...P_c(z))). \qquad(2.2)\] L’ensemble de Julia \(J_c\) est le bord de \(K_c\). En d’autres termes, s’il existe \(M\in\mathbb{R}\) tel que \(\left|P^n_c(z)\right|\leq M\). Dans ce TP, nous considérons \(M=2\).
Les ensembles de Julia ont quelques propriétés importantes
Comme \(J_c\) est inclus dans le disque de rayon \(|c|+1\) centré en 0, on peut affirmer que \(z\notin J_c\) si et seulement si la suite des itérés \(P^n_c(z)\) sort de ce disque à une itération donnée.
Pour calculer l’ensemble de Julia, \(J_c\), associé à une valeur, \(c\in\mathbb{C}\), on peut se restreindre au domaine carré \([-2,2]\times[-2i,2i]\in\mathbb{C}\). Ce domaine est discrétisé en une grille dont la finesse du maillage déterminera la précision du calcul. La grille peut être stockée sous forme d’un tableau d’entiers. L’élément du tableau correspondant à un \(z\) donné, contient l’itération, \(k\), à partir de laquelle \(P^n_c(z)\) sort du disque de rayon 2. C’est cette valeur, \(k\), que nous souhaitons calculer et afficher dans ce travail.
Le calcul de l’ensemble \(K_c\) associé à \(c\in\mathbb{C}\), se fait sur le carré du plan complexe, dont le coin inférieur gauche est \(-2-2i\) et supérieur droit \(+2+2i\), carré qu’on discrétise en une grille. Pour chacune des valeurs complexes de la grille, appelons-les \(z_0\), on détermine si la suite des itérés \[
z_{n+1}=P_c(z_n)=z_n^2 + c,
\qquad(4.1)\] est bornée ou non. Une bonne heuristique est obtenue en effectuant un certain nombre d’itérations, nb_iter, pour voir si la suite sort du disque de rayon 2. Ceci correspond à la condition \[
|z_n|\leq 2.
\qquad(4.2)\] Évidemment, nb_iter représente une borne maximale, car on peut interrompre l’itération dès qu’on a quitté le disque de rayon 2.
Cependant, dans un premier temps, on effectuera toujours nb_iter tests tout en enregistrant la valeur à laquelle on quitte le disque de rayon 2 (c’est cette valeur qu’on affichera). La tâche à réaliser est relativement simple, car aucun calcul ne nécessite des communications. Chaque thread calcule successivement des itérés sur sa propre partie du carré1. Pour cette raison, ce genre de problèmes est appelé trivialement parallèle. On profitera donc de cette simplicité pour écrire un code bien structuré. Dans un second temps, vous devrez réfléchir à un moyen d’équilibrer la charge de chaque thread de façon statique. Dans ce cas-là, on ira donc pas jusqu’à nb_iter mais chaque boucle s’arrêtera au moment où on sort du disque de rayon 2.
Visualisez les résultats à l’aide de la librairie SDL2. Quelques fonctions ainsi qu’un exemple d’utilisation se trouvent sur cyberlearn (dans l’archive gfx_example.tar.gz2). Affichez l’itération, \(k\), à laquelle \(z_k>2\) en niveaux de gris (si vous avez du temps à perdre vous pouvez construire vos propres colormaps, chaque canal de couleur a la même intensité). Faites gérer l’affichage par un nouveau thread. Vous pouvez aller sur la page https://bit.ly/2HdQ6Jb pour trouver des exemples de valeurs de \(c\) et les résultats attendus.
Comparez les performances obtenues entre votre code tournant sur un seul thread avec un code tournant sur plusieurs threads. Faites également la comparaison entre la version avec l’équilibrage de charge et sans. Finalement, comparez la performance de votre code multi-threadé exécuté sur un seul thread avec un code purement séquentiel. Vous pouvez même si cela vous amuse tracer un graphe de la performance en fonction du nombre de threads utilisés.
Comme travail supplémentaire, affichez une animation en faisant varier \(c\) de façon continue. Une jolie animation peut être obtenue en prenant \[ c=0.7885e^{ia}, \qquad(4.3)\] où \(a\in[0,2\pi[\).
Avant d’écrire le code multi-threadé écrivez un code séquentiel. Une fois que vous avez confiance en votre code séquentiel il vous servira de référence pour déterminer si votre code concurrent fonctionne comme il faut. En effet, les deux codes doivent donner exactement les mêmes résultats.
Afin de vous assurer du bon fonctionnement de vote programme multi-threadé, il faut le lancer un grand nombre de fois et qu’à chaque fois le résultat soit le même. N’hésitez pas à écrire un petit script qui exécute votre code un grand nombre de fois, avec un nombre de threads variable et vérifiant que vos résultats sont toujours cohérents.
Je ne donnerai aucun corrigé à ces exercices. Vous pouvez si vous le souhaitez, me rendre votre code afin d’avoir un feedback. Si un·e étudiant·e (ou un groupe) souhaite soumettre sa version du code, je la relirai et la mettrai à disposition comme corrigé sur cyberlearn (avec un bonus sur une des notes du semestre).