Re: [Algorithms] General purpose task parallel threading approach

[Jarkko L. <al...@gm...>]

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.

 

 

Cheers, Jarkko

 

  _____  

From: Sebastian Sylvan [mailto:seb...@gm...] 
Sent: Sunday, April 12, 2009 12:44 AM
To: Game Development Algorithms
Subject: Re: [Algorithms] General purpose task parallel threading approach

 

 

On Sat, Apr 11, 2009 at 9:59 PM, Jarkko Lempiainen <
<mailto:al...@gm...> al...@gm...> wrote:

Task priorities are updated once per frame, but there is no list of tasks to
be sorted before execution of tasks begins. That's purely your own wrong
conclusion drawn from. wherever.

For example the presentation you posted that (as far as I can tell without
seeing the talk) talked about static ordering of tasks ahead of time. And
you also talked about global prioritization, and how you weren't waiting on
other tasks within a task etc.

So, it's online scheduler in the sense that tasks are spawn "randomly"
within tasks, but their priorities are determined in the end of the frame
for next execution based on task dependencies and execution times. That
clears things up?

Okay, that makes sense.

You're not actually resolving dependencies by sorting the tasks up front,
dependencies are still enforced dynamically, you just sort things that do
not have dependencies based on historical behaviour? I.e. you spawn a task
and *if* that task existed last frame you prioritize it based on that?

Have you measured if the added communication overhead of doing this actually
buys you anything on real code? Seems like you'd have to make sure that the
overhead of moving things around based on priority must be counteracted by
the benefits, and since the constant factor for work-stealing is very close
to 1 in empirical studies there doesn't seem to be that much benefit to be
gained from shuffling tasks around...

 

If not, please ask rather than draw further wrong conclusions.

I usually try hard to stay on topic, but seriously, I asked you multiple
concrete questions about how your system would handle specific scenarios,
answering one of those would probably have been more illustrative than
throwing ad-hominems around...


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