TD et TP du Cours Algorithmique Parallèle  
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




Last modification : 2008-09-22 11:07:25 Loris.MYNAME@ens-lyon.fr View source.