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

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?

• 1. MPI has no global data. 2. If you want to construct that list on one process, use MPI_Gather. 3. What do you mean "use the list for MPI_Irecv"? Nov 23, 2022 at 21:41
• I needed this map for tagging while MPI send and receive. Nov 24, 2022 at 7:31

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.

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>

}

return N-1;
} else{
}
}

int main() {

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

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.