How to share work roughly evenly between processes in MPI despite the array_size not being cleanly divisible by the number of processes?

Question

Hi all, I have an array of length N, and I'd like to divide it as best as possible between 'size' processors. N/size has a remainder, e.g. 1000 array elements divided by 7 processes, or 14 processes by 3 processes.

I'm aware of at least a couple of ways of work sharing in MPI, such as:

for (i=rank; i<N;i+=size){ a[i] = DO_SOME_WORK } 

However, this does not divide the array into contiguous chunks, which I'd like to do as I believe is faster for IO reasons.

Another one I'm aware of is:

int count = N / size;
int start = rank * count;
int stop = start + count;

// now perform the loop
int nloops = 0;

for (int i=start; i<stop; ++i)
{
    a[i] = DO_SOME_WORK;
} 

However, with this method, for my first example we get 1000/7 = 142 = count. And so the last rank starts at 852 and ends at 994. The last 6 lines are ignored.

Would be best solution to append something like this to the previous code?

int remainder = N%size;
int start = N-remainder; 
if (rank == 0){
     for (i=start;i<N;i++){
         a[i] = DO_SOME_WORK;
     }

This seems messy, and if its the best solution I'm surprised I haven't seen it elsewhere.

Thanks for any help!

Answer 1

Improving off of @Alexander's answer: make use of min to condense the logic.

int count = N / size;
int remainder = N % size;
int start = rank * count + min(rank, remainder);
int stop = (rank + 1) * count + min(rank + 1, remainder);

for (int i = start; i < stop; ++i) { a[i] = DO_SOME_WORK(); }

Answer 2

Here's a closed-form solution.

Let N = array length and P = number of processors.

From j = 0 to P-1,

Starting point of array on processor j = floor(N * j / P)

Length of array on processor j = floor(N * (j + 1) / P) – floor(N * j / P)