Greg's Devblog Par un développeur, pour les développeurs

Mandelbrot en parallèle

Aujourd'hui à la fac, c'était programmation parallèle d'un Mandelbrot. C'est du fractal, et ça se prête très bien à de la programmation parallèle, puisqu'en fait on itère N fois sur chaque pixel, indépendamment des voisins, pour savoir si on doit l'afficher ou pas (et avec quelle couleur).

La conception du code s'est faite en plusieurs phases :

1. Version séquentielle

Exécution du code en version séquentielle, histoire de voir le temps que ça prend et d'avoir un résultat qui puisse servir d'étalon... Résultat : entre 7 et 8 secondes pour générer l'image avec les paramètres par défaut.

2. Version parallèle, statique.

Réalisation d'une version pouvant tourner en parallèle avec N processus. La méthode est relativement simple et naïve : au démarrage de chaque processus, on récupère le numéro du processus (de 0 à N-1), ainsi que le nombre total de processus lancés. A partir de là, on découpe l'image en N bandes (on garde toute la largeur, on découpe en hauteur), chaque processus calcule sa portion, puis tout le monde envoie la portion calculée au processus 0, qui enregistre l'image finale (et affiche le temps total).

Et là, surprise, même avec 8 ou 10 processus, le gain est assez faible : on tourne en 2.5 à 3.5 secondes, soit à peine 2 à 3 fois plus vite (alors qu'on a pourtant 4 à 5 fois plus de puissance, normalement !).

La raison est en fait rapidement trouvée : les lignes du milieu mettent beaucoup plus de temps à calculer que les lignes aux extrémités (en fait tout ce qui est noir sur l'image a mis longtemps à être calculé). Du coup, les processus qui se tapent les bords en haut et en bas finissent super vite (en 0.05 secondes !), alors que les processus qui ont le milieu à calculer mettent plus de 2 secondes... C'est du beau gachi de puissance, il convient donc de concevoir un truc un peu plus dynamique qui puisse répartir au mieux la charge...

3. Version parallèle, mais dynamique !

La dernière version à être réalisée va donc avoir une approche beaucoup moins statique : le processus 0 ne va rien calculer, mais va en fait servir de chef d'orchestre, et va dire aux autres quoi calculer. A chaque fois qu'un processus a fini de calculer une portion de l'image, il l'envoie au processus 0, qui va ensuite lui redonner un ensemble de ligne à calculer.

Cette fois-ci, on va donc envoyer aux processus des blocs de 1 à 8 lignes à calculer (limites arbitraires et qu'on peut changer pour optimiser les choses), et donc au pire si un processus met beaucoup de temps pour calculer les 8 lignes du milieu, pendant ce temps les autres processus calculeront peut-être 32 lignes ou plus, puisque la charge est répartie dynamiquement !

Et là, le résultat est sans appel, c'est beaucoup mieux : on arrive sous la barre de la seconde, dès qu'on a 8 processus ou plus ! Et pourtant, le processus 0 ne calcule rien, il ne fait que récupérer le résultat des autres :p  On a donc à présent un système qui tient bien la charge, qui peut supporter un grand nombre de processus, et qui s'adapte aux besoins. On peut même avoir un parc hétérogène de machines, ce n'est plus gênant.

4. Pour aller plus loin...

On peut à présent réfléchir à des optimisations pour ce système.

En fait, la faille est que cette fois-ci on passe pas mal de temps dans les communications à cause des transferts de taille relativement faibles. De plus, si tous les processus finissent de calculer à peu près en même temps, alors ils vont tous devoir attendre que le processus 0 ait reçu les messages pour continuer, donc on a tout de même une partie du temps qui est perdu en communication et surtout en attente de communication. Plusieurs stratégies peuvent permettre de limiter ce temps, en voici quelques une en vrac :

• Faire des paquets plus gros : si on fait des paquets plus gros, on fera au total moins de communications, donc en théorie on devrait aller plus vite. Sauf qu'on s'expose au risque d'avoir à attendre à la fin un processus trop lent qui aurait eu un gros bloc à finir... On pourrait donc imaginer faire calculer des blocs de grande taille au début, et réduire la taille et fur et à mesure de l'avancement. Comme ça, à la fin, tout le monde aura de petites taches, et devrait finir sensiblement en même temps...
• Permettre au processus 0 de travailler ! Pourquoi devrait-il perdre son temps à attendre les autres ? En fait, il pourrait s'allouer une ligne à calculer, mais regarder tous les X pixels s'il n'a pas une communication en attente. Comme ça, il participe aussi au calcul, et on devrait gagner un peu (mais plus on aura de processus, moins ça sera intéressant, car plus il devra communiquer de toute façon)
• Dans la version actuelle, les communications sont synchrones : quand on demande à avoir des lignes à calculer, on est bloqué en attendant que le processus maître réponde... Une meilleure stratégie pourrait être d'envoyer la demande de façon asynchrone (ie, non bloquante) quand on arrive au milieu du calcul, de façon à avoir la réponse sous le coude à la fin du calcul. Comme ça, dès que c'est fini, on a de fortes chances d'avoir le message près en réception. Dans le même genre, on pourrait imaginer se voir confier 2 taches à la fois par le processus maître, et donc quand on fini la première on en redemande une, etc... Je pense qu'au final ça revient sensiblement au même, à voir.
• Mieux répartir la charge dès le départ. Cette stratégie est celle préconisée par Mathias, tout le mérite lui en revient ^^ En gros, on peut imaginer calculer au début une version simplifiée (calculée plus rapidement, ou alors plus petite) afin de localiser plus rapidement les zones noires, et donc dès le départ faire des paquets de taille variable selon la charge de travail estimée (avec les options par défaut, le temps pour traiter un pixel varie d'un facteur 10 000 entre les pixels les plus rapides à calculer et les plus longs). Au lieu d'envoyer des paquets de taille relativement fixe (et donc représentant une charge de travail très variable), on peut alors envoyer des paquets dont les charges effectives sont proches.
• Tenter de répartir un peu mieux les temps de communications entre les différents processus : là le facteur ralentissant est que tout le monde communique avec le processus 0. On pourrait imaginer sous-découper les processus et l'image en 2 groupes (voire plus), leur faire se débrouiller avec ça, et puis à la fin rassembler les lignes calculées. On limite alors les communications car 2 processus (voire plus) vont centraliser les appels. Dans cette optique, on pourrait avoir une partie des processus qui remplissent l'image par le haut, et l'autre partie par le bas : quand les 2 groupes se sont rejoints, on s'arrête !

Et alors ?

Bah rien ^^ J'ai trouvé ça sympa comme sujet, donc je me suis dit que j'en ferai un billet :p Bon, c'est sûr que c'est plus facile de faire ce genre de chose à la fac où on peut monopoliser 16 PCs en même temps (dual core, donc potentiellement 32 processus à pleine vitesse), alors que chez soi on a bien moins de matériel... Je devrais peut-être économiser pour installer une ferme de PCs chez moi en fait :p