L’ensemble de Mandelbrot avec du calcul parallèle en CUDA

Après deux mois d’attente, le cours d’Udacity sur la calcul parallèle en CUDA a enfin commencé. Comme pour leurs autres cours, c’est très soigné et on a envie de continuer à la fin de la séquence, mais il faut patienter une semaine de plus. Petit défaut quand même, leur valeur ajoutée Nvidia n’est pas particulièrement forte, la première semaine se termine avec une interview, certes intéressante, mais cela reste un discours de chercheur. On ne voit pas Nvidia de l’intérieur, des cartes graphiques en morceaux, des lignes d’assemblage, des outils de test qui font rêver. Il leur reste encore plusieurs semaines de cours pour faire rêver, je vais leur laisser le bénéfice du doute.

L’autre défaut, qui me mène à cet article, c’est le manque de pratique : un pauvre petit problème par semaine, pas de quoi s’occuper bien longtemps. Et pourtant, ce ne sont pas les petits problèmes amusants qui manquent.
Pour essayer un peu d’essayer par moi même ce que cela pouvait donner, je me suis plongé dans un problème tout bête qui me dérangeait depuis un moment : comment faire lemendel10s jolis dessins de fractales de l’ensemble de Mandelbrot, cette formulaire quasi légendaire qui a le droit à ses chansons sur Youtube.

Le principe est simple : on prend un nombre complexe c, on part de U0 = 0, et on applique la formule Un+1 = Un² + c. Dès que |Un| > 2, on s’arrête (on peut montrer qu’alors la suite diverge en l’infini). On se fixe un nombre maximal d’itération avant d’abandonner. Le nombre d’itération avant d’arriver à une norme supérieure à 2 donne la couleur.

De mystérieux problèmes de vitesse d’exécution

Ce qui est agréable, c’est que  ce problème est trivialement parallélisable, on forme un nombre c = x + i.y avec chaque pixel de l’écran et on calcule les éléments de la suite, indépendamment des autres pixels. Ce qui est moins sympathique, c’est que je n’ai pas vu comment faire beaucoup mieux … pour obtenir une bonne qualité de dégradé, il faut un nombre d’itérations de l’ordre de 200-500. Et s’il existe une manière astucieuse d’arriver à calculer le terme d’indice 500 sans avoir à calculer tous les précédents, elle n’est pas évidente. On se retrouve donc avec la frustration de ne pas pouvoir faire mieux, même si on multiplie le nombre de cœurs …

mendel8Et si le calcul se fait en 3 ms pour une image triviale (écran où tous les pixels convergent en 1 itération), on atteints 300 ms dans le pire des cas. Ou approximativement 150ms sur une image dont la moitié est triviale et l’autre moitié affreuse. Ca ressemble quand même pas mal à de la proportionalité pour quelque chose qui devrait etre constant. Pourtant, le calcul se fait bien en parallèle : sans utiliser CUDA, les images mettent plusieurs centaines de millisecondes dans les meilleurs cas et plusieurs secondes dans le pire cas, .
Quand on regarde au niveau de la taille de l’image, ce n’est pas non plus aussi simple qu’on le voudrait. 5ms pour une image 100*100, 8 ms pour une image 1000*100 ou 200*200 et 13 ms pour une image de 1000*1000. Ce n’est pas aussi constant qu’on le voudrait, mais quand même, ça y ressemble.
Ce qui est alors intéressant, c’est qu’en prenant une image 200*200, on passe de 0.7 ms pour un image triviale à 17 ms dans le pire cas. Soit à peu près un facteur 20. Dans le cas d’une image 1000*1000, on passe de 3ms à 300ms soit un facteur 100.
D’où vient cet écart ? Est-ce une limite du nombre de threads, est-ce un problème d’accès mémoire (je n’ai pas du tout travaillé l’optimisation) ? Il reste encore des mystères à percer sur le fonctionnement de CUDA …

Le code est accessible sur Pastebin

Exploration de l’ensemble de Mandelbrot

mendel2.pngAprès tout ces histoires de temps de calcul, il faut quand même de jolies images. Et rien qu’avec cette pauvre formule z² + c, il y a un bon paquet de choses à explorer. Tellement que même après des dizaines de tentatives, je tombe encore sur des motifs que je n’avais jamais vu auparavant …mendel5

Alors que l’on crois reconnaitre un motif, on découvre en zoomant qu’en fait il y a d’importantes différences.

Ici par exemple, on croit en voyant le “point bleu” au centre que l’on a retrouvé le motif initial …mendel6

On s’approche, on s’approche, et en effet, ça y ressemble beaucoup !

Mais quand on finit de zoomer, en découvre des spirales dont les nœuds ont 8 branches.
Mais dans d’autres cas, on retombe en effet sur le motif initial.mendel7mendel3Il y a en suite les endroits incroyablement simples. La couleur est presque unie. Les motifs sont quasi-circulaires … tout parait parfaitement ordonné.

mendel4

Une grande famille pleine de variantes

mendel9Et tout ça, c’est pour l’ensemble de Mandelbrot habituel. Mais si on commence à jouer avec la formule, on tombe sur des centaines d’autres fractales tout aussi surprenantes.

Même en écrivant n’importe quoi comme formule de récurrence, on tombe sur des motifs jolis de ce style.
Et comme à chaque fois, on zoom, on zoom et on retombe sur un motif qui n’a absolument rien à voir.

Quand je vois des formules aussi simples qui donnent d’aussi belles images, je me demande pourquoi on se limite au lycée à voir des suite arithmétiques ou géométriques. Les mathématiques seraient sans doute un peu plus appréciées par certains si on leur donnait l’occasion de découvrir le côté artistique qui se cache derrière des formules à priori abstraites et ennuyeuses.