11 octobre 2013

Brève initiation à la programmation parallèle par Kevin Coulomb

Kevin Coulomb travaille en tant qu’ingénieur de recherche et développement pour SysFera, société éditrice de logiciel spécialisée dans les questions de HPC. Il développe des codes open source liés au parallélisme et à la distribution des calculs principalement dans les langages C et C++.
Kevin donne la formation Programmation parallèle chez Human Coders.

 

La programmation parallèle

Avec le développement des architectures multi-coeurs, que l’on soit un simple développeur sur son portable ou que l’on bosse sur un super-calculateur, on est de plus en plus amené à avoir accès à du matériel fait pour être utilisé de manière concurrente et simultanée par un ou plusieurs jeux d’instructions.

On peut avoir deux réactions, la première est d’ignorer le phénomène et se dire que de toute façon, si son code est actuellement peu performant, il suffit d’attendre quelques mois et d’après la loi de Moore le matériel sera suffisamment puissant pour supporter le programme. On peut également vouloir tirer profit de la puissance qu’offre le matériel pour mieux utiliser les ressources auxquelles on a accès et offrir à l’utilisateur un confort nouveau.

Tout cela parait intéressant, mais concrètement, comment fait-on pour exploiter et paralléliser un programme ?

Trouver du parallélisme

Le premier point à considérer est de repérer les différents aspects parallèles dont un programme peut faire preuve. Prenons l’exemple d’un programme classique séquentiel qui calcule la météo en France pour le lendemain. Si on prend en compte l’étendue de la surface où il faut calculer divers éléments (la pression, l’humidité, les vents, etc.), cela donne un maillage (modélisation géométrique de la terre dans cet exemple) extrêmement complexe et complet avec énormément de calculs à faire. La première étape est donc de trouver les différents éléments parallélisables dans notre maillage et de déterminer les différents niveaux de parallélisme.

Le premier niveau de parallélisme se situe au niveau du domaine, plutôt que d’avoir un processeur qui calcule sur toute la France les valeurs des éléments (pression, humidité, vent), pourquoi ne pas découper la France en sous domaines ? Ainsi chaque processeur calculerait une partie restreinte du maillage initial.

Le second niveau de parallélisme se situe au niveau des éléments, pourquoi ne pas redécouper sur chaque zone et utiliser un thread qui gérera la pression, un autre qui gérera l’humidité, etc.

Le troisième niveau se situe au niveau du code lui-même, au lieu de faire une boucle for sur un ensemble de valeurs, pourquoi ne pas paralléliser cette boucle for ligne 42 par exemple ?

Au final, au lieu d’avoir besoin d’un serveur ultramoderne et sur-puissant pour calculer la météo de demain, il est possible d’avoir le résultat plus rapidement en utilisant des machines beaucoup plus modestes et en découpant intelligemment le programme. De plus, si du jour au lendemain nos données en entrée changent (un maillage plus fin de la France pour plus de précision ?), il est toujours possible de rajouter un ou plusieurs processeurs pour gérer les domaines supplémentaires. Même sans ajouter de ressources, la hausse de la taille des données en entrée sera en partie atténuée par la répartition de ces calculs supplémentaires sur chaque processeur.

De l’importance de l’architecture sous-jacente

Pour paralléliser un programme, cette partie théorique est primordiale, savoir repérer les zones de parallélismes possibles et les zones intrinsèquement séquentielles (qui nécessitent une synchronisation des données par exemple) est nécessaire pour faire une bonne parallélisation. Toutefois ce n’est pas suffisant, l’aspect théorique est important, mais la connaissance de l’architecture sous-jacente se révèle souvent primordiale. En effet rien n’est dit sur « la taille » des domaines à découper sur l’exemple ci-dessus, et d’une ressource de calcul à une autre, cette valeur peut influer énormément sur la phase de calcul. Un programme parallèle qui perd tous les effets de cache pourra se retrouver moins performant qu’un programme séquentiel bénéficiant des effets de cache. De manière similaire, un programme parallèle qui passe son temps à se resynchroniser perdra au final plus de temps à se synchroniser qu’il permet d’en gagner en parallélisant les tâches.

Des concepts d’implémentations

Une fois ces considérations terminées, vient la mise en place programmatique du parallélisme avec le découpage du programme et les pièges qui viennent avec : comment partager une variable entre plusieurs threads et plusieurs processus sur plusieurs machines ? C’est là que les concepts type « mutex » (mutual exclusion, objet garantissant l’exclusion mutuelle de l’accès à une donnée), « signal », « sémaphore » (sorte de mutex généralisé), « communication (a)synchrone », « communication bloquante », … arrivent et posent des problèmes. Quand on commence à manipuler ces objets, le début est très souvent frustrant : un programme qui bloque ‘sans raison’, un programme qui crashe soudainement alors que le cœur du programme n’a pas changé, des données erronées qui sont échangées, un programme qui va au bout avec un résultat final faux, … et bien souvent le développeur se retrouve découragé car peu d’outils de debug performants sont disponibles. De plus, la complexité du système mis en place complique bien souvent la compréhension de l’origine du problème. Par exemple, un débordement mémoire sur un processus peut entraîner l’envoi, plus loin dans le code, d’une mauvaise donnée à un autre processus, qui lui échouera à cause de cette valeur. Enfin, quand tous les processus communiquent entre eux, non seulement trouver le processus fautif est déjà problématique, mais il reste encore la majorité de la partie debug à faire.

Bilan

Comprendre et savoir utiliser les architectures parallèles n’est pas une chose aisée, chaque cas est particulier et il n’y a pas de « ciseau magique » pour découper un programme et le paralléliser. Il est possible de se former seul, avec de la logique, des expériences et de la patience on peut obtenir un résultat que l’on juge satisfaisant. Il est généralement recommandé de suivre une formation spécifique pour comprendre plus en détails les concepts et les facteurs qui influent sur une application parallèle, et éviter de nombreux écueils.

Bon courage à tous ceux qui souhaitent se lancer dedans.

 

Retrouvez la formation Programmation parallèle dans notre catalogue de formation.