% INF5171 — Programmation concurrente et parallèle % UQAM — Département d'informatique % Plan de cours — Automne 2021 * Horaires, locaux et enseignants: Responsable(s) du cours ======================= Coordination ------------ Beaudry, Éric PK-4635 Enseignement ------------- Giraldeau, Francis Groupes: 020 Description =========== Objectifs --------- Familiariser les étudiants avec les concepts et les paradigmes de la programmation concurrente et parallèle. Acquérir les compétences nécessaires à la mise en oeuvre de ces concepts dans différents environnements, afin d'obtenir des programmes performants et fiables. Sommaire du contenu ------------------- Architectures parallèles : architecture des processeurs (pipelines, coeurs multiples); multiprocesseurs, multi-ordinateurs, grilles de calculs. Types d'application concurrentes : à fils d'exécution multiples, parallèles, distribuées. Synchronisation et communication : variables partagées, échange de messages. Programmation par variables partagées : verrous, sémaphores, barrières, moniteurs. Mesures de performance: temps, coût, accélération, efficacité. Stratégies de programmation : parallélisme itératif, récursif, de flux, de données, de sac de tâches; parallélisme de résultat, d'agenda, de spécialistes. Modalité d'enseignement ----------------------- Ce cours comporte une séance hebdomadaire obligatoire de laboratoire (2 heures). Préalables académiques ---------------------- - INF3173 - Principes des systèmes d'exploitation Contenu détaillé ---------------- **Sommaire** - Introduction et rappels des concepts des systèmes d'exploitation. - Types d'architectures parallèles: processeurs multi-coeurs, processeur graphique, grappes de calculs. - Parallélisme de tâches, de données et chemin critique. - Analyse des algorithmes parallèles: temps d'exécution, accélération et efficacité. - Synchronisation, opérations atomiques et communication interprocessus. - Exploitation des instructions vectorielles - Mesure de performance, compteurs de performance, intensité arithmétique, bande passante et effet de cache. - Test et vérification des applications parallèles. - Mise en oeuvre en C++ à l'aide de librairies modernes. **Introduction et rappels** - Survol des architectures parallèles - Classe de traitement parallèle - Calcul de l'accélération - Rappels à propos des systèmes d'exploitation **Parallélisme de tâche** - Identification des sections séries et parallèles - Gestion de fil d'exécution à bas-niveau - Synchronisation: verrous, conditions, barrières - Étude de cas avec la librairie Pthreads **Parallélisme de données** - Granularité du calcul - Chemin critique d'exécution - Division du travail en intervalle - Conditions critique - Variable partagée ou locale - Analyse du coût et de l'accélération asymptotique - Réduction et trie en parallèle - Intégration en parallèle - Étude de cas avec la librairie OpenMP - Étude de cas avec la librairie TBB **Instructions vectorielles** - Principe de fonctionnement - Registres et instructions x86 - Utilisation de l'API intrinsèque - Vectorisation automatique et avec OpenMP - Élimination des branches **Calcul sur processeur graphique** - Différence entre architectures - Définition et lancement de noyau de calcul - Communication entre l'hôte et le périphérique - Étude de cas avec OpenCL (ou équivalent) **Hiérarchie de mémoire** - Organisation de la hiérarchie de mémoire - Protocole de cohérence de cache - Opérations atomiques - Défaut de cache v.s. faute de page - Patrons d'accès à la cache - Problème de faux partage - Profilage des accès mémoires - Intensité arithmétique - Modèle de la ligne de toit **Programmes distribués** - Calcul sur grape - Modèles de communication - Accélération en fonction de la taille du problème - Notion d'efficacité - Étude de cas avec MPI **Mesure de performance** - Mesure du temps écoulé - Comparaison des méthodes de profilage - Traçage d'application et du noyau - Étude du code assembleur généré - Outils statistique pour la comparaison des résultats **Vérification des programmes parallèles** - Stratégie de débogage - Mise à l'échelle, banc d'essais de performance - Méthode de test de charge - Vérification formelle statique v.s. fonctionnement - Étude de cas avec Helgrind et ThreadSanitizer Évaluation ========== Description sommaire Semaine(s) Pondération (%) ---------------------- ------------------ ----------------- Quiz 1 4 5 Quiz 2 13 5 Examen mi-session 9 (2 novembre) 20 Examen final 15 (21 décembre) 30 TP1 4 (remise) 10 TP2 7 (remise) 10 TP3 10 (remise) 10 TP4 13 (remise) 10 Les sujets pour des travaux pratiques vont dépendre du matériel et de l'environnement disponible pour leur réalisation. Les travaux pratiques sont à réaliser seuls ou en équipe de deux. Il est important que chaque personne comprenne bien les laboratoires et les travaux pratiques, car ils feront l'objet de questions aux examens. Le rapport et le code doivent être remis sur Moodle. Attention: aucune remise ne pourra être faite après la date limite fixée dans Moodle. En cas de divergences avec l'entente d'évaluation, les modalités de l'entente d'évaluation prévalent.