#use wml::std::lang
#use wml::fmt::isolatin

#include <menu-item.wml>
#include <bibstyle.wml>
#include <banner.wml>  title="Algo. Parallèle" path="enseignement/"
<br>
<center>
<table border=0 cellspacing=0 cellpadding=5 width="98%">
<tr><td>
<frame title="TD et TP du Cours Algorithmique Parallèle">
<br>
<dl>
<b> TD1 : Réseaux de tri</b>
<dd> Principe du 0-1, Tri bitonique, Tri-Serpent. <a href="algo-par/td1.pdf">sujet</a> ou <a href="algo-par/td1.corr.pdf">correction</a>
</dd>
</dl><br>
<dl>
<b> TD2 : P-RAM</b>
<dd> Sélection dans une liste, Tri par base, Extraction de composante connexe (début).
  <a href="algo-par/td2.pdf">sujet</a> (<a href="algo-par/td2.eng.pdf">english version</a>) ou <a href="algo-par/td2.corr.pdf">correction</a>
</dd>
</dl>
<br>
<dl>
<b> TD3 : P-RAM et anneaux de processeurs</b>
<dd> Fin de l'extraction de composante connexe, rotations de Givens et facteur d'accélération:
  <a href="algo-par/td3.pdf">sujet</a>  ou <a href="algo-par/td3.corr.pdf">correction</a>
</dd>
</dl>
<br>
<dl>
<b> TD4 (TP) : Simulation de communications collectives</b>
<dd> Implémentation du All-To-All sur un anneau de processeurs, puis sur un hypercube:
  <a href="algo-par/td4.pdf">sujet</a>, <a href="algo-par/td4-src.tgz">archive contenant le canevas du TP</a>, documentation sur <a href="simgrid/">SimGrid</a>
</dd>
</dl>
<br>
<dl>
<b> TD5 (TP) : Communicateurs et produit matriciel en MPI</b>
<dd> Produit de matrice par double diffusion avec MPI:
  <a href="algo-par/td5.pdf">sujet</a>, <a href="algo-par/td5-src.tgz">archive contenant le canevas du TP</a>, 
  <a href="http://www-unix.mcs.anl.gov/mpi/www"/>documentation sur MPI</a>, sur l'<a href="http://www-unix.mcs.anl.gov/mpi/mpich/">implémentation MPICH</a> 
</dd>
</dl>
<br>
<dl>
<b> TD6 : Révision - PRAM, anneaux et grilles de processeurs</b>
<dd>  <a href="algo-par/td6.pdf">sujet</a>
</dl>
<br>
<dl>
<b> TD7 : Correction du partiel et Ordonnancement sans communication</b>
<dd> <a href="algo-par/td7.pdf">sujet</a>
</dd>
</dl>
<br>
<dl>
<b> TD8 (TP) : Utilisation de processus légers</b>
<dd> On reprend le produit de matrices par double diffusion en MPI du TD5, et on essaye de l'optimiser en
 effecutant un recouvrement calculs/communications en utilisant des <I>threads</I>: 
<a href="algo-par/td8.pdf">sujet</a>. Voir la documentation MPI ci-dessus.
</dd>
</dl>
<br>
<dl>
<b> DM : Heuristiques d'ordonnancement de tâches indépendantes</b>
<dd> Simulation d'un ordonnancement maître-esclaves sur plate-forme hétérogène: 
<a href="algo-par/dm_sujet.pdf">sujet</a> et <a href="algo-par/dm-src.tgz">archive</a> contenant le canevas du programme.<br>
La documentation de SimGrid est disponible <a href="simgrid/">ici</a>.<br>
Si vous souhaitez travailler ailleurs qu'en salle info, vous pouvez également installer SimGrid sur votre machine, 
en le téléchargeant <a href="http://gcl.ucsd.edu/simgrid/dl/">ici</a>.<br>
Pour ceux qui n'était pas au TP SimGrid, n'oubliez pas d'initialiser correctement les variables de votre shell, pour pouvoir utiliser la version de SimGrid qui est sur mon compte. Par exemple, rajouter à votre ficher .bashrc la ligne suivante:<br>
<tt>
   export LD_LIBRARY_PATH=\$LD_LIBRARY_PATH:/home/lmarchal/lib
</tt>

<br><br>
<font size="+1">Attention, une erreur s'est glissée dans le sujet !</font><br>
Dans le fichier <tt>sched_struct.c</tt>, lignes 122 à 125 (dans la fonction sched_master.c), il fallait lire:<br><br>
<tt>
   PRINT_MESSAGE<br>
   	("Received \"%s\" from \"%s\". Here is its computing power : %f and its bandwidth : %f \n",<br>
   	 request->name, MSG_host_get_name(slave), power, bandwidth);<br>
</tt>
<br>
(il manquait l'argument <tt>bandwidth</tt>, l'archive est maintenant corrigée.)<br>
Désolé pour ceux qui ont perdu du temps sur ce bug !
<br>


<br><br><b><font size="+1">FAQ </font>(les questions que j'ai reçues au sujet du DM):</b><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b>
Que signifie à la question 6 le "parallélisme dans les comm" ? Ne
peut-il pas y avoir plusieurs comm simultanées dans les questions
précédentes ? 
</b></I><br>
D'abord, pour qu'il y ait plusieurs communications simultanées, il
faut que le maître soit capables de les prendre en charge, ce qui
n'est a priori pas le cas: les communications sont bloquantes et il ne
possède pas plusieurs threads pour effectuer plusieurs
communications. 
D'autre part, même si le maître est capable d'effectuer 2 envois
simultanés, ceux-ci vont entrer en conflit dans le lien de
communication qui relie le maître au reste de la plateforme. 
<br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b> engorgement = f(date)<br>
bande passante = f(engorgement) <br>
 durée de comm = f(bande passante, distance)<br>
 Dès lors la durée de comm dépend de la date; quel sens cela a-t-il
 de faire un envoi préliminaire pour tester la durée de comm ? <br>
</b></I>
<br>
Si tu fais un envoi préliminaire pour tester la durée de la comm, dans
ce cas c'est la date de cette envoi préliminaire qui intervient dans
ton équation:<br>
          engorgement = f(date)<br>
Effectivement, les conditions du réseau lors de ce test induisent un
biais sur la mesure de la durée de la comm. À moins de concevoir un
algorithme complexe pour tester les durées des communications vers
chaque esclave, vous ne pourrez pas vous affranchir de ce
biais. Ensuite, tout dépend de la valeur que vous donnez à cette
mesure: mesure exacte, ou bien approximation de la durée nécessaire à
une communication, ou encore durée nécessaire pour effectuer la
communication dans des conditions d'engorgement du réseau...
<br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b>
Le routage est-il fixé une fois pour toutes ?
</b></I><br>
oui, c'est la partie "ROUTES" du fichier "platform.txt"
<br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b>
 Que signifie le champ bandwidth pour une requête ? (est-ce le
 minimum des bandwidths des liens empruntés par la route ? est-ce la
 durée de comm mesurée ?) 
</b></I><br>
Ce champ est une simple indication de ce que vous pourriez faire pour
que le maître possède des informations sur ses esclaves: ce champ
n'est pas initialisé, à vous de vous en servir comme bon vous
semblera, vous pouvez également le supprimer et utiliser d'autres noms
de champs.
<br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<i><b>Comment utiliser les tables de hashage ?</i><br>
Voir une petite description des fonctions de <tt>tbx_hashtable.h</tt> <a
href="hashtable/">ici</a></b><br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<i><b>Les canaux de communication tels que GENERAL_CHANNEL peuvent-ils être
 empruntés par plusieurs messages à la fois ? Si oui, sont-ils des FIFOs ?<br>
Comment faire pour rajouter des canaux de communication ?</i></b><br>

Oui, les canaux peuvent être emprûntés par plusieurs messages à la
fois et se comportent comme des FIFOs. Par exemple, tous les esclaves
peuvent envoyer leur messages sur le canal '<tt>REQUEST_CHANNEL</tt>' du
maitre, qui les récupère dans l'ordre de leur arrivée avec
<tt>MSG_task_get</tt>.

Pour rajouter des canaux de communication, il suffit de modifier la
définition du type <tt>channel_t</tt> dans <tt>sched_strut.h,</tt> par exemple:<br>
<tt>
 typedef enum {<br>
     REQUEST_CHANNEL = 0,<br>
     GENERAL_CHANNEL,<br>
     MY_NEW_CHANNEL,<br>
     MAX_CHANNEL<br>
 } channel_t;<br>
</tt><br>
Attention: prenez garde de toujours garder <tt>MAX_CHANNEL</tt> à la fin de la
définition, dont la valeur sera alors égal au nombre de canaux
réellement utilisés. Cette valeur est utilisée au tout début, lors de
l'initialisation de MSG, dans <tt>mslave.c</tt> :<br>
<tt>
   MSG_set_channel_number(MAX_CHANNEL);
</tt>
<br><br><i>(Vous pourriez également calculer à la main le nombre de canaux que
vous utilisez, ou même mettre un majorant:</i><br>
<tt>
   MSG_set_channel_number(50);
</tt><br>
<i>mais c'est plus pratique d'utiliser MAX_CHANNEL comme précédemment,
vous n'avez plus à vous préoccuper du calcul du nombre de canaux.)</i>
<br><br>
<b>NB: le nombre de canaux doit être fixé avant la création de la
plate-forme, donc vous ne pouvez pas rajouter de canaux de façon
dynamique au cours de l'exécution.</b><br>

<br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b>
J'essaye de modifier le fichier deployment pour rajouter des machines,
je rajoute donc une ligne "Jean_Yves sched_slave Boivin" par exemple,
mais cette ligne ne semble pas etre prise en compte, vu que la machine
n'apparaît pas dans la simulation....Y'a t'il un autre fichier à
modifier ?
</I></b><br>
non, c'est la bonne méthode, il suffit de rajouter cette ligne pour
que ça marche... mais il faut impérativement terminer la ligne par un
retour-charriot, sinon le parseur ne la prend pas en compte !
<br><br><br>

<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b>
Que signifie et quand est-ce que surgis ce message d'erreur ?<br>
[msg/msg_task.c , __MSG_task_check : 158] Simulator Data uninitialized <br>
</b></I><br>

ça veut dire que tu fais des cochonneries avec les taches, par exemple
que tu tentes d'ordonnancer (avec task_put) une tache que tu n'as pas
créé avec MSG_taask_create<br>

ou bien, pire, que tu es allé tapé (à cause d'un débordement de
tableau, ou autre pointeur perdu) dans les données de MSG, et que tu
as écrasé ses infos...<br><br>
<b> NB: si vous voulez en savoir plus, il suffit d'aller voir dans le fichier <tt>msg/msg_task.c</tt> du répertoire des sources de simgrid, qui est sur mon compte dans <tt>/home/lmarchal/simgrid-2.18.5/src</tt></b>

<br><br>
<img src="Utils/Icons/folder-closed.gif" border=0> 
<I><b>Le fichier de déploiement est censé contenir les informations relatives à la taille des tâches; alors pourquoi redéfinit-on task_computation_amount ... au début de sched_struct.c ?</b></I><br>
Effectivement, ces quantités sont prédéfinies au début du fichier, et
elles sont ensuite initialisées avec les valeurs des paramètres du
fichier de deploiement. Donc les valeurs initiales ne sont pas
utilisées...<br>
désolé pour ce manque de cohérence :)
<br><br>
</dd>
</dl>
<br>
</frame>

</td></tr>
</table>
</center>