Bienvenue sur le site de l'UE

Programmation Parallèle

Master 1 informatique - Semestre 2 - Année 2016-2017


Responsable: Rémi MORIN: remi.morin(at)lif.univ-mrs.fr

Résumé

Depuis la généralisation des architectures multi-coeurs, la programmation parallèle est devenue incontournable pour développer des applications exploitant pleinement les capacités de traitement offertes par les ordinateurs actuels. Elle est aussi un moyen de simplifier la structure du logiciel en l'organisant sous la forme de tâches distinctes qui interagissent entre elles afin de répondre aux requêtes de l'utilisateur (ou de l'environnement).
Cette UE présente aux étudiants du M1 les principales difficultés de la programmation multi-thread et les techniques classiques permettant de développer un code correct et performant. Tout d'abord, les instructions de base liées à la classe Thread en Java sont introduites avec les concepts sous-jacents de verrou et de variable de condition. L'effet de ces instructions sur l'état d'un thread est illustré sur des exemples simples s'appuyant sur des diagrammes de séquence. Les notions d'indépendance et d'atomicité permettent ensuite de spécifier précisément les problèmes classiques de synchronisation en séparant le besoin d'exclusion mutuelle des contraintes d'attente particulières. L'approche recommandée pour débuter est celle de la conception et de la programmation de moniteurs (à la Hoare), étudiée sur plusieurs exemples classiques.
Les outils dédiés à la programmation parallèle en Java sont également présentés en cours et exploités en Travaux Pratiques: locks divers, pools de threads, collections synchronisées ou concurrentes, objets atomiques, etc. Les difficultés propres à la programmation sans verrou sont illustrées par la construction de structures de données simples et de verrous performants.
Enfin, un aperçu du modèle mémoire Java permet d'initier les étudiants à la notion de programme «bien synchronisé» et aux risques d'exécutions inconsistantes séquentiellement du fait des optimisations de codes réalisées lors de la compilation ou de l'exécution.
Emploi du temps prévisionnel:

Organisation

Le module consiste en 10h de cours, 10h de TD et 10h de TP.
Trois rendus de TP comptent pour 40 % dans la note finale. En particulier, un projet en temps limité (TP noté) en fin de semestre permet d'évaluer la maitrise de quelques techniques de programmation.

Planning


Cours

TD

TP

Semaine 1

Présentation de l'UE et des MCC
Introduction aux threads en Java:
volatile, synchronized, wait(), notify(), etc.

Premiers programmes multithreads
Fonctionnement des verrous

Partage dynamique de tâches
États d'un thread

Semaine 2

Indépendence et atomicité
Rappels de techniques de synchronisation:
Moniteurs, sémaphores, etc.

Le dîner des philosophes
et quelques variantes

Blanche-neige équitable
La corde des babouins
Lâcher-prise des philosophes

Semaine 3

Outils concurrents de Java 5:
Verrous, objets atomiques, threadpool
Collections synchronisées et concurrentes

Le problème des sauvages
Association de nains qui dansent

Codage du pôt des sauvages
Nains et hobbits dans une barque

Semaine 4

Programmation optimiste
Problème ABA

Recherche de bugs divers
Emploi des verrous de Lecture/Ecriture

Emplois d'un threadpool
Accélération du tri rapide

Semaine 5

Aperçu du modèle mémoire Java
Consistence séquentielle et garantie DRF

Programmation sans verrou

Projet en temps limité

Compléments

Références bibliographiques

  1. Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965.
    Technological University, Eindhoven, The Netherlands.
    Vous y retrouverez le problème du barbier.
  2. Hierarchical ordering of sequential processes by E.W. Dijkstra (1971, June).
    Acta Informatica 1(2): 115–138.
    Vous y retrouverez le problème des philosophes.
  3. Monitors: An Operating System Structuring Concept, C.A.R. Hoare
    Communications of the ACM, Vol. 17, No. 10. October 1974, pp. 549-557.
  4. Programmation concurrente en Java, Brian Goetz.
    Pearson, Mai 2009 | ISBN-10: 2-7440-2508-9 | ISBN-13: 978-2-7440-2508-2
  5. The Art of Multiprocessor Programming, Maurice Herlihy, Nir Shavit.
    Morgan Kaufmann Pub, Février 2008 | ISBN-10: 0123705916 | ISBN-13: 978-0123705914