Résolution triangulaire de systèmes linéaires creux de grande taille dans un contexte parallèle multifrontal et hors-mémoire.

Slavova Tzvetomila

Description

Niveau: Supérieur, Doctorat, Bac+8

• mémoire

THÈSE En vue de l'obtention du DOCTORAT DE L'UNIVERSITÉ DE TOULOUSE Délivré par INP Toulouse Discipline ou spécialité : INFORMATIQUE JURY Ecole doctorale : Mathématiques, Informatique et Télécommunications de Toulouse Unité de recherche : CERFACS Directeur de Thèse : Amestoy, P. R. Présentée et soutenue par Tzvetomila Slavova Le 28 Avril 2009 Titre : Résolution triangulaire de systèmes linéaires creux de grande taille dans un contexte parallèle multifrontal et hors-mémoire. Parallel triangular solution in the out-of-core multifrontal approach for solving large sparse linear systems. Amestoy P.R Professeur, INPT,Toulouse Directeur de thèse Duff,I. Directeur de recherche, CERFACS, Toulouse Co-encadrant Guermouche, A. LaBRI, Univ. Bordeaux 1 / INRIA Futurs Co-encadrant L'Excellent,J-Y. Chargé de recherche, INRIA-LIP, Lyon Membre Ng, E. G. Directeur de recherche, Lawrence Berkeley Lab. Rapporteur Trystram, D Professeur, INPG, Grenoble Rapporteur Ucar, B. Chargé de recherche CNRS, LIP, Lyon Membre

• rapporteur trystram


• futurs co


• grenoble rapporteur


• toulouse co


• délivré par inp toulouse


• résolution triangulaire de systèmes linéaires

Sujets

• Mémoire
• Institut national polytechnique de Toulouse
• Université de Toulouse

Informations

• Publié par: profil-feym-2012
• Publié le: 01 avril 2009
• Nombre de lectures: 24
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

THÈSE

En vue de l'obtention du

DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE

Délivré par INP Toulouse
Discipline ou spécialité : INFORMATIQUE


Présentée et soutenue par Tzvetomila Slavova
Le 28 Avril 2009

Titre : Résolution triangulaire de systèmes linéaires creux de grande taille
dans un contexte parallèle multifrontal et hors-mémoire.

Parallel triangular solution in the out-of-core multifrontal approach
for solving large sparse linear systems.




JURY

Amestoy P.R Professeur, INPT,Toulouse Directeur de thèse
Duff,I. Directeur de recherche, CERFACS, Toulouse Co-encadrant
Guermouche, A. LaBRI, Univ. Bordeaux 1 / INRIA Futurs Co-encadrant
L’Excellent,J-Y. Chargé de recherche, INRIA-LIP, Lyon Membre
Ng, E. G. Directeur de recherche, Lawrence Berkeley Lab. Rapporteur
Trystram, D Professeur, INPG, Grenoble Rapporteur
Ucar, B. Chargé de recherche CNRS, LIP, Lyon Membre



Ecole doctorale : Mathématiques, Informatique et Télécommunications de Toulouse
Unité de recherche : CERFACS
Directeur de Thèse : Amestoy, P. R.

THÈSE
présentée pour obtenir
LE TITRE DE DOCTEUR DE L’INSTITUT NATIONAL
POLYTECHNIQUE DE TOULOUSE
Spécialité: INFORMATIQUE
par
Tzvetomila Slavova
CERFACS
Résolution triangulaire de systèmes linéaires creux de
grande taille dans un contexte parallèle multifrontal et
hors-mémoire.
Parallel triangular solution in the out-of-core multifrontal
approach for solving large sparse linear systems
Thèse présentée le 28 Avril 2009 devant le jury composé de:
Amestoy, P. R. Professeur, INPT, Toulouse Directeur de thèse
Duff , I. Directeur de recherche, CERFACS, Toulouse Co-encadrant
Guermouche, A. LaBRI, Univ. Bordeaux 1 / INRIA Futurs Co-encadrant
L’Excellent, J-Y. Chargé de recherche, INRIA-LIP, Lyon Membre
Ng, E. G. Directeur de recherche, Lawrence Berkeley Lab. Rapporteur
Trystram, D. Professeur, INPG, Grenoble Rapporteur
Ucar, B. Chargé de recherche CNRS, LIP, Lyon Membre
Thèse préparée au CERFACS, CERFACS Report Ref: TH-PA-09-59Résolution triangulaire de systèmes linéaires creux de grande
taille dans un contexte parallèle multifrontal et hors-mémoire.
Parallel triangular solution in the out-of-core multifrontal
approach for solving large sparse linear systems2Abstract
We consider the solution of very large systems of linear equations with direct
multifrontal methods. In this context the size of the factors is an important limitation
for the use of sparse direct solvers. We will thus assume that the factors have been written
on the local disks of our target multiprocessor machine during parallel factorization.
Our main focus is the study and the design of efficient approaches for the forward and
backward substitution phases after a sparse multifrontal factorization. These phases
involve sparse triangular solution and have often been neglected in previous works on
sparse direct factorization. In many applications, however, the time for the solution can
be the main bottleneck for the performance.
This thesis consists of two parts. The focus of the first part is on optimizing the out-of-
core performance of the solution phase. The focus of the second part is to further improve
the performance by exploiting the sparsity of the right-hand side vectors.
In the first part, we describe and compare two approaches to access data from the
hard disk. We then show that in a parallel environment the task scheduling can strongly
influence the performance. We prove that a constraint ordering of the tasks is possible;
it does not introduce any deadlock and it improves the performance. Experiments on
large real test problems (more than 8 million unknowns) using an out-of-core version of a
sparse multifrontal code calledMUMPS (MUltifrontal Massively Parallel Solver) are used
to analyse the behaviour of our algorithms.
In the second part, we are interested in applications with sparse multiple right-hand
sides, particularly those with single nonzero entries. The motivating applications arise in
electromagnetism and data assimilation. In such applications, we need either to compute
the null space of a highly rank deficient matrix or to compute entries in the inverse of a
matrix associated with the normal equations of linear least-squares problems. We cast
both of these problems as linear systems with multiple right-hand side vectors, each
containing a single nonzero entry. We describe, implement and comment on efficient
algorithms to reduce the input-output cost during an out-of-core execution. We show how
the sparsity of the right-hand side can be exploited to limit both the number of operations
and the amount of data accessed.
The work presented in this thesis has been partially supported by SOLSTICE ANR
project (ANR-06-CIS6-010).
Keyword: Gaussian elimination, multifrontal method, Distributed computing, parallel
computing, sparse matrices, tasks scheduling, multiple right-hand side vectors.iiRésumé
Nous nous intéressons à la résolution de systèmes linéaires creux de très grande taille
par des méthodes directes de factorisation. Dans ce contexte, la taille de la matrice
des facteurs constitue un des facteurs limitants principaux pour l’utilisation de méthodes
directes de résolution. Nous supposons donc que la matrice des facteurs est de trop grande
taille pour être rangée dans la mémoire principale du multiprocesseur et qu’elle a donc
été écrite sur les disques locaux (hors-mémoire : OOC) d’une machine multiprocesseurs
durant l’étape de factorisation. Nous nous intéressons à l’étude et au développement
de techniques efficaces pour la phase de résolution après une factorization multifrontale
creuse. La phase de résolution, souvent négligée dans les travaux sur les méthodes
directes de résolution directe creuse, constitue alors un point critique de la performance
de nombreuses applications scientifiques, souvent même plus critique que l’étape de
factorisation.
Cette thèse se compose de deux parties. Dans la première partie nous nous proposons
des algorithmes pour améliorer la performance de la résolution hors-mémoire. Dans
la deuxième partie nous pousuivons ce travail en montrant comment exploiter la nature
creuse des seconds membres pour réduire le volume de données accédées en mémoire.
Dans la première partie de cette thèse nous introduisons deux approches de lecture
des données sur le disque dur. Nous montrons ensuite que dans un environnement
parallèle le séquencement des tâches peut fortement influencer la performance. Nous
prouvons qu’un ordonnancement contraint des tâches peut être introduit; qu’il n’introduit
pas d’interblocage entre processus et qu’il permet d’améliorer les performances. Nous
conduisons nos expériences sur des problèmes industriels de grande taille (plus de 8
Millions d’inconnues) et utilisons une version hors-mémoire d’un code multifrontal creux
appeléMUMPS (solveur multifrontal parallèle).
Dans la deuxième partie de ce travail nous nous intéressons au cas de seconds membres
creux multiples. Ce problème apparaît dans des applications en electromagnétisme
et en assimilation de données et résulte du besoin de calculer l’espace propre d’une
matrice fortement déficiente, du calcul d’éléments de l’inverse de la matrice associée
aux équations normales pour les moindres carrés linéaires ou encore du traitement de
matrices fortement réductibles en programmation linéaire. Nous décrivons un algorithme
efficace de réduction du volume d’Entrées/Sorties sur le disque lors d’une résolution hors-
mémoire. Plus généralement nous montrons comment le caractère creux des seconds
-membres peut être exploité pour réduire le nombre d’opérations et le nombre d’accès à
la mémoire lors de l’étape de résolution.
Le travail présenté dans cette thèse a été partiellement financé par le projet SOLSTICE
de l’ANR (ANR-06-CIS6-010).
Mots-clés: calcul distribué, calcul parallèle, élimination de Gauss, matrices creuses,
méthode multifrontale, séquencement des tâches, seconds membres multiplesiv