Re: [Algorithms] General purpose task parallel threading approach

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

Sebastian Sylvan wrote:
> Exactly! And if that specific runtime framework enforces specific 
> restrictions, then that means your specific code has to be written 
> under those specific restrictions, which means your runtime framework 
> is not general.
>  

I used to be in the OS business for many years. However, Microsoft ate 
us on the high end, and Linux ate us on the low end -- there's not room 
for much else these days, IMO.

>
> It's a mathetmatical truth that any system that requires dependencies 
> to be known up front can not also be dynamic.
> You have said that your system requires this, I quote:
> "A task doesn't get run until its dependencies are resolved.
> [...]
> In our system, we have explicit data dependency metadata
> [...], so this knowledge is something we
> have up front."
>

Up front at the start of a frame, not up front at the start of the program.

A dependency is simply expressed as a DOM-style path, much like XPath, 
JavaScript and WPF. All components and functions of the path are "live," 
and any change is distributed to dependents. You can re-assign these 
paths if you want; such a re-assignment will take effect the next frame.

>
> If you read more carefully I've given you two examples of how tasks 
> using polymorphism can not be scheduled ahead of time either. Any kind 
> of dynamic control flow needs an on-line scheduler.

Sure it can! You just have to say that polymorphism isn't allowed to 
cause new tasks to get spawned synchronously. I think that's a very 
simple rule to live by, and it makes smearing the workload across cores 
much easier. Not to mention it causes fewer bugs.

>
> Well depending on how you propose to know the priorities, this may not 
> be what you said before. 

Well, it seems that you're talking to several people at once, so the 
"you" you've been using has started to look a little diffuse to me.

> My whole argument has been (and I've stated this very clearly in every 
> messag) that an ahead-of-time scheduler can not schedule dynamic code. 
> If you weren't talking about an ahead of time scheduler you could've 
> said this on any number of

The scheduler I propose is not ahead of time, but it does know (and 
update) the dependencies of tasks, including tasks that get added to the 
queue during a frame.
If you want to buckle down to ahead-of-time, there's actually two kinds 
of ahead-of-time: one that is truly static (such as those proposed by 
people who set up "tasks" at program start, and then run them 
statically), and one that is static per frame, but is dynamic across 
frames. I think the latter may also be useful for games, but that's not 
what I'm proposing.

>
> If WPF requires all dependencies to be known up front then it is 
> restricted.

You know what, my car is restricted. It can't go faster than 85 miles 
per hour. It can only run on paved roads. Heck, I can't even drive to 
another state from where I live without the infrastructure of a gas 
station. Still, it turns out that those restrictions allow me to buy a 
car that is quite affordable, comfortable, and safe, and actually solves 
the problem I need it to solve (get from home to work and back, every 
day, without breaking).
I'll let you figure out how to map this analogy to writing schedulers 
for games :-)

> I re-wrote our task scheduler for our rendering system not four months 
> ago, and guess what? It's an ahead-of-time scheduler.

> All I'm doing is pointing out the mathematical impossibility of both 
> knowing all dependencies up front, *and* allowing dynamic control flow 
> (including polymorphism).

And I'm saying that the system I'm describing knows all the dependencies 
when a task is inserted, but because tasks can be inserted during 
processing, that means it's not "ahead of time" in the sense of 
start-of-frame or start-or-program.
That being said, almost all new tasks are created because new objects 
are created in the system, and object creation (or, rather, injection) 
generally happens at a defined time. Seems dynamic enough for anything 
we do (and we do a whole-Earth virtual world with user generated 
content, which is pretty much the most dynamic case you can think of 
while still calling it a game).

Again: Spawning threads/tasks willy-nilly, especially based on hidden 
switch/if statements in code, and then (this is the worst part) 
synchronously waiting for the result, is a Bad Idea if you want to 
spread across many, many cores. If you consider caches local to cores, 
then cores are actually similar to NUMA machine architectures, with all 
that implies. If you want to be totally general (in the sense of a 
current general-purpose UNIX-like operating system, say), then you will 
not scale well across large numbers of cores. A different programming 
paradigm is needed. What I'm describing is one that I think will work 
out great.

Sincerely,

jw