Re: [Algorithms] General purpose task parallel threading approach

[Sebastian S. <seb...@gm...>]

On Sun, Apr 12, 2009 at 12:15 AM, Jarkko Lempiainen <al...@gm...>wrote:

>  Yes, only tasks that have been previously executed are prioritized (if
> not, the task has some default priority). The job queue also processes tasks
> in groups (e.g. a group per function), so all tasks for a task group have
> the same priority and are scheduled sequentially for execution (e.g.
> multiple animate_character(character*) function tasks with different
> character* form a task group). I profiled that the overhead of adding and
> executing a task from the queue is around 500 cycles total on my test PC, so
> it’s not bad, but I haven’t used the queue in a real game engine yet so I
> can’t tell how well (or badly) it works in real-life scenarios. Anyway, it
> should be quite easy to change the scheduling strategy of the queue once
> it’s being integrated into an engine to see how it compares to work stealing
> for example.
>

It would definitely be interesting to see some benchmark comparisons... The
problem I have with it a priori is that just plain old work stealing works
so surprisingly well (performance is very close to the theoretical maximum
for a given number of processors and a given length of critical path), that
there doesn't seem much room for improvement as far as throughput is
concerned.

You'd need to test both on the same code I guess because the cost of these
things vary, but if we guesstimate a bit then depending on the exact
architecture and calling convention (and the number of parameters that need
to be pushed on to the stack etc.) let's say cilk's "4x the cost of a
function call" equates to about 50 cycles giver or take, then you're adding
an order of magnitude extra overhead which seems quite steep to me.

-- 
Sebastian Sylvan
+44(0)7857-300802
UIN: 44640862