Mar 23/09 10h15: Réseaux de tri Todo: bien comprendre le 2.3.2: tri pair-impair sur réseau
linéaire de processeurs.
Mar 30/09 10h15: PRAM 1: introduction; exemples de
diviser-pour-règner sur les listes chaînées; définitions (travail,
efficacité) et simulation (conservation du travail, théorème de Brent).
Jeu 02/10 10h15
(à la place de complexité Turing): PRAM 2: séparation des
modèles, et la fameuse machine à trier de Cole.
Mar 07/10 10h15: Algorithmique sur un anneau de processeurs:
introduction, algos de diffusion (pipeline, taille des données que
l'on envoie, ...)
Mar 14/10 10h15: Algorithmes sur anneaux: produit
matrice-vecteur, matrice-matrice, et balayage d'images.
Mar 21/10 10h15: Bilan sur les topologies virtuelles, les
implémentations distribuées vs centralisées, l'algorithmique sur
anneaux. Survol des réseaux d'interconnections et de différents modèles
de communications. Chemins et routage dans un hypercube.
Mar 28/10 10h15: Partiel
Mar 04/11 10h15: Plongement d'anneaux et de tores dans un
hypercube, et communications collectives (broadcast). Ordonnancement
de graphes de tâches (introduction).
Attention pas cours le 11/11!
Mar 18/11 10h15: Ordonnancement de graphes de tâches sans
communications, avec et sans dépendances, avec nombre de processeurs
bornés ou non. Heuristiques de liste.
Mar 25/11 10h15: Implémentation des heuristiques de
liste. Ordonnancement avec communications: NP-complétude du problème
à ressources illimitées et heuristique de Hanen et
Munier. Heuristiques du chemin critique.
Mar 02/12 10h15: Fin de l'ordonnancement: comparaison
d'heuristiques, et heuristiques de clustering. Architectures
systoliques: comment faire un produit de matrices?
Mar 09/12 10h15: Fin du systolique et nids de boucles.