Tech Days 2010 : Développement parallèle efficace

Executive summary : quand on parle de programmation parallèle, on pense immédiatement threads, locks, etc. Avant de se jeter dans ceci, il est bon de prendre un peu d’altitude et de faire de la modélisation des problèmes de concurrence comme on le ferait pour n’importe quel besoin métier. Il y a d’ailleurs des méthodes bien rôdées pour cela.

Première session technique, présentée par Bruno Boucard, sur la façon de créer ou de modifier un logiciel pour avoir un bon parallélisme. Pas orienté code, mais très bien du point de vue de l’architecture, et en particulier des approches que je n’ai pour l’instant pas trouvées dans de la littérature. De plus, du retour d’expérience très pratique qui ajoute une réelle valeur à la session.

Décomposition du travail d’architecture pour la parallélisation

Il est important de bien suivre une approche réfléchie et ne pas se lancer tête baissée dans le code. Ca paraît évident, mais la programmation parallèle a une telle réputation de domaine d’expert qu’on ne pense pas nécessairement à la partie non-technique. Les étapes proposées sont :

1. Mesurer la performance : cette étape est essentielle pour avoir une référence, sur laquelle on pourra se baser pour savoir si la parallélisation qu’on met en place résulte effectivement en une amélioration des performances globales de l’application.
2. Trouver la concurrence :
   1. L’application à paralléliser est-elle orientée données ou orientée traitements ? Ceci va bien sûr modifier l’approche de parallélisation.
   2. Trouver les dépendances fonctionnelles (inaltérables) ou techniques (sur lesquelles on peut éventuellement travailler) avec de l’outillage type NDepend.
   3. Décomposer les tâches à l’aide de ces informations, et en regardant bien la granularité des tâches, c’est-à-dire le nombre d’instructions dans chaque. Si on est sur des tâches très granulaires, attention à la partie incompressible (démarrage d’un thread, etc.).
3. On recherche alors le meilleur algorithme pour ce genre de fonctionnement :
   1. Données linéaires ou récursives => décomposition géométrique ou récursive.
   2. Tâches linéaires ou récursives => parallélisme des tâches ou division des tâches.
   3. Flux de données régulier ou pas => approche de type pipeline ou coordination orientée événements.

Quelques notes supplémentaires

Attention au problème de false-sharing : si on crée deux ensembles de données proches en mémoire (membres d’une même classe, index adjacents dans un tableau, etc.), on risque, lors de la mise en concurrence, de se retrouver avec des mises à jour importantes du cache L2 qui pénalisent la performance. Une démo montre qu’on prend facilement un facteur de 5 sur ce genre de détail.

Parcours d’un arbre : on est typiquement dans le cas récursif. On peut donc utiliser une parallélisation récursive, en faisant particulièrement attention à la profondeur de l’arbre, qui est le principal paramètre jouant sur le type de décomposition.

Diviser pour mieux régner : le bon exemple qui fait tout de suite comprendre de quoi on parle est le quicksort. Dans cet algorithme de tri, on découpe de manière récursive la liste en deux domaines, puis on traite chacun des ensembles de manière séparé. Attention dans ce cas-là : il ne faut pas non plus trop gonfler le nombre de tâches, car on perd alors en performance.

Les agents sont des systèmes qui isolent les données, et qui communiquent uniquement par des canaux. En gros, ça revient à porter l’immuabilité, qui est très importante pour la parallélisation, à un niveau plus haut dans l’architecture logicielle : ce n’est plus seulement une instance de classe qui est immuable, mais un ensemble de données qui est, vu de l’extérieur, comme fixé pendant que l’agent prend en charge son traitement. Du coup, l’agent peut se concentrer sur son traitement métier sans se préoccuper des locks, priorités, etc.

La programmation parallèle a aussi ses best practices, et propose plusieurs patterns d’utilisation dans les programmes :

• Single Program Multiple Data : plusieurs traitements identiques sur des données découpées en blocs typiquement de même taille.
• Master Worker : le master push du boulot aux workers par une queue, et les workers traitent.
• Boucle parallèle : décomposition géométrique de données.
• Fork / Join : on lance plusieurs tâches en parallèle et on attend leur fin. Cette méthode s’adapte bien à de nombreux cas.

Pour éviter au maximum les locks retardant les threads si ils lisent de la donnée partagée, on peut utiliser le Thread Local Storage.

ConcurrentQueue<T> encapsule une Queue<T> en l’exposant de la même manière, mais en garantissant une prise en charge efficace des locks, et en la masquant au consommateur.

Conclusions

Les conclusions du présentateur de la session sont les suivantes :

• Prendre un haut niveau d’abstraction.
• Utiliser des solutions simples à maintenir.
• Attention à bien utiliser des librairies threadsafe.
• Ne jamais préjuger de l’ordre d’exécution : l’ordre d’exécution des threads n’est pas déterministe, et on peut très bien se retrouver avec une application qui fonctionne dans certains cas et pas d’autres. Attention donc à bien tester la justesse du code.

Il insiste également sur l’importance de l’itératif. Comme pour le code métier, il faut itérer pour arriver à un bon résultat. Le but derrière étant de revenir au Free Lunch, bref la bonne vieille époque où les applications allaient plus vite car les processeurs augmentaient en fréquence. Sauf que maintenant, il faut arriver à architecturer les applications de façon qu’elles gagnent automatiquement en performance lorsque le nombre de cœurs augmente, l’augmentation de performance par la montée en fréquence étant tarie.

Personnellement, je retiens surtout la notion de modélisation, d’architecture en étape pour mettre en place le parallélisme, et je note les trois bouquins référencés par Thierry Boucard, à savoir :

• Patterns for Parallel Programming
• Concurrency in Programming Languages
• The Art of Concurrency

On a souvent tendance à prendre le parallélisme du point de vue technique (PLinq, OpenMP, etc.), mais, comme d’habitude, il est essentiel de prendre de la hauteur pour faire des bons programmes. Bref, une session très utile pour prendre le problème de la parallélisation par le bon bout.