Parallélisme et Répartition

Master 1 Informatique, années 2008-2012

Objectifs Généraux

• Etre capable de "penser parallèle" dès la spécification d'une applicationjusqu'à sa mise en oeuvre efficace dans un environnement de calcul multi-processeurs (à mémoire partagée ou non).
• Avoir acquis les connaissances et concepts de base minimum pour affronter sereinenement la "révolution du multi-coeur" en tant que développeur logiciel

Contenu / Thèmes / Mots clé

• Calcul haute performance
• Architectures parallèles, Supercalculateurs, Grilles de calcul
• Modèles théoriques du parallélisme (PRAM, logP, ...)
• Mesures de performance, passage à l'échelle, prise en compte des modèles de mémoire
• Schémas classiques d'expression du parallélisme (maitre/esclaves, diviser pour régner, etc...)
• Algorithmes parallèles classiques (tris, algèbre, imagerie ...)
• Langages ou bibliothèques standard comme openMP, MPI
• Sensibilisation aux tendances : programmation (Stream_IT, TPL/Parallel, FX, Intel TBB, etc), architecture (multi-cores, GPUs, etc)

Ouvrages de référence

• M. Gengler, S. Ubeda, F. Deprez, Initiation au parallelisme - Concepts, architectures et algorithmes, Masson 1996 (une bonne introduction au sujet, et comme les concepts sont discutés à un niveau pas trop technique, le livre n'est pas trop demodé même si il commence à dater un peu)
• Algorithmique Parallèle, Cours et exercices corrigés, Arnaud Legrand, Yves Robert, Dunod, 2003, compléments sur http://mescal.inria.fr/membres/arnaud.legrand/algopar (tres bien fait, bien que nous ne nous servons que de tous petits extraits)
• A Grama, A. Gupt, G. Karpys, V. Kumar, Introduction to Parallel Computing (2nd edition), Addison Wesley 2003. (en partie ici www-users.cs.umn.edu/~karpys/parbook )
• P.S. Pacheco. "Parallel programming with MPI". Morgan Kaufmann. 1997.
• R. Chandra, R. Menon, L. Dagum, D. Kohr, D. Maydan, J. Mc_Donald. "Parallel Programming in openMP". Morgan Kaufmann Publishers. 2000. Voir aussi www.openmp.org

Organisation

Responsable : FabriceHuet

Enseignement :

• 7 séances de 2 heures de cours
• 7 séances de 2 heures de TD
• 7 séances de 2 heures de TD machine (sur une base de C sous Linux)

Contrôle des connaissances (1ère session) :

• Contrôle continu à 100 % :
  • Présence en cours : 5%
  • TD : 20%
  • TP : 30% (2 projets à rendre)
  • Devoir sur table (45%) : notes de cours manuscrites sur une unique feuille A4 autorisées.

Sujet d'examen individuel de Novembre 2008. Une reponse parfaitement redigee pour l'exercice 1. Une reponse pour l'exercice 2. De meme pour les exercices 3 et 4.

Sujet d'examen individuel de Decembre 2009. Vous trouvez ici des reponses correctes et raisonnablement bien expliquees pour l'exercice 1, 3, debut du 4, et une des questions en vrac de l'exercice 2.

Transparents de support de cours

TD (en salle)

1 Exemples simples et notions architecture parallèles

2 Graphe de parallélisme, et premiers algos parallèles

3 Premiers Algos PRAM

TD machine

1 Reconnaitre sur des programmes connus les formes de parallélisme

2 Introduction à openMP

3 Complements openMP et préfixes en parallèle

4 Sections parallèles et lignes de vue

5 OpenMPI

6 Broadcast et produit Matrice-Vecteur

7 Plus court chemin

Examen

1 Examen 2010-2011 Session 1 et une correction partielle

2 Examen 2010-2011 Session 2

Sites de cours thématiquement proches (et bien faits !)

• Calcul parallèle et distribué, et Grilles de calculs; Supelec, http://www.metz.supelec.fr/metz/personnel/vialle/course/IIC-CPDG/index.htm

• Advanced Parallel Programming: Models, Languages, Algorithms, Univ. Linkopings http://www.ida.liu.se/~chrke/courses/APP/

• Parallel Programming for Multicore, Electrical Engineering and Computer Sciences Department, University of California, Berkeley http://www.cs.berkeley.edu/~yelick/cs194f07

• Multicore Programming Primer: Learn and Compete in Programming the PLAYSTATION3 Cell Processor. MIT. http://cag.csail.mit.edu/ps3/lectures.shtml

• Programmation parallèle haute performance UQUAM http://www.labunix.uqam.ca/~tremblay/INF7235/

• Introduction au parallelisme, Master informatique, Univ. Paris Sud http://www.lri.fr/~cecile/ENSEIGNEMENT/IP/

• Presentation de MPI tres complete, et didactique, http://perso.limsi.fr/chergui/cours/ENSTA_mpi1_cours.pdf

Liens complémentaires sur le web

• http://www.thinkingparallel.com

• http://www.cilk.com/multicore-blog

• e-book: C. Leiserson, I. Mirman, "How to Survive the Multicore Revolution (or at Least Survive the Hype)" http://www.cilk.com/Default.aspx?app=LeadgenDownload&shortpath=docs%2fHow_to_Survive_the_Multicore_Software_Revolution.pdf

• Concepts of High Performance Computing, G. Hager, G. Welleim, March 2008 http://www.rrze.uni-erlangen.de/ausbildung/vorlesungen/coHPC.pdf

• Ian Foster, "Designing and building parallel programs". Addison-Wesley publishing company. 1994. (Gratuit ici: http://www-unix.mcs.anl.gov/dbpp/) : un peu ancien, mais peut être utile notamment concernant les concepts généraux; aborde le sujet d'un point de vue "software engineering"

• F. Pellegrini, Cours "Architectures et systèmes des calculateurs parallèles" ftp://ftp-developpez.com/pellegrini/parallelisme/calculateur/calculateurs-paralleles.pdf (permet d'approfondir les aspects architecture des processeurs)

• Cours "Systèmes parallèles et temps réel", Univ Laval, Canada, http://wcours.gel.ulaval.ca/2007/a/19268/default

Texte introductif et de motivation générale

Les ordinateurs multiprocesseur sont maintenant devenus la norme, tandis que les augmentations de vitesse des processeurs uniques ralentissent. La clé de l'amélioration des performances, réside par conséquent dans l'exécution d'un programme sur plusieurs processeurs en parallèle. L'impact sur la maniére de programmer les applications est considérable: celles-ci doivent absolument être concues comme etant multi-taches mais aussi, capables d'exhiber un comportement parallèle. En d'autre termes, jusqu'à présent, nous étions habitués à bénéficier d'un rendement accru pour nos programmes séquentiels et mono-thread, juste en profitant de l'évolution des processeurs. A présent, toutes les applications devront être concues comme etant parallèles et multithreadées, ceci supposant aussi de savoir gérer le partage de données et leur coordination.

L'objectif de ce module est donc d'introduire les concepts, algorithmes, méthodologies, outils utiles pour programmer en parallèle sur des architectures disposant de plusieurs unités de calcul (multi-processeurs et/ou multi-coeurs).

Par extension, on aborde aussi la programmation de systèmes constitués de la mise en réseau de plusieurs calculateurs. Dans ce cas, il devient difficile d'utiliser le concept de mémoire partagée pour coordonner et synchroniser l'exécution des différentes taches. Il s'agit alors de programmation parallèle et répartie qui repose sur l'échange (plus ou moins explicites) de messages entre les taches.

to top