On Fri, 2 Aug 2013, Peter Foelsche wrote:
Dear All,
does the boost graph library provide a solution to the problem I'm trying to solve:
I want to distribute a set of tasks to multiple CPUs/Threads. The tasks have predecessor and successor dependencies. There are no loops. More often than not, a task consists of only very few operations. So if I brute force program this, the resulting code is busy only with scheduling -- the real code does not show up in the profiling results. I think this can be solved by collapsing some tasks into a single task to minimize scheduling/communication. I've got a cost function associated with every task.
Is this some well known algorithm which is already available in boost graph?
How important is a good solution compared to doing the scheduling quickly? One option you may have is work stealing, which is designed for dynamic tasks being spread across threads; one implementation that allows dependencies is PFunc (https://projects.coin-or.org/PFunc). An optimal solution will be hard to find, since the problem (with arbirary dependencies) is NP-complete even for scheduling onto one thread. Do you have further restrictions on the dependencies (at most one predecessor, at most one successor, etc.)? -- Jeremiah Willcock