Re: [Algorithms] General purpose task parallel threading approach

[Jon W. <jw...@gm...>]

Sebastian Sylvan wrote:
> I think they key notion you may be misunderstanding about work 
> stealing is that the stealing happens from the opposite end of the 
> queue versus where the owning thread executes from. If stealing 
> happened from the "execution end" then yes, you could get this weird 
> interleaving, but that's not the case.

Steal order doesn't matter, because in that case you may easily have two 
threads adding tasks:

Adding order:

1   2
x   y
z   w
a  
b  
c 
d

Now, stealing, no matter from which order you steal, will not lead to 
optimal scheduling. You do need to sort by dependencies, and to avoid 
having to do optimization on the full spanning graph, simply choosing 
the task with the deepest*widest dependency chain first will usually 
work out well enough.

Sincerely,

jw