Derniers contenus

Voici le Colloscope MPI/MPI*, sur lequel vous trouverez toutes les informations nécessaires quant au planning des khôlles et-TP khôlles..

1. TP-khôlles

Les passages en TP-Khôlles s'effectueront le vendredi matin avec M. Peignier en salle R106. Une demi-classe est présente de 8 h à 11 h 10, avec alternance chaque semaine (la sonnerie de début est à 8 h 10, mais soyez sûrs d'arriver à 8 h 00 afin de directement lancer les machines...). A chaque TP-kholle, tout le monde travaille sur le TP, mais seuls deux trinômes seront vraiment évalués en pratique, avec moi qui navigue entre les étudiants à évaluer. Il est possible de prendre du temps pour répondre aux questions des autres, mais dans une certaine limite.

Planning consultable sur le colloscope.

Plus de détails sur ce qui est concrètement attendu sur ce document

2. Khôlles classiques

Les passages en Khôlles classiques s'effectueront le mardi de 12 h à 13 h en salle (F402) avec M. Besson.

Planning consultable sur le colloscope.

Tout ce qui précède, auquel on ajoute le début du chapitre de Concurrence et de synchronisation.

Il faut :

- savoir ce qu'est un thread ("sous-programme" qui partage la mémoire du processus qui l'a créé). On ne demande pas de connaître par coeur les fonctions en OCaml ou en C permettant de gérer les thread, elles doivent être rappelées ; mais il faut savoir les utiliser.

- savoir ce qu'est une section critique

- savoir utiliser un ou plusieurs mutex pour protéger des sections critiques, en utilisant le principe de verrouillage/déverrouillage ; la syntaxe des fonctions OCaml ou C utilisées n'est pas à connaître par coeur, mais il faut savoir les utiliser une fois qu'elles sont rappelées.

- connaître l'algorithme de Peterson et l'algorithme de la Boulangerie de Lamport, qui fournissent des implémentations basiques de lock/unlock (même si elles ne sont plus utilisées aujourd'hui)

- connaître les définitions des problèmes suivants qui peuvent survenir lors de l'exécution de thread en parallèles : interblocage, attente active, famine. Ces problèmes peuvent survenir si on fournit une mauvaise implémentation des outils de synchronisation (Peterson/Lamport ont de l'attente active), mais même avec une bonne implémentation de ces outils, leur mauvaise utilisation peut conduire à ces problèmes.

On pourra demander aux élèves d'écrire des morceaux de code simple pour paralléliser des blocs de code, et leur demander de résoudre des problèmes de synchronisation simples (expliquer pourquoi une solution à un problème n'est pas satisfaisante, comment la corriger, etc...). Les sémaphores ont été évoqués trop récemment pour pouvoir être utilisés, on s'abstiendra de donner des exercices utilisant des sémaphores pour l'instant.

Tout ce qui précède, auquel on ajoute la partie sur les algorithmes d'approximation. Aucune méthode générale de construction de tels algorithmes n'est exigible (bien qu'on puisse guider les élèves vers la construction d'un tel algorithme sans le fournir directement, quand elle est basée sur une méthode facile, par exemple une approche gloutonne). Il faut cependant :

- savoir ce qu'est une $\alpha$-approximation calculée par un algorithme

- si on connaît la borne $\alpha$ fournie par un algorithme, savoir montrer qu'elle est minimale (en montrant qu'elle est atteinte)

- savoir justifier qu'un algorithme n'est pas une $\alpha$-approximation, pour $\alpha$ fixé (en exhibant une mauvaise instance) et pour tout $\alpha$ (en exhibant une mauvaise instance pour tout $\alpha$)

Les schémas d'approximations (algorithmes d'approximations prenant en paramètre un $\varepsilon$ et garantissant une borne de la forme $\alpha = 1+\varepsilon$, qui permettent donc une précision aussi grande que l'on veut) ne sont pas explicitement au programme, et donc en sont pas à connaître. On peut cependant travailler avec des tels algorithmes en fournissant le guidage nécessaire.