Re: [Boost-users] graph theoretical problem

Subject: Re: [Boost-users] graph theoretical problem
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-08-05 12:52:07

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