Petit panorama de la programmation parallèle

Introduction



La programmation parallèle est à la mode. En effet, la course effrénée aux Ghz des années 2000 a laissé peu à peu la place à la multiplication du nombre de coeurs de calculs. Mais contrairement à l'augmentation de la fréquence des processeurs dont les développeurs pouvaient profiter presque sans effort, l'accès de façon simultanée à plusieurs unités de calcul requiert une nouvelle façon de penser les programmes. Encore relativement peu enseignée dans les cursus universitaires, il s'agit pourtant de la manière standard dont devront être pensés les algorithmes dans les années à venir (avant de laisser peut être la place un jour à la technologie des ordinateurs quantiques, ce qui, pour le coup, demandera un certain temps ... d'adaptation).

Mais ce que l'on désigne par le terme générique "programmation parallèle" peut en fait revêtir des aspects assez différents dans la pratique. Concevoir des algorithmes capables de s'exécuter sur les dizaines de milliers de coeurs des supercalculateurs n'a en effet pas grand-chose à voir avec la parallélisation d'une boucle où chaque itération s'exécute de manière indépendante sur chacun des coeurs d'un ordinateur de bureau. Le principe de base reste le même : découper et répartir de manière efficace les tâches entre les ressources de calculs, mais les problématiques peuvent être assez éloignées. L'objectif de cet article est d'essayer de présenter ces problématiques et les technologies de parallélisation associées.

Terminologie



Pour bien comprendre la suite, il est nécessaire d'avoir en tête la signification de quelques termes :

- processeur vs coeur : Un processeur est l'entité matérielle qui regroupe un ou plusieurs coeurs (core en anglais) de calcul (par exemple l'Intel Core i7 2600K dispose de 4 coeurs de calcul). Le système d'exploitation va pouvoir exécuter des tâches en parallèle sur ces différents coeurs. Si plusieurs programmes ou logiciels sont en fonctionnement, ils pourront s'exécuter de manière simultanée au lieu de s'exécuter chacun leur tour. L'avantage de la parallélisation est de permettre à unique programme de bénéficier de la capacité de calcul de tout ou partie des coeurs présents sur une machine pour accélérer sa vitesse d'exécution. A titre de remarque, des technologies comme l'Hyperthreading ajoutent une couche supplémentaire entre le processeur et les coeurs : 4 coeurs matériels sont ainsi vus comme 8 par le système d'exploitation ce qui permet de maximiser l'utilisation des entités de calcul en minimisant les temps morts.

- processus vs thread : Une application peut s'exécuter sur plusieurs processus, chacun d'entre eux pouvant comporter plusieurs threads. Il s'agit de deux niveaux distincts de parallélisme : les applications multiprocessus sont plutôt destinées à être exécutées sur de très nombreux processeurs à mémoire distribuée, tandis que le multithreading nécessite l'accès des threads à une mémoire partagée. Ainsi, le parallélisme sur des ordinateurs personnels ou sur des petits serveurs est en général le fruit d'un multithreading, tandis que du parallélisme entre des machines distantes, sur des clusters de calcul ou sur des supercalculateurs est souvent basé sur des codes multiprocessus. Ces derniers s'exécutent comme des applications complètement indépendantes qui communiquent entre elles les informations nécessaires au bon fonctionnement du programme.

- mémoire partagée vs mémoire distribuée : Deux technologies de gestion de la mémoire coexistent pour répondre à des besoins différents. Lorsque l'on parallélise un programme sur son ordinateur de bureau, tous les coeurs de calcul vont pouvoir accéder à la même mémoire, en l'occurrence les barettes de RAM de la machine. La communication des informations est alors assez simple, puisque tous les threads peuvent avoir accès à toutes les informations. Cependant, à partir d'un certain nombre de processeurs, le partage de la mémoire n'est plus possible : les serveurs de taille importante sont divisés en plusieurs unités (ou noeuds) interconnectées (via un réseau Infiniband par exemple) : la mémoire est alors dite distribuée sur les différents noeuds. Chacune de ses unités peut elle-même disposer de plusieurs processeurs accompagnés d'une mémoire locale.

Petit exemple d'architecture



Pour illustrer les différentes composantes du paragraphe différents, voici à quoi peut ressembler un calculateur de taille modeste :


calculateur


L'architecture est constituée de plusieurs noeuds qui peuvent être vus comme autant de machines indépendantes interconnectées. Chacun de ces noeuds abrite un ou plusieurs processeurs ainsi qu'une mémoire partagée (au niveau du calculateur, la mémoire est considérée comme distribuée). Enfin, chacun de ces processeurs peut lui-même être composé de plusieurs coeurs. A titre de comparaison, un ordinateur de bureau, lui, à une architecture qui se rapproche de celle d'un seul de ces noeuds : un processeur à un ou plusieurs coeurs qui partagent la même mémoire.

Cet exemple va permettre de présenter différentes stratégies de parallélisation d'un programme. Pour la suite on en retiendra 3 principales :
- le SIMD qui permet à un coeur de paralléliser certaines opérations
- le Multithreading qui va permettre à un programme d'utiliser toutes les ressources d'un noeud
- le Multiprocessus grâce auquel l'ensemble du calculateur va pouvoir être utilisé

Au coeur d'un coeur, le SIMD



Commençons par la parallélisation de plus bas niveau, celle au plus proche de l'architecture des processeurs, le SIMD. SIMD est l'acronyme de Single Instruction, Multiple Data. Le principe en est le suivant : lorsque des opérations simples doivent être effectuées sur toute une série de données, alors l'unité de calcul a la possibilité d'utiliser des instructions (SSE, AVX...) effectuant ces opérations en parallèle, de manière vectorielle. Souvent, ce n'est pas au développeur de s'occuper de ce niveau de parallélisation (à moins qu'il ne programme en assembleur), les compilateurs se chargeant de cette tâche d'optimisation. Toutefois, des compilateurs comme l'Intel ICPC permettent de mettre les mains dans le cambouis et d'ajuster à la main la vectorisation de certaines boucles (se reporter à la documentation de l'ICPC pour davantage de détails).

On notera que la parallélisation sur cartes graphiques (GPU computing) qui s'est développée ces dernières années utilise cette approche bas niveau : de nombreux coeurs appliquent les mêmes opérations à un ensemble de données. Certains algorithmes peuvent ainsi bénéficier d'une accélération très appréciable, mais pour d'autres qui nécessitent des accès à des éléments éloignés les uns des autres en mémoire, les performances sont nettement moins bonnes. Tout dépend donc de l'application concernée. Pour tirer parti de ce type de parallélisation, il faut aller au plus près du matériel et bien maîtriser la façon dont les unités de calcul opèrent sur les données pour optimiser la répartition des tâches sur des grilles de blocs de threads.

Le Multithreading, ou comment paralléliser sans se prendre la tête...



Le Multithreading est le type de parallélisation le plus couramment utilisé aujourd'hui et qui permet à une application de tirer parti de la puissance de calcul de tous les coeurs d'une machine. Le principe en est le suivant : le programme est subdivisé en parties séquentielles (exemple : initialisation du programme, lecture de données etc...) et en parties parallèles (boucles de calcul, algorithmes etc...). Dans les zones parallélisées, tous les threads ont potentiellement accès à l'ensemble des données du programme (mémoire partagée) : cela simplifie grandement les choses par rapport au multiprocessus, mais il faut toutefois veiller à bien gérer la portée des variables (privées ou partagées) pour éviter des écritures simultanées aux mêmes adresses mémoire.

Le multithreading passe par l'utilisation de bibliothèques qui permettent d'atteindre différents niveaux de performances (les temps d'overhead peuvent être sensiblement différents par exemple) parmi lesquelles on peut compter : OpenMP (simple à mettre en place, utilisation de directives #pragma), Intel Threading Building Blocks (utilisation de templates à la manière de la bibliothèque standard du C++), Intel Cilk Plus, POSIX Threads, Qt threads (pour par exemple déléguer l'affichage et le calcul à des threads différents)... Le nouveau standard C++ 2011 marque aussi l'avènement d'outils de threading au sein de la bibliothèque standard (std::thread), ce qui représente tout de même une nouvelle fonctionnalité majeure du langage.

Avec certains de ces outils, la parallélisation d'une boucle peut se faire par l'ajout d'une seule ligne, alors pourquoi s'en priver ?

Le Multiprocessus, ou comment paralléliser en se prenant la tête...



Malheureusement, le multithreading se heurte à une barrière matérielle. En effet, à partir d'une certaine taille, les machines sont subdivisées en noeuds de calcul : l'ensemble de la mémoire n'est alors plus visible par tous les processeurs et les ennuis commencent. Les idées sous-jacentes au multiprocessus sont globalement les mêmes que le multithreading mais la grande différence est qu'ici toutes les variables sont privées. Une application peut ainsi être vue comme un ensemble de programmes indépendants qui à certaines occasions communiquent des informations. La difficulté supplémentaire est que chaque communication peut être assez coûteuse en temps (et plus il y a de noeuds, plus cela est coûteux) et qu'il faut donc ne pas en abuser. De plus, la mémoire disponible par noeud peut ajouter une certaine complexité par rapport au multithreading. Il est en effet évident qu'il est vain d'essayer de communiquer l'ensemble des données d'un noeud à un autre pour des raisons d'occupation mémoire. D'autre part, si dans le cas du multithreading il est nécessaire de bien répartir la charge de calcul sur les différents coeurs, dans le cas du multiprocessus il est également nécessaire d'équilibrer la charge en mémoire. La programmation multiprocessus repose donc sur un équilibre entre le nombre de communications, le volume des données communiquées et la répartition de la charge en calcul et en mémoire. Dans certains cas, il peut même être avantageux de recalculer certaines quantités plutôt que de les stocker et de les transmettre.

L'une des bibliothèques phare de la programmation multiprocessus est MPI (pour Message Passing Interface) disponible en C, C++ et en Fortran. Comme son nom l'indique elle permet à des processus indépendants de se passer des messages et elle est devenue au fil des ans un standard pour les supercalculateurs. Elle inclut des fonctions pour envoyer des messages (MPI_Send, MPI_Isend...), pour en recevoir (MPI_Recv, MPI_Irecv...), pour synchroniser les processus (MPI_Wait...), pour diffuser des données (MPI_Bcast...) ou les réduire (MPI_Reduce...) selon des arbres de communication permettant une scalabilité logarithmique. Une nouvelle norme majeure, la 3ème, est prévue pour bientôt avec l'ajout de nouvelles fonctions et une clarification du standard.

La programmation Multiprocessus Multithreadée



Très souvent, les applications sont soit multithreadées pour travailler sur un nombre de coeurs restreint, soit multiprocessus pour travailler sur un grand nombre de coeurs. Toutefois, il peut être avantageux de profiter du meilleur des deux mondes. En effet, pour les nouvelles générations de supercalculateurs qui atteindront des centaines de milliers de coeurs, de trop nombreuses communications peuvent augmenter significativement le temps de calcul. La solution est alors d'utiliser MPI pour communiquer d'un noeud à l'autre, et d'utiliser du multithreading pour assurer la parallélisation au sein de chaque noeud. Grâce à cette méthode hybride, on réduit le nombre de messages par un facteur égal au nombre de coeurs par noeud. Même si cela nécessite une réflexion en amont sur la cohabitation de deux paradigmes différents, le jeu en vaut la chandelle pour tirer le meilleur des performances d'une machine.

Conclusion



Cette courte présentation des différentes techniques de parallélisation s'achève ici. Trois méthodes sont particulièrement utilisées aujourd'hui : le SIMD au sein des processeurs, qui est le plus souvent à la charge des compilateurs, le multithreading pour les architectures à mémoire partagée, et le multiprocessus pour les architectures à mémoire distribuée. La parallélisation par thread est devenue au fil des ans assez simple à mettre en place, mais reste limitée à des machines de taille modeste. La parallélisation par processus permet de lever cette limitation au prix d'une conception un peu plus complexe. Finalement, le mélange de ces deux techniques permet d'exploiter au mieux un calculateur.
Para obter informações mais completas sobre otimizações do compilador, consulte nosso aviso de otimização.