Parallélisation

De Wiki de Calcul Québec
Aller à : Navigation, rechercher
Autres langues :anglais 100% • ‎français 100%

Note : Une partie de cet article est inspiré des pages de Wikipédia anglaise et française sur le parallélisme en informatique.

Sommaire

Introduction

Jusqu'au début des années 2000, l'accélération des calculs informatiques se faisait en augmentant la fréquence d'horloge des processeurs. Le nombre d'opérations à effectuer pour résoudre un problème étant constant (pour un calcul déterministe), augmenter la fréquence d'horloge permettait ainsi de traiter davantage d'opérations par seconde et de réduire les temps de calcul. Malheureusement, pour des raisons physiques, la fréquence d'horloge a saturé aux environs de quelques gigahertz vers 2004 pour tous les processeurs. Il devient dès lors très difficile, voire impossible, d'accélérer un calcul simplement en l'exécutant sur une architecture plus rapide. Il est ainsi aujourd'hui nécessaire d'exploiter la puissance de plusieurs unités de calcul en parallèle.

Types de parallélisation

Il existe plusieurs niveaux de parallélisme. Il y a d'abord une forme de parallélisme automatique, dont font partie le parallélisme des bits et le parallélisme des instructions. Ces deux types de parallélisme sont assurés par les processeurs, via des instructions spécifiques, et par les compilateurs qui exploitent ces instructions.

Parallélisme des données

Il y a ensuite le parallélisme des données. Dans ce cas, la même tâche est exécutée sur des jeux de données ou des paramètres différents. Les tâches sont alors complètement indépendantes algorithmiquement. C'est notamment le cas dans une approche d'exploration d'espace des paramètres (parameter sweeping en anglais). Notez que malgré l'indépendance algorithmique des tâches, celles-ci peuvent se partager certaines ressources. Ainsi, sur les superordinateurs, deux tâches indépendantes se partageront souvent le même bus mémoire, et se partageront presque toujours le même réseau et le même système de fichiers. Il est important d'avoir conscience de ces ressources partagées afin de bien optimiser ses tâches. Vous voudrez ainsi généralement limiter au maximum vos accès au système de fichiers et vos communications réseau afin de rendre vos tâches indépendantes de celles des autres utilisateurs.

Parallélisme des tâches

Il y a finalement le parallélisme des tâches. Dans ce cas, une tâche sur un jeu de données fixe est divisée en sous-tâches indépendantes qui sont exécutées sur des unités de calcul distinctes. La réalisation de la tâche principale nécessite généralement des points de synchronisation, ou d'échanges de données entre les sous-tâches. Ces communications limiteront généralement le gain de performance atteignable. Implémenter ce type de parallélisme au sein d'un algorithme nécessitera modifications - parfois substantielles - au code de l'application.

Loi d'Amdahl

La loi d'Amdahl exprime, en termes mathématiques, que le gain maximal atteignable pour une optimisation donnée d'un algorithme, est limité par la portion non optimisée de l'algorithme. En considérant la parallélisation comme une optimisation, on peut ainsi dire que le gain atteignable par la parallélisation est limité par la portion de l'algorithme qui demeure séquentielle. Dans un cas optimal, la parallélisation d'un algorithme complet offre un gain linéaire : en doublant les ressources disponibles, le temps d'exécution est divisé de moitié. En pratique par contre, on parallélise généralement seulement une portion de l'algorithme. Ainsi, si on parallélise une portion du code qui requiert 10% du temps de calcul, on ne peut espérer obtenir un gain supérieur à 10%, même en utilisant une quantité infinie de ressources. De plus, dans le cas quasi omniprésent où la parallélisation requiert des communications supplémentaires, ce gain est diminué davantage. En pratique, le gain sur la portion parallélisée sera généralement linéaire à petite échelle, puis saturera à plus grande quantité de ressources.

Parallélisme des données

Le parallélisme des données est probablement la plus simple façon de paralléliser une tâche. Il n'y a en général aucune modification à faire à l'algorithme. Il suffit plutôt de lancer plusieurs tâches indépendantes sur un ou plusieurs nœuds de calcul, chaque tâche effectuant le calcul pour un jeu de paramètres donné.

Malgré qu'il ne soit pas nécessaire de modifier l'algorithme dans ce cas, il peut être nécessaire ou utile de modifier votre script de soumission. Ceci est en pratique nécessaire lorsque les nœuds de calcul sont dédiés par tâche, tel que sur Colosse et Mp2. En effet, dans une telle situation, si vous n'adaptez pas votre script de soumission, vous gaspillerez une partie des ressources qui vous sont allouées.

Tâches en arrière-plan

Tel qu'illustré dans la section Simulations séquentielles multiples, vous pouvez lancer plusieurs tâches en parallèle dans un même script de soumission si vous suffixez votre ligne de commande par le caractère &, et que vous ajoutez la commande wait à la fin de votre script. L'esperluette indique à l'interpréteur de commandes que la tâche doit être lancée en arrière-plan. La commande wait, quant à elle, indique à l'interpréteur de commandes que la complétion du script ne sera faite que lorsque toutes les commandes en arrière-plan lancées précédemment seront terminées.

Note : Si vous omettez la commande wait, le script se terminera et les tâches en arrière-plan seront terminées.

Lots de tâches séquentielles

Les lots de tâches séquentielles, supportées par Torque et Moab, permettent de gérer l'exécution d'un grand nombre de tâches en faisant varier un paramètre. Vous pouvez combiner cette technique avec les tâches en arrière-plan afin d'exécuter des centaines, voire des milliers de tâches avec une seule soumission. Pour un exemple de script de soumission avec des lots de tâches, voir la section Lot de tâches séquentielles.

GNU parallel

GNU parallel est un outil mis à disposition des utilisateurs sur certains superordinateurs de Calcul Québec. Comparativement aux tâches en arrière-plan et aux lots de tâches séquentielles, GNU parallel facilite la gestion d'un grand nombre de tâches de durées courtes (par rapport au temps de calcul maximal d'une tâche) ou de durées variables. Il s'agit d'un outil particulièrement utile pour optimiser votre utilisation des ressources, car il lance automatiquement une nouvelle tâche lorsqu'une première se termine.

BqTools

Les BqTools sont un autre outil facilitant la soumission de calculs en lots. Cet outil est disponible sur Ms2 et Mp2. Il s'agit d'un outil particulièrement utile pour faire varier des paramètres de simulation.

À prendre en considération

Bien que la parallélisation grâce au parallélisme des données permettent en théorie un gain optimal, ce n'est parfois pas le cas, dû à l'utilisation de ressources partagées. Il est important de réduire au maximum l'utilisation des ressources partagées. En ordre d'importance, pour une tâche séquentielle, on voudra réduire l'utilisation du système de fichiers, puis des accès à la mémoire vive.

Parallélisme des tâches

Le parallélisme de tâches fait référence au cas où ce sont les tâches à réaliser qui doivent être parallélisées, plutôt que les données ou paramètres d'entrée. Il s'agit d'un cas où il est presque toujours nécessaire de modifier le code source de l'application. Exception : dans certains cas très simples, les compilateurs sont parfois capables de paralléliser eux-mêmes une partie du code. Il existe traditionnellement deux façons de paralléliser une tâche : en utilisant plusieurs fils d'exécutions, ou en utilisant plusieurs processus.

Par fils d'exécution

Sous Linux, les fils d'exécution (threads en anglais) ont accès à un espace de mémoire vive commun. Ils peuvent ainsi opérer sur les mêmes données. Cela offre l'avantage qu'il n'est pas nécessaire de copier de la mémoire entre deux unités de calcul, et cela élimine pratiquement la communication entre les unités. L'inconvénient correspondant est par contre que le programmeur doit assurer la cohérence de la mémoire vive entre les fils d'exécution. Par exemple, si le fil d'exécution 0 doit lire et modifier un élément x en mémoire vive, le programmeur doit s'assurer qu'un autre fil d'exécution n'ira pas modifier ce même élément entre la lecture et l'écriture. On utilise pour ce faire des verrous (lock), ce qui est pratiquement une forme de communication entre les fils d'exécution. Les fils d'exécution sont aussi limités à s'exécuter sur un seul et même nœud de calcul. Le gain atteignable est ainsi limité par le nombre de fils d'exécution, qui sera typiquement égal ou inférieur au nombre de cœurs de calcul disponibles sur le nœud.

Pour paralléliser un programme en utilisant des fils d'exécution, on utilise (sous Linux), les pthreads, ou POSIX threads. C'est l'outil qui est généralement recommandé pour la parallélisation de programmes d'usage courant. Pour la parallélisation d'applications de calcul scientifique ou de haute performance, qui font généralement appel intensivement à des boucles, on recommande plutôt l'utilisation d'OpenMP. Il s'agit d'un jeu d'instructions - limité, mais simple et puissant - destinées au pré-compilateur C, C++ ou Fortran, qui facilite grandement la gestion des fils d'exécution. Paralléliser un programme en utilisant OpenMP peut s'avérer aussi simple que de rajouter deux ou trois lignes d'instructions bien placées. Le programme modifié présente aussi l'avantage de pouvoir être compilé aussi bien avec plusieurs qu'avec un seul fil d'exécution.

Références

Plusieurs pages d'introduction aux pthreads sont disponibles en ligne. En voici une courte liste :

Pour OpenMP, notre page de wiki présente plusieurs exemples. Le site web officiel contient aussi de bonnes références. Le tutoriel suivant est aussi une très bonne façon de se familiariser avec la programmation OpenMP.

Par processus : MPI

Contrairement aux fils d'exécution, les processus sous Linux ne partagent aucun espace mémoire. Cela a pour avantage qu'il est plus facile de s'assurer de l'intégrité des données en mémoire. En effet, outre par des techniques avancées telles que le RDMA, un processus ne peut pas, même par accident, modifier l'espace mémoire d'un autre. L'inconvénient de cet avantage est qu'il devient nécessaire de faire des opérations explicites de communication pour copier des données entre deux processus. On utilise généralement pour ce faire la bibliothèque de passage de messages MPI.

Contrairement à la parallélisation par fils d'exécution, la parallélisation par processus via MPI permet d'utiliser une quantité de ressources beaucoup plus élevée. En effet, les processus peuvent être aussi bien sur le même nœud de calcul que sur des nœuds différents. MPI permet une communication entre deux processus, peu importe leur interconnexion (Ethernet, InfiniBand ou mémoire partagée par exemple).

Références

Notre page wiki MPI liste un ensemble d'exemples d'utilisation de MPI. Le site MPI Tutorial (en anglais) offre aussi un bon tutoriel pour débutants.

Architectures massivement parallèles

Suite à la saturation des fréquences de processeurs, la tendance a été de fabriquer des processeurs disposant de plusieurs cœurs. Rapidement, les chercheurs se sont rendu compte qu'ils pourraient exploiter les processeurs graphiques, qui sont des processeurs massivement parallèles, de la même façon qu'ils utilisent des processeurs multicoeurs. La tendance continue de s'accélérer depuis l'introduction des processeurs à plusieurs cœurs intégrés (many integrated cores ou MIC) par Intel en 2012.

Processeurs graphiques

Les processeurs graphiques (GPU en anglais) sont des processeurs à basse fréquence disposant de centaines, voire de milliers, de cœurs. À titre d'exemple, le processeur K20X de NVidia dispose de 2688 cœurs cadencés à 732 MHz. Ces unités de calcul disposent de leur propre mémoire, séparée du système. Cette séparation pose en soit un défi supplémentaire : il faut transférer les données de la mémoire du système vers la mémoire du GPU, effectuer le calcul, puis rapatrier les données sur la mémoire du système. Afin d'obtenir un gain de performance décent, un algorithme doit donc minimiser ces transferts.

Les processeurs graphiques ont historiquement été optimisés pour effectuer du calcul en précision simple, suffisante pour les jeux vidéo. Poussés par l'utilisation des GPU en calcul de haute performance, les calculs en double précision sont possibles depuis quelques années, mais sont généralement plus lents que les calculs en simple précision. À titre d'exemple, les cartes graphiques GTX 580 du serveur Hadès réalisent des calculs en double précision à 1/8ième de la vitesse des calculs en simple précision. Par contre, dans la gamme Tesla, les processeurs de la génération Kepler 20 font nettement mieux en effectuant les calculs en double précision jusqu'à 1/3 de la vitesse des calculs en simple précision.

Les processeurs graphiques excellent à effectuer la même opération sur des milliers d'éléments. Ils sont par contre à éviter lorsque l'algorithme requiert beaucoup de branchements conditionnels (if).

Processeurs à plusieurs cœurs intégrés (MIC)

Les processeurs à plusieurs cœurs intégrés sont la réplique d'Intel aux processeurs graphiques. Il s'agit en fait de coprocesseurs, destinés à épauler le processeur central pour les calculs parallèles. Contrairement aux processeurs graphiques, ils peuvent accéder directement à la mémoire centrale. Ils disposent par contre de moins de cœurs de calcul que les GPU. Les récents processeurs Xeon Phi disposent d'environ 60 cœurs de calcul.

Utilisation des architectures massivement parallèles

Plusieurs technologies différentes rivalisent pour permettre l'utilisation des architectures massivement parallèles. Tout d'abord, au niveau des processeurs graphiques, NVidia propose CUDA, qui est le standard de facto en tant qu'API propriétaire. OpenCL se veut une alternative libre à CUDA et supporte aussi des processeurs graphiques qui ne sont pas fabriqués par NVidia, tels que ceux d'ATI. Enfin, OpenACC se propose tranquillement comme nouveau standard afin de simplifier l'utilisation de ces architectures. Dans le même esprit qu'OpenMP, OpenACC permet l'utilisation de processeurs graphiques grâce à l'inclusion de quelques directives pour le précompilateur.

Parallélisme hybride

Le parallélisme hybride consiste à utiliser en même temps plusieurs formes de parallélisme. Par exemple, une partie du code peut être parallélisée en utilisant MPI et une autre partie en utilisant OpenMP. Un exemple typique serait un calcul de type maître-esclave, où l'un des processus distribue le travail à effectuer aux autres processus. Cette distribution pourrait être effectuée entre plusieurs nœuds de calcul, où résident chacun des processus esclaves. Ceux-ci pourraient ensuite faire leur portion de travail en parallèle en utilisant plusieurs fils d'exécution. Il faudrait dans ce cas s'assurer d'indiquer au gestionnaire de tâches mpiexec qu'il doit lancer un seul processus par nœud. D'autres subtilités, telles que la spécification du ou des fils d'exécution qui feront les communications, doivent aussi être considérées, mais elles dépassent la portée de cette introduction. Le même exemple de parallélisme hybride pourrait aussi s'appliquer en utilisant plusieurs processeurs graphiques en parallèle.

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Ressources de Calcul Québec
Outils
Partager