Re: [Algorithms] General purpose task parallel threading approach

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

Sebastian Sylvan wrote:
>
>
> On Fri, Apr 10, 2009 at 7:11 PM, Jon Watte <jw...@gm... 
> <mailto:jw...@gm...>> wrote:
>
>
>     Of course not. A task doesn't get run until its dependencies are
>     resolved.
>
>
> Which is the whole problem, since it may need to run to even know what 
> its dependencies are.

It's clear that we have totally different ideas about data and software 
architecture.
Clearly you can know what the dependencies are, or you wouldn't be able 
to have those dependencies in the first place.

>
>  Same thing if you call a virtual function - who knows what code will 
> run as a result of that, and what data dependencies that will cause?
>

To answer your rethorical question: Our data path system knows.
If you have wildly different dependencies based on a switch(), then that 
is better expressed as a behavior component (that you can swap out) 
rather than a code switch(). (The "pure OO" movement claims that every 
switch can be turned into a virtual dispatch, but I wouldn't go that far)

> Yours doesn't seem to be. It may work great for your particular 
> specialized conditions (heck, we use something similar for our 
> rendering tasks!)

Our data dependency system is very similar to that of dependency 
properties in WPF, or properties in the Spring web framework. It's very 
general, and used pervasively through the entire system.

> IMO we really will need a general system in the future to be able to 
> kick off enough tasks to keep 64 threads busy for an entire frame.
>

I believe you need to know, and be able to express, what your data is, 
where it is coming from, and how it is processed, to be able to reason 
about it properly. Accidental dependencies that aren't injected 
explicitly is pretty much where all non-trivial coupling and performance 
bugs come from, so engineering those out is a big win, even before you 
start looking at threading a component system.

> You specify dependencies, yes, but they may be dynamic

Which is why the scheduler must be dynamic!

> For example, in some AI code you may want to do a parallel loop 
> through all enemies within a certain radius to score them based on the 
> danger they pose to you - you can't really know before you start 
> executing what enemies you're going to get back from that range query, 
> and therefore which objects you're going to have a dependency on - so 
> you need to start executing the task before you know which 
> dependencies it has.

Subsystems can have dependencies, too. It's perfectly fine to specify 
that AI reasoning depends on collision detection, and collision 
detection depends on integration output (position) from the last frame. 
That way, you can re-use the collision output data for AI, rather than 
to have to re-run queries, too.

Sincerely,

jw