[Home bibliotech]
Home > Les thèses en ligne de l'INP

Algorithmes Parallèles Asynchrones pour la Simulation Numérique

Chau, Ming (2005) Algorithmes Parallèles Asynchrones pour la Simulation Numérique. (Parallel Asynchronous Algorithms in Numerical Simulation.)

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
0.97 Mo

Abstract

En simulation numérique, la discrétisation des problèmes aux limites nous amène à résoudre des systèmes algébriques de grande dimension. Parmi les voies d'investigation et compte tenu de l'évolution actuelle des architectures des ordinateurs, la parallélisation des algorithmes est une solution naturelle pour résoudre ces problèmes. Or lorsqu'on exploite des calculateurs parallèles, les temps d'attente dus à la synchronisation entre les processus coopérants deviennent pénalisants ; cette perte de temps s'avère d'autant plus considérable en présence de déséquilibre de charge. Les algorithmes parallèles asynchrones permettent d'envisager de minimiser les pertes de temps dus la synchronisation, sans faire appel aux techniques d'équilibrage de charge. Ce sont des algorithmes itératifs dans lesquels les composantes du vecteur itéré sont réactualisées en parallèle, dans un ordre arbitraire et sans synchronisation. Les restrictions imposées aux algorithmes sont très faibles. De plus, les modèles mathématiques qui décrivent ce type de méthode permettent de prendre en compte le maximum de flexibilité entre les processus et d'assurer, sous certaines hypothèses, la convergence des algorithmes itératifs. Dans l'étude proposée, les modèles mathématiques ainsi que les théorèmes de convergence des itérations parallèles asynchrones classiques et avec communication flexible sont présentés dans un premier temps. Ensuite, nous exposons la parallélisation de l'algorithme de Schwarz à l'aide de la bibliothèque MPI (Message Passing Interface). Une étude de performance menée sur le serveur de calcul de l'IDRIS (Institut du Développement et des Ressources en Informatique Scientifique) permet de comparer les versions synchrones et asynchrones de l'algorithme parallèle dans le cadre de la résolution d'un problème de convection-diffusion tridimensionnel. Elle met en évidence les gains de temps obtenus grâce à l'asynchronisme. Enfin, sur le plan applicatif, nous nous sommes intéressés à des problèmes tridimensionnels tels que l'électrophorèse de zone à écoulement continu (dont le modèle mathématique résulte d'un couplage entre une équation de Navier-Stokes, une équation de convection-diffusion et une équation de Poisson généralisée) et le problème de l'obstacle (intervenant en mécanique et en mathématiques financières). Dans le cadre de ces applications, des études de performances ont également été menées. ABSTRACT : In numerical simulation, the discretization of boundary value problems lead to the solution of large sparse linear systems. Among the research topics and regard to the evolution of computer architectures, the parallelisation of the algorithms is a natural way to overcome the problems. However, the overhead due to the synchronization between the processors is the drawback of the use of parallel computers ; the waste of time is even more significant as the load is unbalanced. Parallel asynchronous algorithms allow to minimize the overhead due to synchronisation, without using load balancing techniques. These iterative algorithms consist in updating the components of the iteration vector in a parallel way, without synchronization, in an arbitrary order. The restrictions imposed on these algorithms are very weak. Furthermore, the mathematical models that describe the considered algorithms take into account very flexible parallel computation schemes and ensure the convergence of the iterative algorithms, under some hypothesis. The structure of the thesis is as follows. Firstly, mathematical models and convergence results of classical and flexible communication asynchronous iterations are presented. Then the implementation of parallel asynchronous Schwarz algorithm using MPI (Message Passing Interface) is exposed. The synchronous and asynchronous implementations of the algorithms are compared in the context of the solution of 3D convection-diffusion equations. The numerical experiments are carried out on the supercomputer of IDRIS (Institut du Développement et des Ressources en Informatique Scientifique). The benefits brought by asynchronism are shown. Finally, the algorithms are applied to the solution of 3D problems such as the continuous flow electrophoresis (which consists in coupling an incompressible Navier-Stokes equation with a convection-diffusion equation and a generalised Poisson equation) and the obstacle problem (which occurs in financial mathematics). Performance studies have also been carried out in the context of these applications.

Department or laboratory:Institut de Recherche en Informatique de Toulouse - IRIT (Toulouse, France)
Directeur de thèse:Spitéri, Pierre and Guivarch, Ronan
Uncontrolled Keywords:Calcul scientifique - Equations aux dérivées partielles - Electrophorèse - Méthode alternée de Schwarz - Parallélisme - Problème de l'obstacle - Algorithmes asynchrones. KEYWORDS : Scientific computing - Partial differential equations - Electrophoresis - Alternating Schwarz method - Parallelism - Obstacle problem - Asynchronous algorithms
Subjects:Computer science > Computer programming and systems
Computer science > Computer science and telecommunications
Deposited On:22 December 2005

Archive Staff Only: edit this record


Contacts | Infos légales | Plan du site | Intranet

(c)INP de Toulouse 2012 - Tous droits réservés. -  INP Communication