I want to solve a load balancing problem using MPI with the C language. Each MPI task has an array of different size (consisting of integers).
Initial situation : data is distributed unequally between MPI processes. And we want to get arrays with same length in each process after distributing data.
We asssume each process contains an array of a radom size :
int nbTask;
int myRank;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &nbTask);
MPI_Comm_rank(MPI_COMM_WORLD, &myRank);
time_t t;
srand(time(NULL) + myRank);
int size = (rand() % (60 - 40 + 1)) + 40;
I then calculate the size that each array would have after balancing :
int global_sum;
int new_size;
MPI_Allreduce(&size, &global_sum, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
new_size = (int)(((float)global_sum/nbTask) + 1);
int exScan;
MPI_Exscan(&size, &exScan, 1, MPI_INT, MPI_SUM, MPI_COMM_WORLD);
Can you think of an algorithm to send data from each processor to another in order to get the same size of arrays in each processor.
Appearantly, the solution uses MPI_Scan or MPI_Exscan to find what to send to processor p-1 and p+1
Here is my solution :