M2 QUAntum Research Master Education Network – ERASMUS MUNDUS QUARMEN

Marc Baboulin.

The focus of this course is the parallel programming in distributed memory systems, with the message-passing paradigm using the MPI library.
Fundamentals of MPI programming model, spawning multiple processes, process rank, communicators and sub-communicators, and the distributed memory concept
Point-to-point MPI communications
Blocking vs. non-blocking MPI communications
Collective communication algorithms and MPI routines
Barriers, synchronizations, deadlock prevention
Performance optimization/tuning, load balancing, communication cost
Hybrid parallelism MPI+OpenMP
Advanced MPI topics time permitting (MPI shared memory, neighborhood collectives, ...).

Knowledge of algorithms and programming in C/C++ Basics of computer architecture [M1 QDCS] Parallel algorithms (recommanded).

Janna Burman.

Relation avec d'autres modules : Le module " Auto-stabilisation " est axé sur une autre technique majeure de tolérance aux défaillances, complémentaire de la réplication. Contrairement à cette dernière, l'auto-stabilisation rende les systèmes robustes contre toute défaillance transitoire, mais l'effet des défaillances n'est pas masqué pendant la phase de la stabilisation, comme c'est le cas avec la réplication.

L'évaluation se fait par des épreuves de contrôle continu (interrogations écrites, TD notés, devoirs, lecture et présentations d'articles) et un examen terminal écrit ou oral.

Distributed algorithms are the basis of distributed systems and applications, such as the Internet, the Internet of Things, the Cloud, Bitcoin, etc. In addition to the difficulties induced by the geographical distribution and the dynamical evolution of their components, these real systems are subject to failures: shutdowns, memory corruption, behaviour of malicious participants, etc.
In order to guarantee the correct operation of such systems, a major challenge is to know how to manage both the dynamics and its failures, which multiply with large scale deployments. This module presents a major technique to tolerate a bounded number of (definitive) failure varieties, by completely covering for them.
The objectives of this module are to:
give the basics of distributed algorithms,
understand the problems that arise when designing a robust distributed system and to give solutions to these problems,
address the notions of proof of distributed algorithms and complexity analysis,
make students aware of the fault tolerance aspect,
introduce the replication technique, followed by consensus.

Basic notions of networking, systems, algorithms and complexity.

ORSAY - GIF-SUR-YVETTE

Oguz Kaya.

FR: L'évaluation du cours est basée sur un examen final écrit. Plan du cours: -Description du modèle de machine PRAM. -Travail et profondeur des algorithmes PRAM, optimalité de travail, théorème de Brent. -Conception et analyse d'algorithmes parallèles utilisant le modèle PRAM. -Description des machines parallèles à mémoire distribuée, des réseaux de communication et des algorithmes de communication. -Algorithmes parallèles de graphes et d'arbres. -Algorithmes parallèles de tri et de recherche. -Algorithmes parallèles du calcul matriciel.

EN: Course grading is based on a final written exam. Course plan: -Description of the PRAM model. -Work and depth of PRAM algorithms, work optimality, Brent's theorem. -Design and analysis of parallel algorithms using the PRAM model. -Description of the distributed memory parallel machines, communication networks, and communication algorithms. -Parallel graph and tree algorithms. -Parallel sorting and searching. -Parallel linear algebra kernels.

The goal of this course is to provide an adequate theoretical background for the design and analysis of parallel algorithms in different parallel computing environments. The course starts with the introduction of an ideal parallel machine (parallel random-access-machine, or PRAM), then focuses on designing various optimal algorithms and analyzing their complexity in this setting. Then, distributed-memory parallel architectures with different communication networks are introduced. Finally, the parallelization of many well-known fundamental algorithms are discussed.

Basic algorithmic skills Programming knowledge Basic understanding of a computer architecture.

-Introduction to parallel computing (Grama, Gupta, Karypis, Kumar). -Parallel algorithms (Blelloch).

ORSAY - GIF-SUR-YVETTE