Introduction à la Programmation Parallèle PDF 2020-2021

Univ D. Liabes De Sidi Bel Abbes 2ème Année Master RSSI Faculté des Sciences Exactes Cours de Programmation Parallèle Département d’informatique Année 2020 2021 Chapitre I : Introductio...

Univ D. Liabes De Sidi Bel Abbes 2ème Année Master RSSI Faculté des Sciences Exactes Cours de Programmation Parallèle Département d’informatique Année 2020 2021 Chapitre I : Introduction à la programmation parallèle I. Introduction La première architecture d'ordinateur (Von Neumann) offrait un seul flux de contrôle exécutant les opérations séquentiellement. Des chercheurs voulurent booster les capacités de calcul des ordinateurs pour satisfaire la demande importante des nouvelles applications informatiques qui touchent tous les secteurs. L'apparition des ordinateurs parallèles numériques remontent à la fin des années 1950. A cette époque, l'industrie avait déjà développé un certain nombre de machines séquentielles et les ingénieurs se sont intéressés à l'utilisation du parallélisme dans les calculs numériques. Par conséquent, au cours des années 1960 et les années 1970, plusieurs systèmes à mémoire partagée "multiprocesseurs" ont été conçus à des fins académiques et commerciales. De tels systèmes se composaient d'un petit nombre de processeurs (1 à 4) connectés à un petit nombre de modules de mémoire (1 à 16) par l'intermédiaire d'un commutateur. Les processeurs fonctionnaient côte à côte sur les données partagées. Les progrès réalisés dans la technologie des circuits intégrés et les idées des architectes célèbres de ce domaine ont contribué à l'évolution des supercalculateurs. Au début des années 1980, le supercalculateur Cray X-MP pouvait effectuer plus de 200 millions d'opérations par seconde (MFLOPS). Au milieu des années 1980, des processeurs massivement parallèles ont été mis au point en reliant une masse importante de microprocesseurs. Le Red MPP ASCI était la première machine ayant une performance au dessus de 1 Tera-FLOPS en 1996 en utilisant plus de 4000 nœuds de calcul disposés en une grille. Les années 1990 ont également vu l'évolution des clusters d'ordinateurs qui sont semblables aux machines massivement parallèles. Les chercheurs de ce domaine s'intéressaient essentiellement à deux points: le temps requis à la réalisation des opérations demandées, c'est ce qu'on appel la 1 latence de traitement, et le deuxième point est le nombre de tâches à réaliser par unité de traitement autrement dit: le débit de traitement. II. Domaine d’utilisation Le traitement parallèle fait référence à l'accélération d'une tâche de calcul en la divisant en tâches plus petites sur plusieurs processeurs. Les applications du traitement parallèle (également connu sous le nom de calcul parallèle) incluent l'astrophysique, le géotraitement (ou levés sismiques), la modélisation du climat, les estimations agricoles, la gestion des risques financiers, la correction des couleurs vidéo, la dynamique des fluides, l'imagerie médicale et la découverte de médicaments.  Lorsque vous activez une application météo sur votre téléphone pour consulter les prévisions du jour, remerciez le traitement en parallèle. Le résultat obtenu n’est pas parce que votre téléphone exécute plusieurs applications (Multitâche) ; donc le calcul parallèle ne doit pas être confondu avec le calcul simultané, mais parce que les cartes des modèles climatiques et météorologiques nécessitent de sérieux calcul du parallèle qui vont être faits sur des serveurs. Figure 1. Modélisation météorologique.  Lorsque vous regardez un film, vous allez admirer forcément les effets spéciaux qui le rendent impressionnant. Là aussi, on fait appel au programmes parallèles qui génèrent des séquences d’animation (Figure 2), ou encore plus impressionnant : des algorithmes de reconnaissance de mouvements pour la génération de personnage de synthèse. 2  Figure 2. Création d’animation et génération d’image de synthèse  L’industrie automobile, aéronautique et beaucoup d’autre aussi utilisent des outils de conception et de modélisation puissants qui demandent une force d’exécution assurée par les architectures parallèles à fin de tester, de prédire, et de valoriser la gravité de craches des véhicules. Le calcul de la résistance des matériaux pour les ailes des avions est un autre bon exemple puisque y a plusieurs paramètres qui rentrent en jeu : Pression atmosphérique, poids, turbulences…… Figure 3. Simulation de craches de voitures III. Puissance de calcul Depuis les années 1960, la densité des transistors dans un microprocesseur double tous les 18 à 24 mois, cette observation est appelée la loi de Moore. En dépit de problèmes de consommation énergétique, la loi de Moore est toujours valable en 2020. Les transistors supplémentaires, toujours plus petits, permettent de créer plusieurs unités de calcul, appelé cœurs, au sein du même processeur. Toutefois, au fil des années, il est devenu de plus en plus difficile de suivre le rythme dicté par la loi de Moore - d'ailleurs à plusieurs reprises déjà reformulée. Il est désormais plus 3 coûteux et techniquement plus complexe de doubler tous les deux ans le nombre de transistors - et en retour, la puissance de traitement. "La loi de Moore avait l'habitude de croître à x10 tous les cinq ans [et] x100 tous les 10 ans" note Huang. "En ce moment, la loi de Moore augmente de quelques pourcents chaque année. Tous les 10 ans peut-être seulement x2". Notations : Floating-point operations per second: Opérations en virgule flottante par seconde. Mesure de la vitesse d'un processeur ou d'une des unités de calcul arithmétique d'un processeur. Une opération en virgule flottante manipule des nombres décimaux à virgule, codés sur un certain nombre de bits. Cette unité est mieux représentative de la puissance de calcul d'un processeur que sa fréquence (exprimée en hertz, Hz) ou encore que le nombre d'instructions par seconde qu'il est capable d'exécuter (Mips, millions of instructions per second). Un préfixe indique toujours une quantité : mégaflops (106 flops), gigaflops (109), téraflops (1012)... Les puissances des processeurs actuels se mesurent en général en gigaflops. Autrement dit : Les multiplicatifs : Kilo = 2^10 ; Mega = 2^20 ; Giga = 2^30. Figure 4. La loi de moore 4 IV. Matériels pour le parallélisme Nous somme attirés maintenant vers ce paradigme de programmation qui semble incontournable lorsqu’on souhaite faire une exécution en temps réel ou dans le cas où notre programme traite énormément de données. Cependant, y a-t-il une différence entre le « Hardware » dédié pour une exécution séquentielle et une exécution parallèle ?????? La réponse est oui. Un matériel doté d’une seule UAL ne peut effectuer des taches en parallèle, il ne faut pas confondre avec le principe d’un système d’exploitation multitâche comme le (Windows, Linux …) car ces derniers simulent que deux ou plusieurs applications s’exécutent simultanément, mais en réalité, l’OS les exécute en alternance avec une fréquence très élevée au point que l’humain ne peut l’apercevoir. Alors !! Quel matériel je peux choisir ? a) PC ou station homogène : Commençant par ce qui est à notre porté : De nos jours, les processeurs sont multi-coeurs, c-à-d que le processeur est divisé réellement en plusieurs UALs, on peut remarquer sur le gestionnaire de taches de notre PC (Figure 5) l’existence de plusieurs graphique montrant la performance et l’utilisation de chacun, cette exemple illustre un processeur I7 ancienne génération de 4 cœurs; les nouvelles générations sont équipées de 8 cœurs. Figure 5. Graphique sur les performances d’un processeur i7 5 La figure 6 représente les performances d’une station de calculs plus performante avec un processeur à 12 cœurs. Dance ce cas, on peut diviser une tache globale sur 4 taches (pour le I7) ou 12 taches (pour le xeon) pour une exécution parallèle à condition de ne pas avoir une dépendance de données (qu’on va détailler dans le prochain chapitre), car on ne peut pas paralléliser n’importe quel algorithme. Figure 6. Graphique sur les performances d’un processeur xeon. b) Cluster Un cluster d'ordinateurs est un ensemble d'ordinateurs faiblement ou étroitement connectés qui fonctionnent ensemble de sorte que, sous de nombreux aspects, ils peuvent être considérés comme un système unique. Contrairement aux ordinateurs en grille, les clusters d'ordinateurs ont chaque nœud configuré pour effectuer la même tâche, contrôlée et planifiée par un logiciel. Les composants d'un cluster sont généralement connectés les uns aux autres via des réseaux locaux (LAN), chaque nœud (ordinateur utilisé comme serveur) exécutant sa propre instance d'un système d'exploitation. Dans la plupart des cas, tous les nœuds utilisent le même matériel et le même système d'exploitation, bien que dans certaines configurations (Open Source Cluster Application Resources (OSCAR)), différents systèmes d'exploitation peuvent être utilisés sur chaque ordinateur ou matériel différent. Les clusters sont généralement déployés pour améliorer les performances et la disponibilité par rapport à celles d'un seul 6 ordinateur, tout en étant généralement beaucoup plus rentables que des ordinateurs isolés de vitesse ou de disponibilité comparables. Les clusters ont émergé à la suite de la convergence d'un certain nombre de tendances informatiques, y compris la disponibilité de microprocesseurs à bas prix, de réseaux à haut débit et de logiciels pour le calcul distribué haute performance. Ils ont un large éventail d'applicabilité et de déploiement , allant des grappes de petites entreprises avec une poignée de nœuds à certains des supercalculateurs les plus rapides au monde tels que Sequoia d'IBM Figure 7. Photo d’un cluster La figure 8 illustre la puissance des plus rapides clusters construit jusqu’à 2017. On remarque clairement que leurs performances dépassent 1 million de Tflops, ce qui est vraiment impressionnant. 7  Figure 8. Top 5 des clusters en 2017 c) Le HPC: Le HPC ou Calcul Haute Performance (High Performance Computing ) consiste a combiner la puissance de plusieurs milliers de processeurs pour effectuer des calculs complexes et des traitements de données massives en temps réel. Le plus puissant HPC est construit par IBM et coute 240 millions de dollars. Il a une puissance de calcul de 200 péta Flops et constitué de 4608 nœuds. Chaque nœud est doté d’un processeur (2 IBM Power 9), d’une carte graphique Tesla V100 et d’une mémoire vive de 608 GB. Figure 9. Photo du HPC « summit » d’IBM 8  d) Les Cartes graphiques: Ce matériel est intéressant pour nous, vu sa large disponibilité et son cout faible relativement aux autres équipements. GPU (Graphics Processing Unit ) sont des unités de calculs massivement parallèles (milliers de processeurs). Ces processeurs sont dotés d’une mémoire de très petite taille, ce qui peut être un handicap dans un cadre général, mais qui ne gêne pas dans le cas spécifique de calculs mathématiques comme la résolution de systèmes linéaires. Un processeur graphique, ou GPU (Graphics Processing Unit), est un circuit intégré présent la plupart du temps sur une carte graphique mais il se trouve de plus en plus intégré au chipset des cartes mères, et assurant les fonctions de calcul de l'affichage. Un processeur graphique a généralement une structure hautement parallèle qui le rend efficace pour une large palette de tâches graphiques comme le rendu 3D. La figure 10 illustre la puissance des GPUs ainsi que leur évolution. Figure 10. Evolution de la puissance des GPUs. 9 Remarque: Il est noté que les GPUs sont intégrées via le slot PCI dans une carte mère d’un simple ordinateur ou d’une station de travail. Ceci rend le matériel hétérogène. Un matériel est dit hétérogène s’il comporte d’autre unité de traitement supplémentaire comme : une GPU, Un TPU (Tensor Processing unit), un VPU (Vision Processing Unit) ou une FPGA (Field Programmable Gate Arrays). V. Langages et techniques de programmation parallèle Nous introduisons dans cette partie les outils de programmation parallèle. Parmi ces outils, il y a ceux qui permettent l’échange de données entre les nœuds d’exécution comme invoqué lors de la définition d’un cluster un plus haut ; comme il y a ceux qui permettent une exécution parallèle sur un équipement dont l’architecture est massivement parallèle. a) MPI Le MPI (Message Passing Interface) est développé en 1994 pour normaliser les messages entre les nœuds. La norme MPI (Message Passing Interface Standard) est une norme de bibliothèque de transmission de messages basée sur le consensus du MPI Forum, qui compte plus de 40 organisations participantes, y compris des fournisseurs, des chercheurs, des développeurs de bibliothèques de logiciels et des utilisateurs. L'objectif du MPI est d'établir une norme portable, efficace et flexible pour la transmission de messages qui sera largement utilisée pour écrire des programmes de transmission de messages. Elle est devenue de facto un standard de communication pour des nœuds exécutant des programmes parallèles sur des systèmes à mémoire distribuée. En tant que tel, MPI est la première bibliothèque de transmission de messages normalisée, indépendante du fournisseur. Les avantages du développement de logiciels de transmission de messages à l'aide de MPI correspondent étroitement aux objectifs de conception de portabilité, d'efficacité et de flexibilité. MPI n'est pas une norme IEEE ou ISO, mais est en fait devenu le «standard de l'industrie» pour l'écriture de programmes de transmission de messages sur les plates-formes HPC. b) OpenMP OpenMP (Open MultiProcessing) est un modèle de programmation parallèle basé sur des directives de compilateur qui permet aux développeurs d'applications d'ajouter de manière incrémentielle du parallélisme à leurs codes d'application. La spécification d'API OpenMP 10 pour la programmation parallèle fournit une interface de programmation d'application (API) qui prend en charge la programmation multiprocesseur multi-plateforme à mémoire partagée en C, C ++ et Fortran, sur la plupart des plates-formes. Il se compose d'un ensemble de directives de compilateur, de routines de bibliothèque et de variables d'environnement qui influencent le comportement d'exécution. Étant donné qu'OpenMP se concentre sur le parallélisme au sein d'un nœud (multitraitement à mémoire partagée), il peut être combiné avec des modèles de programmation de transmission de messages, tels que MPI, pour s'exécuter sur plusieurs nœuds. c) Intel TBB Intel® Threading Building Blocks (Intel® TBB) est un modèle de programmation parallèle basé sur l'exécution pour le code C ++ qui utilise des threads. Il se compose d'une bibliothèque d'exécution basée sur des modèles pour nous aider à exploiter les performances latentes des processeurs multicœurs. On utilise Intel TBB pour écrire des applications évolutives qui: Spécifie une structure parallèle logique au lieu de threads, accentuer la programmation parallèle des données et Tirer parti des collections simultanées et des algorithmes parallèles d) OpenCl Signifie "Open Computing Language". OpenCL est un standard ouvert pour la programmation parallèle multiplateforme. Il a été initialement développé par Apple en 2008 et est maintenant maintenu par le groupe Khronos. Le premier système d'exploitation majeur à prendre en charge OpenCL était Snow Leopard (Mac OS X 10.6), sorti en 2009. OpenCL fournit une API qui permet aux programmes logiciels d'accéder simultanément à plusieurs processeurs pour effectuer un traitement parallèle ; par exemple : il inclue les CPU, les GPU, les « digital signal processors » (DSP) et les « field-programmable gate arrays « (FPGA). En répartissant la charge de calcul sur plusieurs processeurs, OpenCL augmente l'efficacité du traitement et peut considérablement améliorer les performances d'un programme. Bien qu'OpenCL prenne en charge de nombreux types de processeurs différents, il est notamment utilisé pour accéder au GPU pour des tâches informatiques générales. Cette technique, également appelée GPGPU, tire parti de la puissance de traitement du GPU et lui permet d'assister le CPU dans la réalisation des calculs. Avant OpenCL, le processeur graphique restait souvent inactif pendant que le processeur fonctionnait à pleine capacité. OpenCL permet au GPU d'assister le CPU dans le traitement des calculs non liés aux graphiques. 11  e) CUDA CUDA est une architecture pour GPU développée par NVIDIA qui a été introduite le 23 juin 2007. Le nom «CUDA» était à l'origine un acronyme pour «Compute Unified Device Architecture». CUDA améliore les performances des tâches de calcul qui bénéficient du traitement parallèle. Ces charges de travail, telles que le traitemnt d'images 3D en temps réel, sont souvent qualifiées de «parallèles embarrassantes» car elles se prêtent naturellement à être calculées par des cœurs individuels. Les GPU CUDA comportent un grand nombre de ces cœurs CUDA, qui peuvent se compter par milliers, intégrés sur une seule carte vidéo. Le logiciel doit être écrit spécifiquement pour l'architecture à l'aide de bibliothèques et d'API CUDA de bas niveau, fournies par NVIDIA. Le langage de programmation natif de ces bibliothèques est C++. VI. Conclusion Dans ce chapitre nous avons introduit le paradigme de la programmation parallèle, ses domaines d’application ainsi que les outils pour une réalisation réelle. Le chapitre suivant détaille les architectures parallèles et leur classification. Par la suite, nous mettrons en pratique une implémentation avec le MPI pour une accélération de programme de calculs matriciels (Somme et produit). Cependant, puisque de nos jours la programmation GPGPU est fortement demandée, il est plus que nécessaire d’aborder la programmation muti-threads avec les cartes graphiques. Références https://www.intel.fr/content/www/fr/fr/it-managers/moores-law-evolution.html https://computing.llnl.gov/tutorials/mpi/ https://www.openmp.org/resources/refguides/ https://software.intel.com/content/www/us/en/develop/documentation/tbb- tutorial/top.html https://www.khronos.org/registry/OpenCL/sdk/2.2/docs/man/html/ https://docs.nvidia.com/cuda/ 12