Parallelism-High Performance Computing-Grid
- Domaine
- Parallelism-High Performance Computing-Grid
- Domain - extra
- Année
- 2012
- Starting
- September
- État
- Open
- Sujet
- Minimizing communication for sparse matrix operations on exascale systems
- Thesis advisor
- GRIGORI Laura
- Co-advisors
- Laboratory
- Collaborations
- UC Berkeley, University of Illinois at Urbana Champaign, Argonne
- Abstract
- This Phd subject is part of a larger project at INRIA Saclay and University Paris Sud which focuses on developing communication avoiding algorithms for high performance computing. These algorithms address one of the main challenge that we face today, which is the exponentially increasing gap between the time it takes to perform one floating point operation and the time it takes to move date between different levels of the memory hierarchy or between processors.
While we have several important results in dense linear algebra, much remains to be done in the context of sparse matrices. This is the focus of this thesis, which will focus on understanding the communication complexity of operations in sparse linear algebra and designing algorithms that minimize communication. The Phd student will have the opportunity to work and visit our international collaborators
from UC Berkeley and University of Illinois at Urbana-Champaign. - Context
- Parallelism is becoming ubiquitous nowadays, since all our computers are formed by multicore processors, while massively parallel computers are formed by thousands of multicore processors. However, much remains to be done to be able to exploit this massive parallelism, in terms of tools, languages, and algorithms. The research described here focuses on algorithms. It addresses one of the main challenges that the high performance computing community faces, which is the increased communication cost. Several works show that unavoidably our
algorithms will be spending more and more of their time communicating, instead of doing actual computation.
Our group works on a novel approach to address this problem, refered to as communication avoiding, in which the algorithms reduce the number of communication instances to a minimum. It is in this challenging context that the Phd student will perform his work. - Objectives
- In this research context, the work proposed here will focus on developing algorithms that minimize communication for sparse matrix operations, that include sparse matrix-vector multiplications, sparse matrix-matrix multiplications, and sparse direct factorizations.
The first goal of this research will be to study the communication complexity of sparse matrix operations. There are very few results in the literature on this topic, and we aim at using graph theory results to identify lower bounds on communication for sparse matrix operations. The study of communication complexity will allow us to identify existing algorithms that minimize communication and to understand the communication bottlenecks of those which are not optimal. This will lead to the design and the implementation of novel algorithms that are communication optimal. - Work program
- The first goal of this research will be to study the communication complexity of sparse matrix operations. There are very few results in the literature on this topic, and we aim at using graph theory results to identify lower bounds on communication for sparse matrix operations.
The algorithms will be adapted to the hierarchical structure of exascale parallel machines that are formed by thousands of multicore processors, often with accelerators as GPUs machines. They need to be based on mixed programming techniques and use advanced scheduling techniques necessary to obtain good performance on these machines.
An important part of this research will focus on the validation of the proposed methods and algorithms on real applications. Our group works on two particular applications. The first application arises in astrophysics, more precisely in the CMB data analysis. The second application is the simulation of compositional multiphase Darcy flow in heterogeneous porous m - Extra information
- Prerequisite
- The candidate should have a good background in algorithms and a good experience in C programming. Experience in parallel algorithms, parallel programming, or numerical linear algebra is a plus.
- Détails
LGrigori_CA.pdf- Expected funding
- Institutional funding
- Status of funding
- Expected
- Candidates
- Utilisateur
- laura.grigori
- Créé
- Mercredi 16 juin 2010 22:14:13 CEST
- dernière modif.
- Samedi 07 avril 2012 23:01:23 CEST
Connexion
Ecole Doctorale Informatique Paris-Sud
Directrice
Nicole Bidoit
Assistante
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps
ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr