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?

Warmonger

There are some examples of using MPI_Gatherv() on the mpi-forum. You can call MPI_Gather() to gather the length of each string from each process in in the array recvcounts, compute the displacements as displs[0]=0, displs[i]=displs[i-1]+recvcounts[i-1], allocate enough space for recvbuf, call MPI_Gatherv() and finally set the null terminating character of recvbuf to ensure a valid printable string. – Siphonophore

Answer 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!>

Aberrant

Answer 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.

Blalock

You are comparing MPI_Gather()+MPI_Gatherv() (collect string lengths first, and then the strings) with MPI_Allreduce()+MPI_Gather() (get the max string length and then collect them) that requires extra memory for padding, and might crash (trying to send more data could lead to a buffer overflow). I have hard time believing your approach can be faster even if it does not crash. – Emporium

I've benchamrked both approaches and yes I couldn't find any significant performance gain using MPI_Allreduce+MPI_Gather. About the extra memory, as long as the size of substrings are almost the same and you memset them , this approach yield similar runtime. There're cases that this might not be efficient, e.g., when substring sizes vary a lot. – Blalock

So were you able to find (significant) performance improvement or not ? – Emporium

From my test cases the MPI_Allreduce+GatherGather was 10 ms faster on average (~355.77ms) with substrings of size 1 MB and a little variation at the end to enforce different sizes. Also, we're skipping the for-loop for calculating displacement and ! I believe, there will be cases this answer works even better than MPI_Gather + MPI_Gatherv.. – Blalock