On Aug 14, 2013 4:18 PM, "Peter Foelsche" <foelsche@sbcglobal.net> 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