Re: [Algorithms] General purpose task parallel threading approach

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

Sebastian Sylvan wrote:
>
>
>  
>
>     Anyway, I was hoping to get some strong arguments either way, but
>     I guess it’s not very clear yet what solution is the best for
>     multi-threading your engine. I read through the Gamefest slides
>     and it was a bit surprising they didn’t deal with prioritization
>     at all, which is vital for throughput.
>
> It's actually not vital for throughput, and I couldn't see anything in 
> the presentation you linked saying it is.
> Tasks are naturally ordered according to their dependencies due to the 
> way they are spawned (you spawn tasks, then you sync - only then do 
> you spawn any dependent tasks). With the cilk based model any task 
> that is enqueued is by definition ready to run. There's in no need for 
> priorities to optimize throughput. 
>

Actually, it is. Consider a case where you have some independent tasks, 
and some serially dependent tasks. Suppose you have 4 independent tasks 
xyzw, 4 linearly dependent tasks abcd, and two cores to schedule across. 
Here are two possible work orderings:

xy
zw
a
b
c
d

ax
by
cz
dw

Clearly, the second case is much preferred. However, without 
prioritization, you won't get that outcome. While you could sort the 
entire graph, and do some dependency/bin packing to push it as compact 
as possible, usually it suffices with some heuristics, such as always 
prioritizing tasks that have dependents, and the longer the dependency 
chain, the higher the priority.

Sincerely,

jw