How to use MPI_Gatherv for collecting strings of diiferent length from different processor including master node?

Question

I am trying to collect different strings of different length from all processors (including the master node) into a single string (array of characters) at the master node. Here is the prototype for MPI_Gatherv:

int MPI_Gatherv(const void *sendbuf, int sendcount, MPI_Datatype sendtype,
            void *recvbuf, const int *recvcounts, const int *displs,
            MPI_Datatype recvtype, int root, MPI_Comm comm)**.

I am unable to define some parameters like recvbuf,recvcounts and displs. Could any one provide source code example in C for this?

Solution 1

As has been pointed out, there are lots of examples of using MPI_Gatherv, including here on stack overflow; an answer which starts off describing how scatter and gather work, and then how the scatterv/gatherv variants extend that, can be found here.

Crucially, for the simpler Gather operation, where every chunk is of the same size, the MPI library can easily precompute where each chunk should go in the final compiled array; in the more general gatherv operation, where this is less clear, you have the option - in fact, the requirement - to spell out exactly where each item should start.

The only extra complication here is that you're dealing with strings, so you probably don't want everything shoved right together; you'll want extra padding for spaces, and of course a null terminator at the end.

So let's say you have five processes wanting to send strings:

Rank 0: "Hello"    (len=5)
Rank 1: "world!"   (len=6)
Rank 2: "Bonjour"  (len=7)
Rank 3: "le"       (len=2)
Rank 4: "monde!"   (len=6)

You'll want this to be assembled into a global string:

Hello world! Bonjour le monde!\0
          111111111122222222223
0123456789012345678901234567890

recvcounts={5,6,7,2,6};  /* just the lengths */
displs = {0,6,13,21,24}; /* cumulative sum of len+1 for padding */

You can see that displacement 0 is 0, and displacement i is equal to the sum of (recvcounts[j]+1) for j=0..i-1:

   i    count[i]   count[i]+1   displ[i]   displ[i]-displ[i-1]
   ------------------------------------------------------------
   0       5          6           0    
   1       6          7           6                 6
   2       7          8          13                 7
   3       2          3          21                 8
   4       6          7          24                 3

And that's straightforwardly implemented:

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

#define nstrings 5
const char *const strings[nstrings] = {"Hello","world!","Bonjour","le","monde!"};

int main(int argc, char **argv) {

    MPI_Init(&argc, &argv); 

    int rank, size;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    /* Everyone gets a string */    

    int myStringNum = rank % nstrings;
    char *mystring = (char *)strings[myStringNum];
    int mylen = strlen(mystring);

    printf("Rank %d: %s\n", rank, mystring);

    /*
     * Now, we Gather the string lengths to the root process, 
     * so we can create the buffer into which we'll receive the strings
     */

    const int root = 0;
    int *recvcounts = NULL;

    /* Only root has the received data */
    if (rank == root)
        recvcounts = malloc( size * sizeof(int)) ;

    MPI_Gather(&mylen, 1, MPI_INT,
               recvcounts, 1, MPI_INT,
               root, MPI_COMM_WORLD);

    /*
     * Figure out the total length of string, 
     * and displacements for each rank 
     */

    int totlen = 0;
    int *displs = NULL;
    char *totalstring = NULL;

    if (rank == root) {
        displs = malloc( size * sizeof(int) );

        displs[0] = 0;
        totlen += recvcounts[0]+1;

        for (int i=1; i<size; i++) {
           totlen += recvcounts[i]+1;   /* plus one for space or \0 after words */
           displs[i] = displs[i-1] + recvcounts[i-1] + 1;
        }

        /* allocate string, pre-fill with spaces and null terminator */
        totalstring = malloc(totlen * sizeof(char));            
        for (int i=0; i<totlen-1; i++)
            totalstring[i] = ' ';
        totalstring[totlen-1] = '\0';
    }

    /* 
     * Now we have the receive buffer, counts, and displacements, and 
     * can gather the strings 
     */

    MPI_Gatherv(mystring, mylen, MPI_CHAR,
                totalstring, recvcounts, displs, MPI_CHAR,
                root, MPI_COMM_WORLD);


    if (rank == root) {
        printf("%d: <%s>\n", rank, totalstring);
        free(totalstring);
        free(displs);
        free(recvcounts);
    }

    MPI_Finalize();
    return 0;
}

Running gives:

$ mpicc -o gatherstring gatherstring.c -Wall -std=c99
$ mpirun -np 5 ./gatherstring
Rank 0: Hello
Rank 3: le
Rank 4: monde!
Rank 1: world!
Rank 2: Bonjour
0: <Hello world! Bonjour le monde!>

Solution 2

MPI_Gather+MPI_Gatherv requires calculating displacement for all ranks which I find it unnecessary when your strings are of almost similar lengths. Instead, you can use MPI_Allreduce+MPI_Gather with padded receive buffers of strings. The padding is done based on the longest available string which is calculated using MPI_Allreduce. Here is the code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#include <mpi.h>

int main(int argc, char** argv) {
    MPI_Init(NULL, NULL);
    int rank;
    int nranks;
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &nranks);

    srand(time(NULL) + rank);
    int my_len =  (rand() % 10) + 1; // str_len   \in [1, 9]
    int my_char = (rand() % 26) + 65; // str_char \in [65, 90] = [A, Z]

    char my_str[my_len + 1];
    memset(my_str, my_char, my_len);
    my_str[my_len] = '\0';
    printf("rank %d of %d has string=%s with size=%zu\n",
            rank, nranks, my_str, strlen(my_str));

    int max_len = 0;
    MPI_Allreduce(&my_len, &max_len, 1, 
                  MPI_INT, MPI_MAX, MPI_COMM_WORLD); 

    // + 1 for taking account of null pointer at the end ['\n']
    char *my_str_padded[max_len + 1]; 
    memset(my_str_padded, '\0', max_len + 1);
    memcpy(my_str_padded, my_str, my_len);

    char *all_str = NULL;
    if(!rank) {
        int all_len = (max_len + 1) * nranks;
        all_str = malloc(all_len * sizeof(char));   
        memset(all_str, '\0', all_len);
    }

    MPI_Gather(my_str_padded, max_len + 1, MPI_CHAR, 
                     all_str, max_len + 1, MPI_CHAR, 0, MPI_COMM_WORLD);

    if(!rank) {
        char *str_idx = all_str;
        int rank_idx = 0;
        while(*str_idx) {
            printf("rank %d sent string=%s with size=%zu\n", 
                    rank_idx, str_idx, strlen(str_idx));
            str_idx = str_idx + max_len + 1;
            rank_idx++;
        }

    }

    MPI_Finalize();
    return(0);  
}

Have in mind that there is a tradeoff between selecting MPI_Gather+MPI_Gatherv which uses displacement and MPI_AllReduce+MPI_Gather which sometimes uses padding, because the former requires more time for calculating the displacements and the latter requires more storage to align the receive buffers.

I have also benchmarked the two approaches with big string buffers and could not find any significant runtime difference.