Re: [Boost-users] graph theoretical problem

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

On Aug 14, 2013 4:18 PM, "Peter Foelsche" <foelsche_at_[hidden]> wrote:
>
> On Mon, Aug 5, 2013, Brian Budge wrote:
>
> > 1. topological sort
>
> Thanks!
>
> Just had this idea:
>
> Once you do a topological sort, one can combine tasks, which are behind
each other but do not depend on each other.
> For these tasks, the local sorting order does not matter.
> One can look at each of these tasks with the intention of putting them
into separate threads.
> If the cost of one of such tasks is not sufficient, one could try to
combine it with one of its dependent tasks which only depend on the task
currently being considered.
> If by combining tasks, one gets tasks, which are sufficiently expensive,
they can be distributed on separate threads, otherwise, one needs to
consider combining them with the tasks at the current level of the sorting
order.
>
> Is this it?!
> Peter
>

Pretty much.  Also anything within that dependency level can be
multithreaded.   It is a greedy algorithm and not optimal, but I would bet
it works pretty darned well.

  Brian