NB: Certains sujets et corrections de TDs sont sur la page web de Cédric Tedeschi
TD1 : Réseaux de tri
- Principe du 0-1, Tri bitonique, Tri-Serpent. sujet
TD5 (TP) : Communications collectives en MPI
- Diffusion et échange total de données avec MPI:
Voici une proposition de correction du TP (parmi beaucoup d'autres choix valides):
TD3 : Anneaux de Processeurs et PRAM
- sujet
TD4 : PRAM, suite et fin
- sujet
Révisions :
- Quelques exercices de révisions (dont certains corrigés) sujet
DM: simulation à évènements discrets
-
Si vous avez besoin de précisions, écrivez-moi: Loris.Marchal@ens-lyon.fr
F. A. Q.
(Je publierais ici vos questions et commentaires)
-
Question 1 : "Si la case choisie n'est pas libre, elle ne bouge pas" : Ce qui compte c'est qu'elle soit libre avant le mouvement ou après le mouvement de la sardine qui est potentiellement actuellement dedans? Car si elle n'est pas libre mais que le poisson qui est dedans bouge à cette étape, il faut savoir si on considère la case avant le mouvement ou après. Si deux sardines veulent rentrer dans une même case libre, que se passe-t-il? Dans la version la plus stricte de la simulation, il faut qu'une case soit libre dans la configuration au temps t pour qu'un poisson puisse s'y déplacer au temps t+1. Et si plusieurs sardines (ou plusieurs requins) veulent se déplacer dans la même case au temps t+1, on résout les conflits par des règles de priorités (ceux qui viennent du haut ont la priorité, puis ceux de gauche, puis ceux de droite, et enfin ceux du bas), ou bien en choisissant au hasard le mouvement autorisé. Si vous pouvez mettre en oeuvre une telle simulation, c'est très bien. Cependant, on peut également s'autoriser un fonctionnement plus "souple", quoique moins précis: On traite les poissons dans un ordre arbitraire, et au moment du traitement d'un des poissons, on vérifie que la case vers laquelle il veut se déplacer est libre. C'est une telle simulation qui est présentée dans l'exemple séquentiel ci-dessus.
- Bug dans le simulateur séquentiel
Ligne 177 du fichier simul_seq.c, à la place de:
if ((fish_at_target != NULL) && (fish_at_target->type = SARDINE)) {
il fallait lire:
if ((fish_at_target != NULL) && (fish_at_target->type == SARDINE)) {
(C'est déjà corrigé dans les fichiers présents sur cette page)
- Question 2.
Si p est le nombre de processeurs et n x n la taille totale de l'océan, est-ce qu'on peut supposer n>= p?, n>= 2p?
Oui, on peut faire ces hypothèses. En pratique, on a n>>p.
- Question 3.
Pour les transmisions entre deux processeurs, qu'est-ce que c'est mieux,
faire une transmision avec toute une colonne de poissons (car c'est le maximum)
ou de faire deux transmisions, la prémière consistant seulement en un entier
qui donne le nombre de poissons à passer, et le deuxième en donnant les
poissons? c'est quoi le plus vite? on doit prioriser le nombre de données
passées, ou le nombre de transmisions faites?
Je pense que dans notre cas, la latence du réseau est assez rapide, donc
faire un premier transfert avec seulement le nombre de données ne devrait pas
coûter cher, et permet d'économiser du temps pour le second transfert. Ce
n'est qu'une idée et il faudrait tester si c'est bien le cas pour en être
sûr. Mais faites ce qui vous semble le mieux.
- Question 4.
Est-ce que c'est incorrect de faire une politique différente à les
frontières et à l'interieur de chaque océan? pour moi, chaque océan est la
partie de l'océan qui correspond à chaque processeur. Je demande ça parce
qu'il exist un problème: dans la situation dans laquelle un requin veut aller
dans une case où il y à une sardine qui veut partir, l'énoncé de la
pratique dit que le requin doit la manger. Ça doit être suivi, car si ça ne
fut pas comme ça, au traitement du requin, on devrait voir qu'est-ce que la
sardine veut faire, et, si elle veut partir vers une autre direction
différente à celle où il y a le requin, voir si elle peut (peut être qu'il
y aie des autres poissons qui voudraient y aller, à cette case vide, ou peut
être il y a un autre poisson et il faut voir qu'est ce qu'il fait).
Mais, l'énoncé donne aussi des problèmes: dans les frontières, on ne peut
pas suivre l'énoncé. la sardine échape du requin, car, par contre, on
dévrait résoudre touts les movements (en les laissant comme des pétitions de
mouvement en lieu de faire les mouvements définitifs) et après avoir transmi
les frontières, résoudre définitivement. Si on fait ça, le recouvrement du
calcul et des transmisions n'a pas lieu.
Alors, nous croyons qu'il y a trois possibilités:
a- on peut faire une politique différente à les frontières
b- on doit faire la même politique, sans appliquer du récouvrement
c- on doit faire la même politique, en faisant une autre transmision initiale
avec les requins qui veulent passer
Effectivement, le respect des règles aux frontières des zones allouées aux
processeurs est un peu délicat. Comme je l'ai répondu précédemment, les
règles sont adaptables, donc la solution 1 que tu proposes est tout à fait
acceptable: on veut surtout avoir de bonnes performances, et donc utiliser le
recouvrement calcul-communication si possible. La solution 3 est aussi
envisageable, mais elle demande 2 fois plus de communications, donc beaucoup de
synchronisation.
- Bug dans le simulateur séquentiel et problème dans le Makefile
Ligne 20 du fichier Makefile, il y a une librairie inutile qui risque de vous gêner à la compilation, donc remplacez
LIBS = -llpk -lm -lfl
par :
LIBS = -lm -lfl
De même, quelques problèmes du simulateur ont été corrigés sur vos conseils, prenez la nouvelle version si vous voulez une simulation plus réaliste.
TD9 : Ordonnancement
- sujet
TD10 : Ordonnancement-2
- sujet
TD11 : Ordonnancement pour plates-formes hétérogènes
- sujet
TD12 : Nids de Boucles
- sujet
TD13 : Pipeline
- sujet
TD14 : Révisions
- sujet
|
|