Master Informatique première année

Introduction au parallélisme

2010-2011

Enseignants

Cécile Germain-Renaud - cecile.germain (at) lri (dot) fr (Responsable)
Joël Falcou

Présentation

Les systèmes parallèles sont devenus la norme, qu'il s'agisse des systèmes de calcul ultra-hautes performances, des ordinateurs personnels ou des serveurs web. Le cours est une introduction aux questions théoriques et pratiques que pose l'exploitation efficace de ces environnements. La ligne directrice du cours est la réalisation des compromis entre efficacité et expressivité des modèles du parallélisme, qui restent multiples. le cours aborde les points suivants, en les illustrant par de nombreux exemples d'algorithmes et d'applications.

Architectures parallèles : typologie des architectures, classification de Flynn, organisation de l'espace d'adressage, hiérarchisation, réseaux d'interconnexion.
Modèles du parallélisme : Graphes de tâches, parallélisme de données et de contrôle, modèles de performances, opérateurs nouveaux (réduction, diffusion, synchronisation)
Typologie des applications. Placement-ordonnancement
Exemples et utilisation de langages/environnements parallèles classiques (MPI, HPF, OpenMP) et plus récents (MapReduce, CUDA).
Introduction a la parallélisation automatique.

Calendrier

Date	Cours	Devoirs et Exposés
03/01	Motivation & concepts
10/01	Algorithmique parallèle (I)
17/01	Algorithmique parallèle (II) - Placement-ordonnancement
24/01	Architectures de communication
31/01	Programmation en espaces d'adressages multiples (I)	Sujet du Devoir 1
07/02	Programmation en espaces d'adressages multiples (II)
14/02	Programmation en espaces d'adressages multiples (III)
28/02	Programmation en Espace d’adressage unique (I)	Choix exposes
07/03	Programmation en Espace d’adressage unique (II)	Rendu Devoir 1 et Sujet du Devoir 2
14/03	Parallélisme de données
21/03	Programmation GPU
28/03	Parallélisation automatique	Rendu Devoir 2
Semaine des examens	Examen (matin) et exposés (après-midi)

TD

Sujets

Exposés

Modèle LogP Culler, D. E., Liu, L. T., Martin, R. P., and Yoshikawa, C. O. 1996. Assessing Fast Network Interfaces. IEEE Micro 16, 1 (Feb. 1996), 35-43. Document. On peut consulter aussi : Document et Document.
Cilk Blumofe, R. D. and Leiserson, C. E. 1999. Scheduling multithreaded computations by work stealing. J. ACM 46, 5 (Sep. 1999), 720-748. Document
Consistance mémoire - Adve, S. V. and Gharachorloo, K. 1996. Shared Memory Consistency Models: A Tutorial. Computer 29, 12 (Dec. 1996) Document
Go parallèle - On the Parallelization of Monte-Carlo planning Sylvain Gelly, Jean-Baptiste Hoock , Arpad Rimmel, Olivier Teytaud, Yann Kalemkarian ICINCO (2008) Document
Réseaux d'interconnexion - John Kim, William J. Dally, and Dennis Abts. “Flattened Butterfly: Cost-Efficient Topology for High-Radix Networks” Proceedings. 33rd Annual International Symposium on Computer Architecture(ISCA), June 2007 Document
Map Reduce - Jeff Dean and Sanjay Ghemawat, Proceedings of the 2004 OSDI Conference, 2004. Document
Evaluation de MapReduce - Ranger, C., Raghuraman, R., Penmetsa, A., Bradski, G., and Kozyrakis, C. 2007. Evaluating MapReduce for Multi-core and Multiprocessor Systems. In Proceedings of the 2007 IEEE 13th international Symposium on High Performance Computer Architecture (February 10 - 14, 2007). Document ET Document en ligne
Exploration d'arbres - Bernard Mans, Catherine Roucairol: Performances of Parallel Branch and Bound Algorithms with Best-first Search. Discrete Applied Mathematics 66(1): 57-74 (1996) Document
Algorithme de Strassen pour le produit de matrices - Desprez, F. and Suter, F. 2004. Impact of mixed-parallelism on parallel implementations of the Strassen and Winograd matrix multiplication algorithms: Research Articles. Concurr. Comput. : Pract. Exper. 16, 8 (Jul. 2004) Document. On peut consulter aussi Document .
Modèle Divisible Beaumont, O., Legrand, A., and Robert, Y. 2003. Optimal Algorithms for Scheduling Divisible Workloads on Heterogeneous Systems. In Proceedings of the 17th international Symposium on Parallel and Distributed Processing (April 22 - 26, 2003). IPDPS. IEEE Computer Society, Washington, DC, 98.2. Document

Evaluation

Note finale = 0.4*CC + 0.6* Examen

Contrôle continu : La moitié pour les devoirs, l'autre moitié pour les exposés.
Devoirs individuels. Les devoirs rendus après la date de remise ne sont pas acceptés.
Exposés en binôme. Résumé de 2 pages plus exposé de 20'. Un membre du binôme est noté sur le résumé, l'autre sur l'exposé.
Tous les documents sont autorisés au partiel et à l'examen.

Page maintenue par Cécile Germain-Renaud