envoi de blocs de tableau 2D en C à l'aide de MPI

Question

Comment envoyez-vous des blocs de tableaux 2D à différents processeurs? Supposons que la taille du tableau 2D soit 400x400 et que je souhaite envoyer des blocs de tailles 100X100 à différents processeurs. L'idée est que chaque processeur effectue un calcul sur son bloc séparé et renvoie son résultat au premier processeur pour obtenir le résultat final.
J'utilise MPI dans les programmes C.

Answer 1

Permettez-moi de commencer par dire que vous n'avez généralement pas vraiment envie de le faire - d'éparpillement et de recueillir d'énormes blocs de données à partir de certains "maîtres" du processus. Normalement, vous voulez que chaque tâche d'être haletant loin à sa propre pièce du puzzle, et vous devez vous efforcer de ne jamais avoir un processeur besoin d'une "vision globale" de l'ensemble des données; dès que vous avez besoin que, vous pouvez limiter l'évolutivité et la taille du problème. Si vous êtes en train de faire ce pour les I/O - l'on lit les données, puis la diffuse, rassemble ensuite en arrière pour l'écriture, vous aurez envie finalement de regarder dans MPI-IO.

Arriver à votre question, bien que, MPI a de très jolies manières de s'en sortir arbitraire des données de la mémoire, et la ventilation/la collecte et à partir d'un ensemble de processeurs. Malheureusement, cela suppose un certain nombre de MPI concepts - MPI Types, les étendues et les opérations collectives. Beaucoup les idées de base sont abordés dans la réponse à cette question -- MPI_Type_create_subarray et MPI_Gather .

Mise à jour - Dans la lumière froide du jour, c'est beaucoup de code et pas beaucoup d'explications. Alors, permettez-moi de m'étendre un peu.

Considérons un 1d entier tableau global de la tâche 0 a que vous voulez distribuer un certain nombre de tâches MPI, afin qu'ils reçoivent chacun un morceau dans leur tableau. Disons que vous disposez de 4 tâches, et le tableau global est - [01234567]. Vous pourriez avoir de la tâche 0 envoyer quatre messages (y compris à lui-même) pour les distribuer, et quand il est temps de ré-assembler, de recevoir quatre messages de faisceau de retour ensemble; mais que devient évidemment beaucoup de temps à un grand nombre de processus. Il y a des routines optimisées pour ces sortes d'opérations - scatter/gather opérations. Donc dans ce cas 1d, vous feriez quelque chose comme ceci:

int global[8];   /* only task 0 has this */
int local[2];    /* everyone has this */
const int root = 0;   /* the processor with the initial global data */

if (rank == root) {
   for (int i=0; i<7; i++) global[i] = i;
}

MPI_Scatter(global, 2, MPI_INT,      /* send everyone 2 ints from global */
            local,  2, MPI_INT,      /* each proc receives 2 ints into local */
            root, MPI_COMM_WORLD);   /* sending process is root, all procs in */
                                     /* MPI_COMM_WORLD participate */

Après cela, les processeurs de données ressemblerait

task 0:  local:[01]  global: [01234567]
task 1:  local:[23]  global: [garbage-]
task 2:  local:[45]  global: [garbage-]
task 3:  local:[67]  global: [garbage-]

Qui est, l'éparpillement opération prend le tableau global et envoie contiguë 2-int morceaux de tous les processeurs.

Pour ré-assembler la matrice, nous utilisons l' MPI_Gather() opération, qui fonctionne exactement de la même chose mais en sens inverse:

for (int i=0; i<2; i++) 
   local[i] = local[i] + rank;

MPI_Gather(local,  2, MPI_INT,      /* everyone sends 2 ints from local */
           global, 2, MPI_INT,      /* root receives 2 ints each proc into global */
           root, MPI_COMM_WORLD);   /* recv'ing process is root, all procs in */
                                    /* MPI_COMM_WORLD participate */

et maintenant l'apparence des données

task 0:  local:[01]  global: [0134679a]
task 1:  local:[34]  global: [garbage-]
task 2:  local:[67]  global: [garbage-]
task 3:  local:[9a]  global: [garbage-]

Recueillir les données de retour, et ici est un 10 parce que je ne pensais pas que ma mise en forme par lui dès le démarrage de cet exemple.

Qu'advient-il si le nombre de points de données n'a pas de répartir uniformément le nombre de processus, et nous avons besoin d'envoyer un nombre différent d'éléments pour chaque processus? Ensuite, vous avez besoin d'une version généralisée de dispersion, MPI_Scatterv(), ce qui vous permet de spécifier le compte pour chaque processeur, et les déplacements -- où dans le tableau global ce morceau de données commence. Donc, disons que vous avez un tableau de caractères [abcdefghi] avec 9 caractères, et vous allez attribuer chaque processus de deux caractères à l'exception du dernier, qui a obtenu trois. Puis vous auriez besoin

char global[9];   /* only task 0 has this */
char local[3]={'-','-','-'};    /* everyone has this */
int  mynum;                     /* how many items */
const int root = 0;   /* the processor with the initial global data */

if (rank == 0) {
   for (int i=0; i<8; i++) global[i] = 'a'+i;
}

int counts[4] = {2,2,2,3};   /* how many pieces of data everyone has */
mynum = counts[rank];
int displs[4] = {0,2,4,6};   /* the starting point of everyone's data */
                             /* in the global array */

MPI_Scatterv(global, counts, displs, /* proc i gets counts[i] pts from displs[i] */
            MPI_INT,      
            local, mynum, MPI_INT;   /* I'm receiving mynum MPI_INTs into local */
            root, MPI_COMM_WORLD);

Maintenant l'apparence des données

task 0:  local:[ab-]  global: [abcdefghi]
task 1:  local:[cd-]  global: [garbage--]
task 2:  local:[ef-]  global: [garbage--]
task 3:  local:[ghi]  global: [garbage--]

Vous avez maintenant utilisé scatterv à distribuer de l'irrégularité des quantités de données. Le déplacement dans chaque cas est de deux*rang (mesurée en caractères; le déplacement est dans l'unité des types d'être envoyé pour un scatter ou reçu pour recueillir; il n'est pas généralement en octets ou quelque chose) depuis le début de la matrice, et les comtes sont {2,2,2,3}. Si elle avait été le premier processeur, nous voulions avoir 3 personnages, nous avons fixé compte={3,2,2,2} et les déplacements auraient été {0,3,5,7}. Gatherv nouveau fonctionne exactement de la même, mais l'inverse; les comtes et les displs des tableaux restent les mêmes.

Maintenant, pour la 2D, c'est un peu plus compliqué. Si nous voulons envoyer 2d sublocks d'un tableau 2d, les données que nous envoyons désormais plus est contiguë. Si nous envoyons des (dis) 3x3 subblocks d'un 6x6 tableau à 4 processeurs, les données que nous envoyons a des trous:

2D Array

   ---------
   |000|111|
   |000|111|
   |000|111|
   |---+---|
   |222|333|
   |222|333|
   |222|333|
   ---------

Actual layout in memory

   [000111000111000111222333222333222333]

(Notez que tous les high-performance computing s'agit de comprendre la disposition des données dans la mémoire.)

Si nous voulons envoyer les données, qui sont marquées "1" à la tâche 1, nous avons besoin de sauter trois valeurs, l'envoi de trois valeurs, sautez trois valeurs, l'envoi de trois valeurs, sautez trois valeurs, l'envoi de trois valeurs. Une deuxième complication est l'endroit où les sous-régions d'arrêter et de commencer; a noter que la région "1" n'est pas le début où la région "0" s'arrête après le dernier élément de la région "0", le prochain emplacement de mémoire est en cours-chemin à travers la région "1".

Nous allons aborder la mise en page en premier lieu le problème - comment sortir juste les données que nous voulons envoyer. Nous avons toujours pu il suffit de copier tous les "0" de la région de données à l'autre, contiguë tableau, et l'envoyer; si nous l'avions prévu de sortir assez attentivement, on pourrait même le faire de telle manière que l'on pourrait appeler MPI_Scatter sur les résultats. Mais nous préférons ne pas avoir à transposer l'ensemble de notre structure de données principal de cette manière.

Jusqu'à présent, tous les MPI types de données que nous avons utilisées sont simples - MPI_INT spécifie (dire) de 4 octets dans une rangée. Cependant, MPI vous permet de créer vos propres types de données qui décrivent arbitrairement complexes de données mises en mémoire. Et ce cas -- rectangulaire sous-régions d'un tableau -- est assez courant qu'il y a un appel spécifique pour cela. Pour les 2 dimensions cas, nous sommes en train de décrire ci-dessus,

    MPI_Datatype newtype;
    int sizes[2]    = {6,6};  /* size of global array */
    int subsizes[2] = {3,3};  /* size of sub-region */
    int starts[2]   = {0,0};  /* let's say we're looking at region "0",
                                 which begins at index [0,0] */

    MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_INT, &newtype);
    MPI_Type_commit(&newtype);

Cela crée un type qui prend tout de la région "0" dans le tableau global; nous pourrions envoyer juste ce morceau de données à un autre processeur

    MPI_Send(&(global[0][0]), 1, newtype, dest, tag, MPI_COMM_WORLD);  /* region "0" */

et le processus de réception peut recevoir dans un tableau. Notez que le processus de réception, s'il ne la reçoit dans une matrice 3x3, peut pas décrire ce qu'il reçoit comme un type d' newtype; qui n'est plus décrit la disposition de la mémoire. Au lieu de cela, c'est juste de la réception d'un bloc de 3*3 = 9 entiers:

    MPI_Recv(&(local[0][0]), 3*3, MPI_INT, 0, tag, MPI_COMM_WORLD);

Notez que nous pourrions le faire pour d'autres sous-régions, soit par la création d'un type différent (avec différents start tableau) pour les autres blocs, ou tout simplement par l'envoi au point de départ du bloc particulier:

    MPI_Send(&(global[0][3]), 1, newtype, dest, tag, MPI_COMM_WORLD);  /* region "1" */
    MPI_Send(&(global[3][0]), 1, newtype, dest, tag, MPI_COMM_WORLD);  /* region "2" */
    MPI_Send(&(global[3][3]), 1, newtype, dest, tag, MPI_COMM_WORLD);  /* region "3" */

Enfin, notez que nous avons besoin de global et de local pour être contigus des morceaux de mémoire, ici, c'est, &(global[0][0]) et &(local[0][0]) (ou, de manière équivalente, *global et *local point contiguës, 6*6 et 3*3 morceaux de mémoire, qui n'est pas garanti par la manière habituelle de l'allocation dynamique multi-d des tableaux. Il est montré comment, ci-dessous.

Maintenant que nous comprenons comment spécifier des sous-régions, il n'y a qu'une chose de plus à discuter avant d'utiliser scatter/gather opérations, et c'est la "taille" de ces types. Nous ne pouvions pas utiliser MPI_Scatter() (ou même scatterv) avec ces types encore, parce que ces types ont une étendue de 16 nombres entiers; c'est, où elle est de 16 entiers après le début -- et où ils ne s'alignent pas bien avec le prochain bloc commence, donc on ne peut pas utiliser scatter - il serait de choisir le mauvais endroit pour commencer à envoyer des données à la prochaine processeur.

Bien sûr, on peut utiliser MPI_Scatterv() et spécifier les déplacements de nous-mêmes, et c'est ce que nous allons faire - sauf les déplacements sont dans les unités de l'envoyer-type de la taille, et qui ne nous aide pas non plus; les blocs commencent à décalages (0,3,18,21) des entiers à partir du début du tableau global, et le fait qu'un bloc se termine 16 nombres entiers à partir de là que ça commence à ne pas nous laisser exprimer ces déplacements dans des multiples entiers à tous.

Pour faire face à cela, MPI permet de définir l'étendue de la type pour les fins de ces calculs. Il n'a pas tronquer le type; il est juste utilisé pour déterminer d'où l'élément suivant commence le dernier élément. Pour les types comme ceux-ci avec des trous dans eux, il est souvent pratique pour définir l'étendue à quelque chose de plus petit que la distance dans la mémoire à la fin effective de la type.

Nous pouvons définir l'étendue à tout ce qui est commode pour nous. Nous pourrions nous contenter de faire de la mesure 1 entier, puis définissez les déplacements dans les unités d'entiers. Dans ce cas, si, j'aime le jeu de la mesure à 3 entiers - de la taille d'une sous-ligne - de cette façon, le bloc "1" commence immédiatement après le bloc "0", et le bloc de "3" commence immédiatement après le bloc "2". Malheureusement, il n'a pas assez de travail en tant que bien lors du saut de bloc "2" à bloc "3", mais qui ne peut pas être aidé.

Afin de disperser les subblocks dans ce cas, nous aimerions faire le suivant:

    MPI_Datatype type, resizedtype;
    int sizes[2]    = {6,6};  /* size of global array */
    int subsizes[2] = {3,3};  /* size of sub-region */
    int starts[2]   = {0,0};  /* let's say we're looking at region "0",
                                 which begins at index [0,0] */

    /* as before */
    MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_INT, &type);  
    /* change the extent of the type */
    MPI_Type_create_resized(type, 0, 3*sizeof(int), &resizedtype);
    MPI_Type_commit(&resizedtype);

Ici, nous avons créé le même type de bloc comme avant, mais nous avons redimensionné il; nous n'avons pas changé lorsque le type "commence" (le 0), mais nous avons changé les où elle "se termine" (3 ints). Nous n'avons pas parler de cela avant, mais l' MPI_Type_commit est nécessaire pour être en mesure d'utiliser le type; mais vous ne devez commettre le dernier type que vous utilisez réellement, et non pas toutes les étapes intermédiaires. Vous utilisez MPI_Type_free gratuit le type lorsque vous avez terminé.

Alors maintenant, enfin, nous pouvons scatterv les blocs: les données manipulations ci-dessus sont un peu compliqué, mais une fois que c'est fait, le scatterv semble juste comme avant:

int counts[4] = {1,1,1,1};   /* how many pieces of data everyone has, in units of blocks */
int displs[4] = {0,1,6,7};   /* the starting point of everyone's data */
                             /* in the global array, in block extents */

MPI_Scatterv(global, counts, displs, /* proc i gets counts[i] types from displs[i] */
            resizedtype,      
            local, 3*3, MPI_INT;   /* I'm receiving 3*3 MPI_INTs into local */
            root, MPI_COMM_WORLD);

Et maintenant, nous sommes de fait, après un petit tour de dispersion, de rassembler, et MPI types dérivés.

Un exemple de code qui montre à la fois la recueillir et l'éparpillement de l'opération, avec des tableaux de caractères, de ce qui suit. L'exécution du programme:

$ mpirun -n 4 ./gathervarray
Global array is:
0123456789
3456789012
6789012345
9012345678
2345678901
5678901234
8901234567
1234567890
4567890123
7890123456
Local process on rank 0 is:
|01234|
|34567|
|67890|
|90123|
|23456|
Local process on rank 1 is:
|56789|
|89012|
|12345|
|45678|
|78901|
Local process on rank 2 is:
|56789|
|89012|
|12345|
|45678|
|78901|
Local process on rank 3 is:
|01234|
|34567|
|67890|
|90123|
|23456|
Processed grid:
AAAAABBBBB
AAAAABBBBB
AAAAABBBBB
AAAAABBBBB
AAAAABBBBB
CCCCCDDDDD
CCCCCDDDDD
CCCCCDDDDD
CCCCCDDDDD
CCCCCDDDDD

et le code qui suit.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include "mpi.h"

int malloc2dchar(char ***array, int n, int m) {

    /* allocate the n*m contiguous items */
    char *p = (char *)malloc(n*m*sizeof(char));
    if (!p) return -1;

    /* allocate the row pointers into the memory */
    (*array) = (char **)malloc(n*sizeof(char*));
    if (!(*array)) {
       free(p);
       return -1;
    }

    /* set up the pointers into the contiguous memory */
    for (int i=0; i<n; i++)
       (*array)[i] = &(p[i*m]);

    return 0;
}

int free2dchar(char ***array) {
    /* free the memory - the first element of the array is at the start */
    free(&((*array)[0][0]));

    /* free the pointers into the memory */
    free(*array);

    return 0;
}

int main(int argc, char **argv) {
    char **global, **local;
    const int gridsize=10; // size of grid
    const int procgridsize=2;  // size of process grid
    int rank, size;        // rank of current process and no. of processes

    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);


    if (size != procgridsize*procgridsize) {
        fprintf(stderr,"%s: Only works with np=%d for now\n", argv[0], procgridsize);
        MPI_Abort(MPI_COMM_WORLD,1);
    }


    if (rank == 0) {
        /* fill in the array, and print it */
        malloc2dchar(&global, gridsize, gridsize);
        for (int i=0; i<gridsize; i++) {
            for (int j=0; j<gridsize; j++)
                global[i][j] = '0'+(3*i+j)%10;
        }


        printf("Global array is:\n");
        for (int i=0; i<gridsize; i++) {
            for (int j=0; j<gridsize; j++)
                putchar(global[i][j]);

            printf("\n");
        }
    }

    /* create the local array which we'll process */
    malloc2dchar(&local, gridsize/procgridsize, gridsize/procgridsize);

    /* create a datatype to describe the subarrays of the global array */

    int sizes[2]    = {gridsize, gridsize};         /* global size */
    int subsizes[2] = {gridsize/procgridsize, gridsize/procgridsize};     /* local size */
    int starts[2]   = {0,0};                        /* where this one starts */
    MPI_Datatype type, subarrtype;
    MPI_Type_create_subarray(2, sizes, subsizes, starts, MPI_ORDER_C, MPI_CHAR, &type);
    MPI_Type_create_resized(type, 0, gridsize/procgridsize*sizeof(char), &subarrtype);
    MPI_Type_commit(&subarrtype);

    char *globalptr=NULL;
    if (rank == 0) globalptr = &(global[0][0]);

    /* scatter the array to all processors */
    int sendcounts[procgridsize*procgridsize];
    int displs[procgridsize*procgridsize];

    if (rank == 0) {
        for (int i=0; i<procgridsize*procgridsize; i++) sendcounts[i] = 1;
        int disp = 0;
        for (int i=0; i<procgridsize; i++) {
            for (int j=0; j<procgridsize; j++) {
                displs[i*procgridsize+j] = disp;
                disp += 1;
            }
            disp += ((gridsize/procgridsize)-1)*procgridsize;
        }
    }


    MPI_Scatterv(globalptr, sendcounts, displs, subarrtype, &(local[0][0]),
                 gridsize*gridsize/(procgridsize*procgridsize), MPI_CHAR,
                 0, MPI_COMM_WORLD);

    /* now all processors print their local data: */

    for (int p=0; p<size; p++) {
        if (rank == p) {
            printf("Local process on rank %d is:\n", rank);
            for (int i=0; i<gridsize/procgridsize; i++) {
                putchar('|');
                for (int j=0; j<gridsize/procgridsize; j++) {
                    putchar(local[i][j]);
                }
                printf("|\n");
            }
        }
        MPI_Barrier(MPI_COMM_WORLD);
    }

    /* now each processor has its local array, and can process it */
    for (int i=0; i<gridsize/procgridsize; i++) {
        for (int j=0; j<gridsize/procgridsize; j++) {
            local[i][j] = 'A' + rank;
        }
    }

    /* it all goes back to process 0 */
    MPI_Gatherv(&(local[0][0]), gridsize*gridsize/(procgridsize*procgridsize),  MPI_CHAR,
                 globalptr, sendcounts, displs, subarrtype,
                 0, MPI_COMM_WORLD);

    /* don't need the local data anymore */
    free2dchar(&local);

    /* or the MPI data type */
    MPI_Type_free(&subarrtype);

    if (rank == 0) {
        printf("Processed grid:\n");
        for (int i=0; i<gridsize; i++) {
            for (int j=0; j<gridsize; j++) {
                putchar(global[i][j]);
            }
            printf("\n");
        }

        free2dchar(&global);
    }


    MPI_Finalize();

    return 0;
}