Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leur déploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers.

Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en œuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en œuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en œuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en œuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en œuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.

Les problèmes d'optimisation combinatoire sont souvent des problèmes très difficiles dont la résolution par des méthodes exactes peut s'avérer très longue ou peu réaliste. L'utilisation de méthodes heuristiques permet d'obtenir des solutions de bonne qualité en un temps de résolution raisonnable. Les heuristiques sont aussi très utiles pour le développement de méthodes exactes fondées sur des techniques d'évaluation et de séparation. Nous nous sommes intéressés dans un premier temps à proposer une méthode heuristique pour le problème du sac à dos multiple MKP. L'approche proposée est comparée à l'heuristique MTHM et au solveur CPLEX. Dans un deuxième temps nous présentons la mise en oeuvre parallèle d'une méthode exacte de résolution de problèmes d'optimisation combinatoire de type sac à dos sur architecture GPU. La mise en oeuvre CPU-GPU de la méthode de Branch and Bound pour la résolution de problèmes de sac à dos a montré une accélération de 51 sur une carte graphique Nvidia Tesla C2050. Nous présentons aussi une mise en oeuvre CPU-GPU de la méthode du Simplexe pour la résolution de problèmes de programmation linéaire. Cette dernière offre une accélération de 12.7 sur une carte graphique Nvidia Tesla C2050. Enfin, nous proposons une mise en oeuvre multi-GPU de l'algorithme du Simplexe, mettant à contribution plusieurs cartes graphiques présentes dans une même machine (2 cartes Nvidia Tesla C2050 dans notre cas). Outre l'accélération obtenue par rapport à la mise en oeuvre séquentielle de la méthode du Simplexe, une efficacité de 96.5 % est obtenue, en passant d'une carte à deux cartes graphiques.

La méthode PIC MCC (Particle-In-Cell Monte-Carlo Collision) est un outils très performant et efficace en ce qui concerne l'étude des plasmas (dans notre cas, pour des plasmas froids) car il permet de décrire l'évolution dans le temps et dans l'espace, des particules chargées sous l'effet des champs auto-consistants et des collisions. Dans un cas purement électrostatique, la méthode consiste à suivre les trajectoires d'un nombre représentatif de particules chargées, des électrons et des ions, dans l'espace des phases, et de décrire l'interaction collective de ces particules par la résolution de l'équation de Poisson. Dans le cas de plasmas froid, les trajectoires dans l'espace des phase sont déterminées par le champ électrique auto-consistant et par les collisions avec les atomes neutres ou les molécules et, pour des densités relativement importantes, par les collisions entre les particules chargées. Le coût des simulations pour ce type de méthode est très élevé en termes de ressources (CPU et mémoire). Ceci est dû aux fortes contraintes (dans les simulations PIC explicites) sur le pas de temps (plus petit qu'une fraction de la période plasma et inverse à la fréquence de giration électronique), sur le pas d'espace (de l'ordre de la longueur de Debye), et sur le nombre de particules par longueur de Debye dans la simulation (généralement de l'ordre de plusieurs dizaines). L'algorithme PIC MCC peut être parallélisé sur des fermes de calculs de CPU (le traitement de la trajectoires des particules est facilement parallélisable, mais la parallélisation de Poisson l'est beaucoup moins). L'émergence du GPGPU (General Purpose on Graphics Processing Unit) dans la recherche en informatique a ouvert la voie aux simulations massivement parallèle à faible coût et ceci par l'utilisation d'un très grand nombre de processeurs disponible sur les cartes graphiques permettant d'effectuer des opérations élémentaires (e.g. calcul de la trajectoires des particules) en parallèle. Un certain nombre d'outils numérique pour le calcul sur GPU ont été développés lors de ces 10 dernières années. De plus, le constructeur de cartes graphiques NVIDIA a développé un environnement de programmation appelé CUDA (Compute Unified Device Architecture) qui permet une parallélisation efficace des codes sur GPU. La simulation PIC avec l'utilisation des cartes graphiques ou de la combinaison des GPU et des CPU a été reporté par plusieurs auteurs, cependant les modèles PIC avec les collisions Monte-Carlo sur GPU sont encore en pleine étude. A l'heure actuelle, de ce que nous pouvons savoir, ce travail est le premier a montrer des résultats d'un code PIC MCC 2D et 3D entièrement parallélisé sur GPU et dans le cas de l'étude de plasma froid magnétisé. Dans les simulation PIC, il est relativement facile de suivre les particules lorsqu'il n'y a ni pertes ni création (e.g. limites périodiques ou pas d'ionisation) de particules au cours du temps. Cependant il devient nécessaire de réordonner les particules à chaque pas en temps dans le cas contraire (ionisation, recombinaison, absorption, etc). Cette Thèse met en lumière les stratégies qui peuvent être utilisées dans les modèles PIC MCC sur GPU permettant d'outre passer les difficultés rencontrées lors du réarrangement des particules après chaque pas de temps lors de la création et/ou des pertes. L'intérêt principal de ce travail est de proposer un algorithme implémenté sur GPU du modèle PIC MCC, de mesurer l'efficacité de celui-ci (parallélisation) et de le comparer avec les calculs effectués sur GPU et enfin d'illustrer les résultats de ce modèle par la simulation de plasma froid magnétisé. L'objectif est de présenter en détail le code utilisé en de montrer les contraintes et les avantages liées à la programmation de code PIC MCC sur GPU. La discussion est largement ciblé sur le cas en 2D, cependant un algorithme 3D a également été développé et testé comme il est montré à la fin de cette thèse.

Dans cette thèse, nous présentons notre travail de recherche dans le domaine du calcul haute performance en mécanique des fluides. Avec la demande croissante de simulations à haute résolution, il est devenu important de développer des solveurs numériques pouvant tirer parti des architectures récentes comprenant des processeurs multi-cœurs et des accélérateurs. Nous nous proposons dans cette thèse de développer un solveur efficace pour la résolution sur architectures hétérogènes CPU/GPU des équations de Navier-Stokes (NS) relatives aux écoulements 3D de fluides incompressibles.Tout d'abord nous présentons un aperçu de la mécanique des fluides avec les équations de NS pour fluides incompressibles et nous présentons les méthodes numériques existantes. Nous décrivons ensuite le modèle mathématique, et la méthode numérique choisie qui repose sur une technique de prédiction-projection incrémentale.Nous obtenons une distribution équilibrée de la charge de calcul en utilisant une méthode de décomposition de domaines. Une parallélisation à deux niveaux combinée avec de la vectorisation SIMD est utilisée dans notre implémentation pour exploiter au mieux les capacités des machines multi-cœurs. Des expérimentations numériques sur différentes architectures parallèles montrent que notre solveur NS obtient des performances satisfaisantes et un bon passage à l'échelle.Pour améliorer encore la performance de notre solveur NS, nous intégrons le calcul sur GPU pour accélérer les tâches les plus coûteuses en temps de calcul. Le solveur qui en résulte peut être configuré et exécuté sur diverses architectures hétérogènes en spécifiant le nombre de processus MPI, de threads, et de GPUs.Nous incluons également dans ce manuscrit des résultats de simulations numériques pour des benchmarks conçus à partir de cas tests physiques réels. Les résultats obtenus par notre solveur sont comparés avec des résultats de référence. Notre solveur a vocation à être intégré dans une future bibliothèque de mécanique des fluides pour le calcul sur architectures parallèles CPU/GPU. / In this PhD thesis, we present our research in the domain of high performance software for computational fluid dynamics (CFD). With the increasing demand of high-resolution simulations, there is a need of numerical solvers that can fully take advantage of current manycore accelerated parallel architectures. In this thesis we focus more specifically on developing an efficient parallel solver for 3D incompressible Navier-Stokes (NS) equations on heterogeneous CPU/GPU architectures. We first present an overview of the CFD domain along with the NS equations for incompressible fluid flows and existing numerical methods. We describe the mathematical model and the numerical method that we chose, based on an incremental prediction-projection method.A balanced distribution of the computational workload is obtained by using a domain decomposition method. A two-level parallelization combined with SIMD vectorization is used in our implementation to take advantage of the current distributed multicore machines. Numerical experiments on various parallel architectures show that this solver provides satisfying performance and good scalability.In order to further improve the performance of the NS solver, we integrate GPU computing to accelerate the most time-consuming tasks. The resulting solver can be configured for running on various heterogeneous architectures by specifying explicitly the numbers of MPI processes, threads and GPUs. This thesis manuscript also includes simulation results for two benchmarks designed from real physical cases. The computed solutions are compared with existing reference results. The code developed in this work will be the base for a future CFD library for parallel CPU/GPU computations.