On Mon, Aug 5, 2013 at 10:20 AM, Peter Foelsche
On Mon, 5 Aug 2013, Jeremiah Willcock wrote:
thanks!
How important is a good solution compared to doing the scheduling
quickly? One option you may have is work stealing, which is designed
there will be many executions of the optimized graph -- of course the optimization must complete in a reasonable time
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.)?
no -- there might be zero or more (including more than one) predecessors or successors for every task
Have you already tried the following? 0. spawn threads. all threads grab data off of a queue as it becomes available. I recommend boost::lockfree::queue for this (with some minor caveats) 1. topological sort 2. for each dependency level, submit all work for the level to the queue and wait for that work to be completed before moving to the next dependency level I understand that there will be overhead for very tiny tasks. A possible further optimization is to group items within a single dependency level and allow each queued task to actually be several of these smaller tasks. Brian