Compilation pour machines à mémoire répartie

Différents paradigmes de parallélisme

   La taxonomie de Flynn [36] est une classification des architectures parallèles datant des année 70. Elle porte sur le flux d’instructions (I), exécution du code, et le flux de données (D), flot de données. Ils peuvent être uniques (S, single) ou multiples (M). Quatre cas sont possibles :
SISD (Single Instruction Stream, Single Data Stream). Une machine “séquentielle” qui exécute une instruction à la fois sur une donnée unique. Bien qu’étant soit disant séquentielle, elle permet dans une moindre mesure de faire du parallélisme. En effet, les instructions pipelinées sont considérées comme faisant partie de cette catégorie. Elle correspond à une machine de type Von Neumann [74]. Ces machines standards des années 70 sont rares de nos jours.
SIMD (Single Instruction Stream, Multiple Data Streams). Une machine où chaque instruction peut traiter plusieurs données simultanément. Les machines vectorielles en sont la parfaite illustration. Les applications utilisant beaucoup de tableaux ou de matrices, par exemple le traitement de signal ou d’image, tirent pleinement partie d’une telle architecture. De nos jours, quasiment toutes les machines possèdent un processeur vectoriel avec des jeux d’instructions vectorielles telles que le MMX, SSE ou encore AVX. La section 1.1.1 donne de plus amples explications.
MISD (Multiple Instruction Streams, Single Data Stream). Une machine qui, pour une donnée, exécute simultanément plusieurs instructions. Elles sont souvent spécifiques à un domaine d’application. Les machines systoliques font partie de cette classe.
MIMD (Multiple Instruction Streams, Multiple Data Streams). Une machine qui exécute simultanément plusieurs instructions sur plusieurs données différentes. C’est le type de machines parallèles le plus répandu. Par exemple, les architectures Very Long Instruction Word VLIW permettent d’exécuter plusieurs instructions différentes sur plusieurs données différentes. VLIW a inspiré l’architecture EPIC, Explicitly Parallel Instruction Computing, qui est décrite à la section 1.1.2. La Figure 1.1(d) représente une architecture MIMD. Le modèle MIMD est souvent décomposé en divers sous-catégories pouvant ou non se superposer. Par exemple, une sous-catégorie est la séparation entre le SPMD (Single Program Multiple Data) et le MPMD (Multiple Program Multiple Data), une autre est la séparation entre mémoire partagée, distribuée et hybride dont nous parlerons par la suite. Cette catégorie de machines tend à devenir la machine standard avec des processeurs possédant 2, 4, 8 voire 16 cœurs. Concernant la catégorisation des programmes parallèles, les modèles SPMD et MPMD, sous-catégories du MIMD, sont souvent utilisés. Le SPMD regroupe principalement les programmes scientifiques alors que le MPMD correspond plutôt à des programmes clients-serveurs que l’on trouve sur internet.

POSIX

   POSIX, Portable Operating System Interface, est un standard IEEE, IEEE 1003 qui comporte plusieurs versions. Il est aussi connu sous la référence ISO/IEC9945 [53]. Il a entre autres standardisé l’utilisation de thread, aussi appelé “fil d’exécution” ou “processus léger”. On parle de POSIX threads, ou plus couramment pthreads. POSIX utilise principalement le paradigme fork/join, Figure 1.5. Ce paradigme crée plusieurs processus légers, au moyen de la fonction pthread_create, qui vont s’exécuter simultanément. Ces processus attendent ensuite que tous les pthreads finissent leur exécution pour se rejoindre lors de l’appel à la fonction pthread_join. Ces deux fonctions s’appliquent sur des variables de type pthread_t. Pour gérer les problèmes d’accès concurrents, on peut utiliser des mutex, pour mutual exclusion ou exclusion mutuelle. Le principe consiste à mettre en place un verrou sur l’exécution d’une partie d’un code, pour que celle-ci ne puisse être exécutée que par un seul et unique thread en même temps. Cette partie de code doit donc être la plus courte possible pour garder le maximum de parallélisme. Les exclusions mutuelles sont principalement utilisées lors de la mise à jour d’une variable qui pourrait être modifiée par plusieurs thread. La bibliothèque POSIX utilise les fonctions pthread_mutex_lock et pthread_mutex_unlock sur des variables de type pthread_mutex_t. POSIX est une bibliothèque relativement lourde à utiliser car le programmeur doit tout gérer, aussi bien la création que l’affectation ou la fermeture des thread. C’est une bibliothèque très bas niveau qui est peu utilisée dans les développements effectifs de programmes car elle demande beaucoup d’effort aussi bien pour adapter le code que pour obtenir des résultats et des performances corrects.

PVM

   PVM, Parallel Virtual Machine [91], est une bibliothèque de parallélisation des calculs pour des machines hétérogènes, aussi bien pour des ordinateurs standards que pour des super-calculateurs. Le projet a été initié en 1989 par l’Oak Ridge National Laboratory (ORNL) aux USA [39][96]. Sa dernière version est la version 3.4.6 publiée en 2009. PVM possède une implémentation pour C, C++ et Fortran. PVM fonctionne en mode maître/esclaves. Ainsi, il doit toujours y avoir un des programmes qui est le maître. Son fonctionnement implique que différents programmes puissent tourner simultanément sur différentes machines. PVM se classifie donc comme MPMD. Pour fonctionner, des daemon PVM (pvmd) doivent tourner sur toutes les machines exécutant des programmes PVM. Ces daemon sont chargés d’effectuer les communications et le routage entre les différentes machines. Le programme maître en PVM commence toujours par un appel à pvm_tid. Tous les programmes PVM finissent par un appel à pvm_exit. Le maître peut lancer plusieurs esclaves exécutant une tâche grâce à la fonction pvm_spawn. Ces derniers connaissent l’identité de leur maître avec la fonction pvm_parent. Les messages envoyés sont toujours non bloquants et utilisent un tampon, buffer, à initialiser (pvm_initsend), puis à remplir (pvm_pkint) avant de faire l’envoi (pvm_send). La réception peut être bloquante ou non. Elle se fait au moyen de la fonction pvm_recv et les données doivent être extraites avec pvm_upkint dans le même ordre que le remplissage.

CUDA

   Le langage CUDA, Compute Unified Device Architecture [77], est développé par NVidia. Il est actuellement le leader pour la programmation sur GPGPU. Mais, il est propriétaire et ne peut s’exécuter que sur des GPU de NVidia. CUDA possède un compilateur spécifique pour ces programmes, nvcc. De plus, de nombreuses bibliothèques de programmation très performantes existent dont notamment cuBLAS [79] pour l’algèbre linéaire et cuSPARSE [80] pour les opérations sur les vecteurs et matrices creuses. De même, plusieurs outils de débogage et de profilage sont fournis par NVidia pour aider les programmeurs à optimiser leur code [78]. CUDA utilise la terminologie de grille pour parler d’une exécution sur le GPGPU. Une grille est composée d’une mémoire qui est appelée mémoire globale et d’un ensemble de blocs. Un bloc est lui-même composé d’une mémoire appelée mémoire partagée et d’un ensemble de threads. Les fonctions CUDA s’écrivent comme des fonctions C classiques. Pour différentier l’architecture sur laquelle s’exécutent les fonctions, des qualificatifs peuvent être ajoutés à leur déclaration. __global__ indique que la fonction est exécutée sur le GPGPU, le device, mais doit être appelée depuis l’hôte, l’host. Il correspond au noyau, kernel, a exécuté sur le GPGPU. __device__ est utilisé quand la fonction est exécutée et appelée depuis le device. __host__, pour une exécution et appel depuis l’host, est le qualificatif par défaut. De plus, les appels de noyaux depuis l’hôte doivent être accompagnés d’une configuration définie avec des triples chevrons ≪Dg, Db≫. Dg décrit la grille de calcul sur laquelle le noyaux va s’exécuter en indiquant le nombre de blocs présents sur la grille en 1D, 2D voire 3D. Db décrit chaque bloc présent dans la grille en indiquant le nombre de fils d’exécution, thread, à exécuter en 1D, 2D voire 3D. Les variables présentes sur le GPGPU peuvent se trouver sur différents types de mémoire. Les variables en paramètre peuvent être sur la mémoire globale ou constante du GPGPU avec les qualificatifs respectifs __device__ et __constant__. Les variables déclarées au sein d’une fonction sont par défaut mises en registre si possible, sinon elles se retrouvent dans la mémoire globale du GPGPU, le temps de son exécution. Le qualificatif __shared__ peut être utilisé pour utiliser la mémoire au niveau des blocs qui est beaucoup plus rapide que la mémoire globale du GPGPU. Dépendantes du placement en mémoire choisi, les performances ne sont pas les mêmes. Un accès à une variable en __shared__ est plus rapide qu’un accès pour une variable en __device__. La gestion de la mémoire du GPGPU s’effectue à l’aide des fonctions cudaMalloc, cudaFree. Les transferts de données entre CPU et GPGPU se font avec la fonction cudaMemcpy

Table des matières

Introduction
1 Les modèles de programmation parallèle 
1.1 Différents paradigmes de parallélisme 
1.2 Le modèle à mémoire partagée 
1.3 Le modèle à mémoire distribuée 
1.4 Le modèle PGAS 
1.5 Les GPGPU et les accélérateurs 
1.6 Conclusion 
2 La distribution automatique de tâches 
2.1 La problématique de parallélisation de tâches sur architecture à mémoire distribuée 
2.2 L’état de l’art 
2.3 Les différentes possibilités
2.4 La méthodologie utilisée 
2.5 Les méthodes de modélisation des communications
2.6 Conclusion
3 Transformations successives du code 
3.1 La syntaxe et la sémantique du code 
3.2 La détection et le placement des différentes tâches 
3.3 La préparation du code séquentiel 
3.4 Les optimisations de code 
3.5 La génération automatique du code parallèle 
3.6 Conclusion
4 Preuves de correction des transformations 
4.1 Les preuves sur la préparation du code
4.2 La preuve sur l’optimisation de code
4.3 Les preuves sur le code parallèle généré
4.4 Conclusion 
5 Optimisation du processus de compilation 
5.1 Effects Dependence Graph 
5.2 L’amélioration de la cohérence mémoire 
5.3 L’optimisation des bornes de boucles
5.4 L’optimisation des dimensions de tableau
5.5 La génération de code MPI
5.6 Conclusion 
6 Expériences et interprétations 
6.1 La configuration matérielle 
6.2 Polybench 
6.3 Méthodologie d’expérimentation 
6.4 De l’algèbre linéaire
6.5 De l’exploration de données
6.6 Du traitement d’image
6.7 Synthèse des résultats obtenus 
6.8 Conclusion 
Conclusion
A Description et fonctionnement de PIPS
B Résultats détaillés des expériences
B.1 Algèbre linéaire
B.2 Exploration de données
B.3 Traitement d’image
Bibliographie personnelle
Références

Télécharger le rapport complet