# Parallel computing : scheduling processors for large sums

does anyone know if there exists in the literature an algorithm that solves the following problem?

I have M different and indipendent sums, and P processors. The size of sums are in ascending order with the latest sums of much larger size than the first : $$N_1 < N_2 << N_i << N_M$$

The easiest way is to divide the M sums in order to have more sums but all of the same size. Where this size could be $N_{bal}$:

$$N_{add}=\sum_{i=1}^{M}{N_i}\\ N_{bal}=round(\frac{N_{add}}{P})$$

I work in a distribuited memory cluster, and so if I split sums, I have to aggregate results of splitted sums to have the initial M solutions, with a lot of wasted time spent in processor communications (I work with MPI).

I made an algorithm that tries to keep the workload for each processor close to $N_{bal}$ , assigning little sums to a single processor, or split large sums between groups of processors.

I searched the web for a solution to this problem but have not found anything useful, does anyone know some algorithm?

-

That should give you reasonably good absolute difference between the highest scheduled processor's workload and your $N_{\rm bal}$.
If that is still not good enough for you, take one of the tasks assigned to the highest loaded processor and split it some of it off to be done by the lowest-loaded processor in such a way that that one of the two processors reaches a load of exactly $N_{\rm bal}$. (This is always possible). Repeat until everything is equalized, which can take no more than one split per processor on average.