Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

Are you sure you need something more precise than the obvious greedy algorithm:

Assign processors to task starting with the longest task. For each task you consider, assign it to the processor that has hat least total work assigned to it yet.

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.

I think (but haven't crossed all the i's and dotted the t's here) that this can even be arranged such that no processor needs to work on more than two different split tasks.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.