How to define a global index from local index and rank in parallel computing

Question

Suppose I have 4 processes and each process has $n_i, i=0,1,2,3$ elements. In particular, with rank $0$, we have loc indices list $[0,1,\ldots, n_{0}-1]$ and $1$, we have loc indices list $[0,1,\ldots, n_{1}-1]$ and so on.

Now, I want a global list that is a combination of the above local indices. And it should look as follows:

$$[0,1,\ldots,n_{0}-1,n_{0}, \ldots, n_{0}+n_{1}-1,n_{0}+n_{1}, \ldots, n_{0}+n_{1}+n_{2}-1,n_{0}+n_{1}+n_{2}, \ldots, n_{0}+n_{1}+n_{2}+n_{3}-1 ].$$

How to define such a list so that it can be used for MPI_Irecv and MPI_Isend?

Answer 1

To implement what you want, process 1 needs to know $n_0$; process 2 needs to know $n_0+n_1$; and so on. The way to compute this is not done via MPI_Send and MPI_Recv, but by noticing that what you need is a "prefix sum", which is what the MPI_Scan and MPI_Exscan functions provide. Specifically, the when given n_i on each process, the MPI_Exscan function computes $$ \sum_{j=0}^{i-1} n_j, $$ which is exactly what you need to compute the local range of global indices.

Answer 2

Welcome to Scicomp!

If every process knows its thread/rank id, and you have one global rule as to how the region of responsibility of a (constant size) array for a process is calculated, then there is no need to communicate. Every process can calculate its own responsibility. That also means that you can calculate the ranges of all ranks from afar without asking them.

Say you have an array of length N, and number of processes P. Then each rank may simply call the following methods.

C++ MWE (godbolt):

#include <iostream>

constexpr int getMyRangeStart(const int myThreadid,const int noOfThreads,const int N){
     return myThreadid*((N/noOfThreads)); 
}

constexpr int getMyRangeEnd(const int myThreadid,const int noOfThreads,const int N){
    if(myThreadid==(noOfThreads-1)){
        return N-1;
    } else{
        return (myThreadid+1)*((N/noOfThreads))-1; 
    }
}

int main() {

     int N = 33;  //array length
     int P = 4;   //no of threads/ranks

    for(int thread = 0; thread <P; thread++){
         std::cout <<" array range of thread " <<thread << " is from : " << getMyRangeStart(thread,P,N) << " to " << getMyRangeEnd(thread,P,N) << std::endl;
    }
    return 0;
}

The output is as follows:

 array range of thread 0 is from : 0 to 7
 array range of thread 1 is from : 8 to 15
 array range of thread 2 is from : 16 to 23
 array range of thread 3 is from : 24 to 32

Note that you have to handle special cases when your array is not cleanly divisible by your number of threads. Then the region of the thread with the highest thread number may extend a little further.

This appraoch is possible as long as the size of your data array does not change during runtime. If the size changes, then you may either force recalculation of the ranges, or employ more elaborate load balancing.