Conception et analyse d’algorithmes parallèles en temps pour l’accélération de simulations numériques d’équations d’évolution
Calcul intensif, décomposition et parallélisation des tâches
Durant les dernières décennies, les mathématiques appliquées et le calcul scientifique en particulier, ont connu un développement important et sont maintenant des outils usuels aussi bien dans les communautés (non mathématiques) d’application que dans le monde industriel. Le calcul scientifique, discipline regroupant la modélisation, l’analyse numérique et la simulation, est en évolution croissante vers des applications scientifiques très avancées ou proprement ingénieuses. On trouve de multiples champs disciplinaires d’application se servant intensivement du calcul scientifique. On peut citer la biologie, l’astrophysique, la chimie quantique, la météorologie ou encore des branches de l’industrie telles que l’énergie, l’automobile ou l’aéronautique. Les modèles mathématiques utilisés dans ces divers domaines d’applications sont souvent très complexes et font intervenir un grand nombre de paramètres lors de leurs formulations mathématiques. La simulation numérique de ces problèmes a pour objectif principal d’approcher le mieux possible le comportement physique du problème à travers des modèles discrétisés. Ces derniers forment des systèmes matriciels d’autant plus grands que le problème est complexe et que la précision demandée lors du traitement est importante. Dans la majorité des simulations sur ordinateurs ordinaires, on ne parvient pas à résoudre des problèmes complexes en des temps raisonnables. On risque même de saturer ce type de machines par la simple demande de traitement des données qui nécessitent l’occupation d’une très grande place mémoire ! Avec les demandes actuelles, les machines ordinaires sont surexploitées dans la plus part des domaines d’applications du calcul scientifique. Elles montrent leurs limites malgré le développement et l’évolution de leurs vitesses très élevées de résolution qui se mesurent en flops 1 . Ce recours massif à l’informatique impose de disposer d’ordinateurs très puissants qui offrent un accès à une importante mémoire vive de stockage temporel lors de l’assimilation des données. Les ordinateurs parallèles, également appelés superordinateurs, disposent de la puissance et de l’espace mémoire nécessaires à certaines applications complexes. Ils offrent donc aux scientifiques un nouvel outil de calcul, avec des possibilités et avantages très largement supérieurs à ceux des ordinateurs conventionnels. Cependant, les algorithmes implémentés sur les ordinateurs parallèles, sont nettement différents de ceux que l’on met en œuvre sur des machines ordinaires séquentielles (uni-processeurs). Pour ces raisons, et sans parler des contraintes économiques et techniques, les scientifiques et notamment les numériciens, sont invités à développer des algorithmes (parallèles) s’adaptant à ce type de nouveaux calculateurs massivement parallèles. Les algorithmes doivent privilégier l’accès simultané à plusieurs processeurs et aussi à plus de ressources mémoires. Les méthodes développées à ce titre sont nombreuses. Elles sont principalement basées sur 1. Nombre d’opérations arithmétiques par seconde. 2 la notion de subdivision des tâches que l’on alloue à chacun des processeurs disponibles de la machine parallèle. C’est ainsi que l’efficacité des algorithmes parallèles est fortement liée au degré d’indépendance de chaque subdivision relativement aux autres. Il est préférable que la dépendance soit faible. En effet, ceci réduit les communications inter-processeurs qui peuvent être lourdes sur certaines architectures parallèles, notamment celles qui utilisent un réseau Ethernet. Au niveau de la conception de l’algorithme parallèle, une attention particulière doit être portée à la communication inter-processeurs, inévitable dans les applications scientifiques. Dans un souci d’efficacité, cette communication inter-processeurs doit en effet s’effectuer en un temps strictement inférieur à celui de la différence entre le temps pris par la résolution séquentielle (sur ordinateur ordinaire uni-processeur) et celui de la résolution sur un des processeurs employés parallèlement. Sur ce point précis, il faut se poser la question suivante : la parallélisation de la résolution du problème est-elle nécessaire ? En effet, il n’est pas question de sous-exploiter un superordinateur. Dans le cas o`u le problème n’est pas assez grand (au sens des données de simulation et de la taille du système matriciel relatif), une décomposition judicieuse du traitement permet de réduire la complexité sur chaque subdivision du problème initial. Cependant, une majeure partie de la tâche parallèle sera absorbée par les communications inter-processeurs. Ceci peut rendre la simulation sur des ordinateurs séquentiels plus rapide que sur une machine parallèle, car les vitesses de traitement de ces machines séquentielles ont de nos jours beaucoup augmentées. Par exemple, pour la résolution d’équations aux dérivées partielles (EDP) avec des techniques de décomposition de domaine, le domaine spatial du calcul est décomposé en sous-domaines de calculs de petite taille. L’EDP originale (qui est définie sur le grand domaine) est ensuite résolue sur chacun des sous-domaines, et il est alors nécessaire de définir de fa¸con appropriée les conditions aux bords de chaque sous-domaine. Ceci permet des résolutions locales tout à fait indépendantes et simultanées.
L’algorithme pararéel en temps : un algorithme efficace pour la parallélisation en temps
Depuis sa publication , l’algorithme pararéel a fait l’objet de plusieurs études. Les numériciens ont cherché à l’adapter numériquement et à l’appliquer à divers problèmes. Il offre en effet une capacité importante de parallélisation des problèmes d’évolution qui semblaient intrinsèquement séquentiels et non-parallélisables. Bien qu’il y ait eu des tentatives de parallélisation des problèmes d’évolutions à partir des années 90 , celles-ci n’ont pas été exhaustives. L’algorithme pararéel tel qu’il a été présenté par Lions et al [41] et sous une version améliorée avec de nouveaux résultats de convergence [49], consiste en une méthode assez générale de parallélisation, des EDP et des EDO, pouvant être couplée avec d’autres méthodes itératives. Cet algorithme a été testé sur plusieurs équations pour lesquelles il s’est avéré très performant et robuste. Par exemple, sur des problèmes paraboliques linéaires et non linéaires [65, 9] pour lesquels l’algorithme pararéel tire profit de l’aspect dissipatif de ce type d’équations : celui-ci rectifie certaines instabilités de la solution grossière. L’algorithme a aussi été testé sur d’autres type d’EDP pour des application en mathématiques financières telle que le calcul d’une option de vente Américaine [9]. Il a également prouvé son efficacité dans les domaines de la dynamique moléculaire et de la cinétique en chimie. L’algorithme pararéel a également montré son efficacité lors du couplage avec d’autres types de méthodes itératives en accélérant la résolution des équations sur lesquelles il a été appliqué. Dans cet optique, nous distinguons deux classes : le couplage avec des méthodes de décomposition de domaine et le couplage avec des problèmes de contrôle optimal. Nous citons, dans le cadre de la décomposition de domaine, les travaux précurseurs dont l’objet est le couplage du pararéel avec une méthode de décomposition de domaine sans recouvrement. Aussi nous citons les travaux de Maday et Gueta dans le cadre d’une thèse de doctorat et dans Aouadi, Maday et Gueta (à paraˆıtre) ainsi que les travaux de Minion [53]. Nous renvoyons à pour le traitement du couplage du pararéel avec des problèmes de contrôle optimal. Dans cette thèse nous proposons des algorithmes parallèles dans trois domaines différents. Les trois parties correspondantes, sont complètement indépendantes.
Problème de contrôle optimal parabolique
Dans le cadre du projet de recherche ANR “PITAC” (Parallélisation Incluant le Temps pour Accélérer le Calcul), nous nous sommes intéressés à la parallélisation du problème de contrôle optimal d’un système régi par une EDP parabolique. Dans cette optique, nous nous inspirons de quelques techniques de parallélisation telles que le contrôle virtuel [38] (voir aussi utilisé par Maday et Turinici à travers l’introduction des sauts dans un terme quadratique dans la fonctionnelle de coˆut. Cette introduction des sauts a mené à l’utilisation de l’algorithme pararéel après avoir constaté son caractère préconditionneur vis-à-vis de l’équation d’optimalité d’une certaine fonctionnelle de coˆut. Une autre approche élégante est présentée dans [45] dans le cadre du contrôle de l’équation de Schr¨odinger. Cette méthode consiste à définir des points intermédiaires servant à la fois de conditions initiales et des cibles (comme c’est le cas d’ailleurs dans [47]), pour des sous-problèmes définis sur chacun des sous-intervalles de la décomposition. Ces deux dernières approches constituent les bases de la méthode de parallélisation en temps pour le contrôle optimal parabolique développé dans cette thèse. Nous considérons en effet une subdivision de l’intervalle de temps avec la définition suivante des conditions initiales λ et cibles ξ intermédiaires : λ := (λn)n≥0 := y, et ξ := (ξn)n≥0 := y − p, o`u y et p sont respectivement l’état direct et son adjoint dans le problème de minimisation. Ces définitions nous mènent aux sous-problèmes suivants : ∂tyn − ν∆yn = Bvn sur In × Ω y(t + n ) = λn (1.1) −∂tpn − ν∆pn = 0 sur In × Ω pn(t − n+1) = y(t − n+1) − ξn+1 (1.2) αvn + B ∗ pn = 0 sur In × Ω, o`u B ∗ est l’opérateur adjoint de B. Ces sous-problèmes sont indépendants et peuvent être résolus simultanément.
Problème de neutronique
Simulation de la cinétique des populations de neutrons au sein d’un réacteur nucléaire Dans le cadre du projet LRC Manon (Laboratoire de Recherche Conventionné Modélisation et approximation numérique orientées pour l’énergie nucléaire), et en collaboration avec des ingénieurs du CEA, nous nous sommes intéressés à l’application et l’adaptation de l’algorithme pararéel aux équations de la cinétique neutronique. Ces équations de grande taille doivent bénéficier d’une accélération afin de prévoir les cas accidentels au sein du réacteur nucléaire lors de la production d’électricité qui est basée sur une réaction en chaˆıne de fission des noyaux d’uranium. Nous simulons en trois dimensions un modèle réaliste avec deux groupes d’énergie de flux neutronique (indexés par g) et six groupes de concentrations de précurseurs (indexés par k). En outre, il faut prendre en compte la variation de la géométrie du domaine, due au mouvement vertical et continu des grappes 6 d’absorption. Celles-ci constituent un moyen de contrôle de la puissance produite au sein du cœur nucléaire.
Problème de mécanique quantique : contrôle optimal en résonance magnétique nucléaire
Dans le domaine de la spectroscopie par résonance magnétique nucléaire (RMN) les outils du contrôle optimal jouent un rôle fondamental dans l’obtention d’états physiques particuliers. Les outils mathématiques d’optimisation, typiquement les méthodes d’optimisation itératives, sont cruciaux pour affiner les expériences sur les instruments physiques. Dans le cadre d’une récente collaboration avec des physiciens, nous nous intéressons à un modèle de 5 spins couplés en phase liquide et qui sont ciblés par des champs magnétiques de contrôle. Ces champs de contrôle possèdent deux directions. Cela signifie que notre modèle quantique possède 10 composantes de contrôle. Ce modèle, riche en information, est assez complexe à résoudre. Sa résolution, ordinairement séquentielle, prend énormément de temps. Pour accélérer celle-ci, nous proposons une méthode de parallélisation [45] d’un problème de contrôle optimal associé à un algorithme monotone pour approcher la solution de l’état u des cinq-qbits qui vérifie l’équation de Schr¨odinger : ∂tu(t, x,y, z) = Hu(t, x,y, z) Dans H interviennent 5 champs magnétiques ayant la forme suivante : ωx(t)~x̺ + wy(t)~y̺ , o`u ̺ désigne l’atome de l’échantillon parmi H,P,C,N et F. Les travaux à ce stade sont en cours de développent, cependant les résultats préliminaires d’ouverture montre la pertinence de l’algorithme.
Chapitre 1 Introduction Générale |
