Leçons de niveau 17

Utilisateur:Kabyhaswell/ProgrammationParallèleMPI/Exercices/Communications de base

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Communications de base
Image logo représentative de la faculté
Exercices no2
Leçon : ProgrammationParallèleMPI
Chapitre du cours : Communiquer_entre_processus_:_point-à-point

Ces exercices sont de niveau 17.

Exo préc. :Modèle_d'exécution
Exo suiv. :TODO
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Exercice : Communications de base
Kabyhaswell/ProgrammationParallèleMPI/Exercices/Communications de base
 », n'a pu être restituée correctement ci-dessus.



Envois et réceptions simples[modifier | modifier le wikicode]

Exercice 2-1 : aller-retour[modifier | modifier le wikicode]

Écrivez un programme qui fonctionne avec un nombre quelconque de processus et dans lequel :

  • le processus 0 tire un nombre entier aléatoirement et l’affiche
  • le processus 0 envoie ce nombre au processus 1
  • le processus 1 incrémente ce nombre
  • le processus 1 envoie le résultat au processus 0
  • le processus 0 affiche le résultat

Exercice 2-2 : ping-pong[modifier | modifier le wikicode]

Écrivez un programme qui fonctionne avec un nombre quelconque et dans lequel les processus 0 et 1 s'échangent un tableau de nombres à virgule flottante. La taille du tableau est passée en argument du programme.

  • Ce tableau est initialisé sur le rank 0 avec des valeurs aléatoires entre 0 et 1000.
  • Le processus de rang 0 l’envoie au processus de rang 1.
  • Le processus de rang 1 multiplie toutes les valeurs par 2 et renvoie le résultat au processus de rang 0.

Modifiez maintenant votre programme pour que cet échange se fasse 50 fois.

Exercice 2-3 : cherchez l’erreur[modifier | modifier le wikicode]

Considérez le programme suivant. Quel est le problème ?

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h> /* pour getpid() */
#include <mpi.h>

#define TAG 42

int main( int argc, char** argv ) {
    int rank, token;
    MPI_Status status;
    
    MPI_Init( &argc, &argv );
    MPI_Comm_rank( MPI_COMM_WORLD, &rank );
    if( rank > 1 ) { /* Seuls les processus 0 et 1 participent */
        MPI_Finalize();
        return EXIT_SUCCESS;
    }

    srand( getpid() );
    token = rand();
    MPI_Send( &token, 1, MPI_INT, rank ^ 0x1, TAG, MPI_COMM_WORLD );
    MPI_Recv( &token, 1, MPI_INT, rank ^ 0x1, TAG, MPI_COMM_WORLD, &status );

    MPI_Finalize();
    return EXIT_SUCCESS;
}

En réalité, ce programme fonctionne-t-il ? Pourquoi ?

Modifiez le programme pour utiliser un MPI_Ssend à la place du MPI_Send. Le programme fonctionne-t-il ?

Modifiez ce programme pour qu'il fonctionne.

Exercice 2-4 : anneau à jeton[modifier | modifier le wikicode]

Le but de cet exercice est de faire circuler un anneau entre les processus. Le jeton est injecté par le processus de rang 0 et initialisé à la valeur 0. Chaque processus qui reçoit l’anneau de son voisin de rang inférieur l'incrémente et le transmet à son voisin de rang supérieur. Pour des raisons de simplicité, la rotation s'arrête au rang 1, quand le processus de rang 1 arrête de transmettre le jeton et affiche sa valeur. Le jeton doit faire un nombre arbitraire de tours de l’anneau, par exemple 16.

Vous pourrez par exemple, dans un premier temps, utiliser MPI_Ssend pour débugger.

Exercice 2-5 : comptage des nombres premiers[modifier | modifier le wikicode]

Le but de cet exercice est de compter le nombre de nombres premiers dans un intervalle. Pour cela, nous allons utiliser un algorithme très naïf qui compte le nombre de nombres premiers dans un intervalle, et découper l'intervalle en sous-intervalles. Chaque processus va calculer le nombre de nombres premiers dans un sous-intervalle, et le processus de rang 0 va sommer ces nombres pour avoir le nombre de nombres premiers dans l'intervalle global. C'est une méthode de type "diviser pour mieux régner".

La fonction de comptage des nombres premiers que nous allons utiliser est la suivante.

/* Retourne le nombre de nombres premiers dans l'intervalle [ from; to [ */

int nbPremiers( int from, int to ) {
    int i, j, nb, estPremier;

    nb = 0;
    if( from < 2 ) from = 2;
    for( i = from; i < to; i++ ) {
        estPremier = 1;
        for( j = 2 ; j < i ; j++ ) {
            if( 0 == (i % j) ) {
                estPremier = 0;
                break;
            }            
        }
        nb += estPremier ;
    } 
    return nb;
}

Le processus de rang 0 coordonne le calcul : nous allons l'appeler le processus maître. Les autres processus ne font que calculer ce que le maître leur dit de calculer. Ce sont les processus esclaves. On peut également les appeler les processus travailleurs, bien que cette dénomination, utilisée en anglais (master/worker) ne soit utilisée que rarement en français.

Écrivez un programme MPI où le processus de rang 0 appelle une fonction maitre et les autres processus appellent une fonction esclave.

Dans un premier temps, le processus 0 découpe l'intervalle en autant de tranches de taille égale qu'il y a de processus. Pour chaque esclave, il calcule les bornes de l'intervalle sur lequel il va travailler, et il lui envoie ces bornes. Il lui envoie donc un tableau de deux entiers. Il garde ensuite la fin de l’intervalle pour lui.

Implémentez vos fonctions maitre et esclave pour que :

  • pour chaque processus esclave, le processus maître calcule les bornes de l'intervalle sur lequel il va travailler
  • le processus maître lui envoie les bornes calculées en une seule communication
  • le processus esclave reçoit ces bornes

Chaque processus a maintenant les bornes de l'intervalle sur lequel il va travailler : appelez la fonction qui compte le nombre de nombres premiers dans cet intervalle. Une fois qu'il a le résultat, chaque processus l’envoie au processus maître, qui se charge de les additionner et d'afficher le résultat. N'oubliez pas que le processus maître a lui aussi un calcul à faire.

En regardant la fonction nbPremiers, vous pouvez constater que le temps de calcul n’est pas le même si on travail sur des petits nombres et sur des grands nombres : en effet, même si la boucle extérieure traite le même nombre d'éléments, la boucle intérieur traite un nombre d'éléments qui dépend de la valeur des bornes de l’intervalle. Ainsi, avec l'approche que nous venons de voir, les processus qui ont la fin de l’intervalle ont beaucoup plus de calcul à faire que ceux qui ont le début de l'intervalle. La charge est donc déséquilibrée entre les processus.

On peut modifier l’approche du schéma maître-esclave pour qu'il équilibre mieux la charge. Le maître découpe l'intervalle de travail en plus petits sous-intervalles, et il renvoie du travail aux esclaves dès qu'ils ont terminé. Dans ce schéma, ce sont les esclaves qui demandent du travail.

Écrivez de nouvelles fonctions maitre et esclave dans lesquelles :

  • chaque esclave envoie une demande de travail, c'est-à-dire qu'il effectue une communication vers le maître en lui envoyant un entier quelconque avec un tag particulier. Ici, on utilisera les tag à des fins de signalisation.
  • le maître reçoit ces messages et affiche l'expéditeur et le tag du message. Attention, les messages veulent arriver dans n’importe quel ordre : il faut être capable de les traiter quelque soit l'esclave qui a envoyé le message.

Le processus maître calcule les bornes de l’intervalle sur lequel chaque esclave va travailler. Ici, comme les calculs les plus longs sont faits en fin d'intervalle, on va parcourir l'intervalle à reculons : si chaque intervalle est de longueur SLICE et qu'on veut aller jusqu'à MAX, le premier intervalle envoyé sera [MAX-SLICE, MAX[, le suivant sera [MAX-1*SLICE, MAX-SLICE[, et ainsi de suite.

Modifiez vos fonctions maitre et esclave pour qu'à chaque esclave qui demande du travail, le maître envoie les bornes d'un intervalle. Cet envoi se fait avec un tag particulier. L'esclave reçoit les bornes de cet intervalle, teste la valeur du tag et, si c'est bien ce tag qu'il reçoit, appelle la fonction de comptage des nombres premiers dans cet intervalle.

Les esclaves ont fait un calcul : ils envoient le résultat au maître, qui additionne tous les résultats qu'il a reçus. Ajoutez à vos fonctions maitre et esclave l'envoi du résultat. Ici, c'est une communication différente de la communication initiale où chaque esclave demande du travail : la donnée transmise va être utilisée, donc ce message ne doit pas être traité de la même façon. Utiliser donc un tag différent, et le maître va distinguer ces messages en utilisant leur tag.

Pour le moment, le maître a envoyé du travail exactement une fois à chaque esclave. Modifiez vos deux fonctions pour que le maître envoie du travail tant que l'intervalle n'est pas entièrement parcouru. Une fois qu'il a tout envoyé, il renvoie un message d'un autre type aux esclaves afin de leur signifier la fin du travail. Vous utiliserez un autre tag pour cela.

Communications non-bloquantes[modifier | modifier le wikicode]