Efficient algorithm to distribute work?
- by Zwei Steinen
It's a bit complicated to explain but here we go.
We have problems like this (code is pseudo-code, and is only for illustrating the problem. Sorry it's in java. If you don't understand, I'd be glad to explain.).
class Problem {
final Set<Integer> allSectionIds = { 1,2,4,6,7,8,10 };
final Data data = //Some data
}
And a subproblem is:
class SubProblem {
final Set<Integer> targetedSectionIds;
final Data data;
SubProblem(Set<Integer> targetedSectionsIds, Data data){
this.targetedSectionIds = targetedSectionIds;
this.data = data;
}
}
Work will look like this, then.
class Work implements Runnable {
final Set<Section> subSections;
final Data data;
final Result result;
Work(Set<Section> subSections, Data data) {
this.sections = SubSections;
this.data = data;
}
@Override
public void run(){
for(Section section : subSections){
result.addUp(compute(data, section));
}
}
}
Now we have instances of 'Worker', that have their own state sections I have.
class Worker implements ExecutorService {
final Map<Integer,Section> sectionsIHave;
{
sectionsIHave = {1:section1, 5:section5, 8:section8 };
}
final ExecutorService executor = //some executor.
@Override
public void execute(SubProblem problem){
Set<Section> sectionsNeeded = fetchSections(problem.targetedSectionIds);
super.execute(new Work(sectionsNeeded, problem.data);
}
}
phew.
So, we have a lot of Problems and Workers are constantly asking for more SubProblems. My task is to break up Problems into SubProblem and give it to them. The difficulty is however, that I have to later collect all the results for the SubProblems and merge (reduce) them into a Result for the whole Problem.
This is however, costly, so I want to give the workers "chunks" that are as big as possible (has as many targetedSections as possible).
It doesn't have to be perfect (mathematically as efficient as possible or something). I mean, I guess that it is impossible to have a perfect solution, because you can't predict how long each computation will take, etc.. But is there a good heuristic solution for this? Or maybe some resources I can read up before I go into designing?
Any advice is highly appreciated!
