#use wml::std::lang
#use wml::fmt::isolatin
#include <menu-item.wml>
#include <bibstyle.wml>
#include <banner.wml> title="Algo. Parallèle" path="enseignement/AlgoPar"
<br>
<center>
<table border=0 cellspacing=0 cellpadding=5 width="98%">
<tr><td>
<frame title="TD et TP du Cours Algorithmique Parallèle">
<table border=0 cellspacing=0 cellpadding=20 width="100%">
<tr valign=top><td valign=top width="100%">
<b> NB: Certains sujets et corrections de TDs sont sur la <a href="http://graal.ens-lyon.fr/~ctedesch/teaching.html">page web de Cédric Tedeschi</a></b><br><br>
<dl>
<b> TD1 : Réseaux de tri</b>
<dd> Principe du 0-1, Tri bitonique, Tri-Serpent. <a href="algo-par/td1-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD5 (TP) : Communications collectives en MPI</b>
<dd> Diffusion et échange total de données avec MPI:
<ul>
<li>
<a href="algo-par/td2-05-mpi.pdf">sujet</a>
<li>
<a href="algo-par/td2-05-src.tgz">archive contenant le canevas du TP</a>
<li>
documentation sur <a href="http://www-unix.mcs.anl.gov/mpi/www"/> MPI</a>
<li>
documentation sur l'<a href="http://www-unix.mcs.anl.gov/mpi/mpich/">implémentation MPICH</a>
</ul>
Voici une proposition de correction du TP (parmi beaucoup d'autres choix valides):<br>
<ul><li>
question 2 : <a href="algo-par/manual_broadcast.html">manual_broadcast.c</a>
<li>
questions 3 à 5 : <a href="algo-par/manual_all2all_fr.html">manual_all2all.c</a>
(the same with english comments: <a href="algo-par/manual_all2all_eng.html">manual_all2all.c</a>)
</ul>
</dd>
</dl>
<br>
<dl>
<b> TD3 : Anneaux de Processeurs et PRAM</b>
<dd> <a href="algo-par/td3-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD4 : PRAM, suite et fin</b>
<dd> <a href="algo-par/td4-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> Révisions :</b>
<dd> Quelques exercices de révisions (dont certains corrigés) <a href="algo-par/revisions-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> DM: simulation à évènements discrets</b>
<dd>
<ul>
<li> <a href="algo-par/dm05.pdf">sujet</a>
<li> génération de distribution homogène : <a href="algo-par/gen_homo.c">fichier C</a> ou
<a href="algo-par/gen_homo.html">version HTML</a>
<li> simulateur séquentiel : <a href="algo-par/simul_seq.c">fichier C</a> ou
<a href="algo-par/simul_seq.html">version HTML</a>
<li> génération de distribution hétérogène: <a href="algo-par/gen_hetero.c">fichier C</a> ou
<a href="algo-par/gen_hetero.html">version HTML</a>
<li> une archive avec tout ça (+ Makefile + exemple d'utilisation) : <a href="algo-par/dm-algo-par-src.tgz">dm-algo-par-src.tgz</a>
</ul>
Si vous avez besoin de précisions, écrivez-moi: <a href="mailto:Loris.Marchal\@ens-lyon.fr">Loris.Marchal\@ens-lyon.fr</a><br>
<br>
<b>F. A. Q.</b><br>
<I>(Je publierais ici vos questions et commentaires)</I><br>
<ul>
<li><p align="justify"> <b>Question 1 :</b>
<I>
"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.</br>
Si deux sardines veulent rentrer dans une même case libre, que se
passe-t-il?</I></br>
Dans la version la plus stricte de la simulation, il faut qu'une
case soit libre dans la configuration au temps <i>t</i> pour qu'un
poisson puisse s'y déplacer au temps <i>t+1</i>. Et si plusieurs
sardines (ou plusieurs requins) veulent se déplacer dans la même
case au temps <i>t+1</i>, 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é.<br>
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. </p>
<li> <b>Bug dans le simulateur séquentiel</b><br>
Ligne 177 du fichier <tt>simul_seq.c</tt>, à la place de:<br>
<tt><FONT COLOR="#B22222">
if ((fish_at_target != NULL) && (fish_at_target->type = SARDINE)) {
</FONT>
</tt><br>
il fallait lire:<br>
<tt><FONT COLOR="#B22222">
if ((fish_at_target != NULL) && (fish_at_target->type == SARDINE)) {
</FONT>
</tt><br>
(C'est déjà corrigé dans les fichiers présents sur cette page)<br><br>
<li> <b>Question 2.</b><br>
<I> 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?</I><br>
Oui, on peut faire ces hypothèses. En pratique, on a <I>n>>p</I>.<br><br>
<li> <b>Question 3.</b><br>
<I>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?</I><br>
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.<br><br>
<li> <b>Question 4.</b><br>
<I>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.<br>
Alors, nous croyons qu'il y a trois possibilités:<br>
a- on peut faire une politique différente à les frontières<br>
b- on doit faire la même politique, sans appliquer du récouvrement<br>
c- on doit faire la même politique, en faisant une autre transmision initiale
avec les requins qui veulent passer
</I><br>
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. <br><br>
<li> <b>Bug dans le simulateur séquentiel et problème dans le Makefile</b><br>
Ligne 20 du fichier <tt>Makefile</tt>, il y a une librairie inutile qui risque de vous gêner à la compilation, donc remplacez<br>
<tt><FONT COLOR="#B22222">
LIBS = -llpk -lm -lfl
</FONT>
</tt><br>
par :<br>
<tt><FONT COLOR="#B22222">
LIBS = -lm -lfl
</FONT>
</tt><br>
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.<br><br>
</ul>
</dl>
<br>
<dl>
<b> TD9 : Ordonnancement</b>
<dd> <a href="algo-par/td9-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD10 : Ordonnancement-2</b>
<dd> <a href="algo-par/td10-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD11 : Ordonnancement pour plates-formes hétérogènes</b>
<dd> <a href="algo-par/td11-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD12 : Nids de Boucles </b>
<dd> <a href="algo-par/td12-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD13 : Pipeline</b>
<dd> <a href="algo-par/td13-05.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD14 : Révisions</b>
<dd> <a href="algo-par/td14-05.pdf">sujet</a>
#, <a href="algo-par/td14-05-corr.pdf">correction (disponible)</a>
</dl>
<br>
<br>
</td></tr>
</table>
</frame>
</td></tr>
</table>
</center>