Re: [Boost-users] graph theoretical problem

Subject: Re: [Boost-users] graph theoretical problem
From: Brian Budge (brian.budge_at_[hidden])
Date: 2013-08-05 13:29:29

On Mon, Aug 5, 2013 at 10:20 AM, Peter Foelsche <foelsche_at_[hidden]> wrote:
> 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