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

mpi

Solution

If I had `N` tasks (e.g., array elements) and `size` workers (e.g., MPI ranks), I would go as follows:

int count = N / size;
int remainder = N % size;
int start, stop;

if (rank < remainder) {
    // The first 'remainder' ranks get 'count + 1' tasks each
    start = rank * (count + 1);
    stop = start + count;
} else {
    // The remaining 'size - remainder' ranks get 'count' task each
    start = rank * count + remainder;
    stop = start + (count - 1);
}

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

That is how it works:

/*
  # ranks:                    remainder                     size - remainder
            /------------------------------------\ /-----------------------------\
     rank:      0         1             remainder-1                         size-1
           +---------+---------+-......-+---------+-------+-------+-.....-+-------+
    tasks: | count+1 | count+1 | ...... | count+1 | count | count | ..... | count |
           +---------+---------+-......-+---------+-------+-------+-.....-+-------+
                      ^       ^                            ^     ^
                      |       |                            |     |
   task #:  rank * (count+1)  |        rank * count + remainder  |
                              |                                  |
   task #:  rank * (count+1) + count   rank * count + remainder + count - 1

            \------------------------------------/ 
  # tasks:       remainder * count + remainder
*/

Problem

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!

Original source