Mar 22/09 10h15: PRAM (1): introduction; exemples de
sauts de pointeurs (diviser-pour-règner); définitions (travail,
efficacité) et simulation (conservation du travail, théorème de Brent).
Mar 29/09 10h15: PRAM (2): séparation des
modèles, et la fameuse machine à trier de Cole. Conclusion PRAM:
théorie vs pratique... Todo: Lire (et chercher) la démonstration de
correction de la machine à trier.
Mar 06/10 10h15: Algorithmique sur un anneau de processeurs (1):
introduction et algos de diffusion avec le principe du
pipeline. Mémoire distribuée vs mémoire partagée des PRAMs.
Mar 13/10 10h15: Algorithmique sur un anneau de processeurs (2): produit
matrice-vecteur, matrice-matrice, balayage d'images... Bilan sur les
topologies virtuelles, les implémentations distribuées vs
centralisées, l'algorithmique sur anneaux. Todo: Ecrire d'autres algos de balayage d'images, et aussi un
algo de décomposition LU sur anneau (la solution est sur
les feuilles distribuées en cours).
Mar 20/10 10h15: Survol des réseaux d'interconnections
et de différents modèles de communications, et le cas de
l'hypercube. Todo: Ecrire et bien comprendre l'algorithme de diffusion dans
l'hypercube.
Mar 27/10 10h15: Ordonnancement (1): introduction aux graphes de
tâches; définition des ordonnancements et des problèmes
d'optimisation associés dans le cas sans communications; complexité
des problèmes avec un nombre infini/fixé de processeurs.
Mar 03/11 10h15: Ordonnancement (2): étude des
heuristiques de listes: garantie et exemple qui atteint
la borne; introduction des coûts de communication: exemples,
NP-complétude du problème à resources non bornées, et heuristique
garantie pour les graphes à gros grains.
Mar 10/11 10h15: Partiel: Réseaux de
tri, PRAM, algo sur anneau, topologies et modèles de coms, hypercube.
Mar 17/11 10h15: Ordonnancement (3): heuristiques: le chemin
critique avec ou sans communications, les techniques de
clustering, et comparaison d'heuristiques.
Mar 24/11 10h15: Architectures
systoliques: comment faire un produit de matrices? Todo: faire une décomposition LU en systolique (la solution est
sur les feuilles distribuées en cours).
Mar 01/12 10h15: Nids de boucles (1): analyse de dépendances, les
graphes de dépendances étendus/réduits, principe de la distribution
de boucles et exemple illustrant l'algorithme d'Allen et Kennedy.
Mar 08/12 10h15: Pas cours, mais TD dans le créneau du
cours (Amphitéatre Schrodinger).
Mar 15/12 10h15: Nids de boucles (2): Formalisation de
l'algorithme d'Allen et Kennedy, et transformations unimodulaires
(méthode de l'hyperplan de Lamport).