Re: [Algorithms] General purpose task parallel threading approach

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

On Sun, Apr 12, 2009 at 3:15 AM, Jon Watte <jw...@gm...> wrote:

> Luckily, I'm not running generic code; I'm running code that interfaces
> with a specific operating system, a specific compiler, and a specific
> runtime framework.


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.


> > Yes, unfortunately I can't seem to explain adequately to you that a
> > system that requires all dependencies to be known up front is not
> > actually dynamic in any meaningful sense of the word.
>
> And I can't explain to you how that's not actually true


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."
and therefore your system can not be dynamic.


> > My criticism of your approach is hardly that it's too high level.
> > Quite the opposite! I'm saying that it is, as a matter of mathematical
> > fact, not flexible enough to run code with dynamic control flow,
> > because by definition you can not know
>
> Yet it is doing it, daily. Note that most flow control comes from
> expression evaluation and polymorphism, rather than old-school
> if-then-else and switch statements which you seem to be worried about.


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.


> > dependencies ahead of time for such code. Dynamic control flow
> > *requires* an on-line scheduler - yours isn't.
>
> My specific proposal was that each time a core is free, it picks the
> highest priority task available in the queue. Priorities are ideally
> updated each time a new task is added to the queue (but that can be
> loosened up for efficiency if it turns out to be a bottleneck). I think
> that's an on-line scheduler.


Well depending on how you propose to know the priorities, this may not be
what you said before.
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 occasions. You said (see your quote above) that you *were*
doing ahead-of-time scheduling before, if you've now changed your mind then
we clearly aren't in disagreement any more (on this particular issue
anyway).

Go write a real application using WPF dependency properties, and then

tell me that that's a "low level" "restricted" programming model.


If WPF requires all dependencies to be known up front then it is restricted.
That's probably fine because it has a very specific usage area. Like I've
said before, restricted doesn't mean bad, it just means restricted. I
re-wrote our task scheduler for our rendering system not four months ago,
and guess what? It's an ahead-of-time scheduler.
Saying that ahead-of-time scheduling can only handle restricted scenarios is
not the same as calling anyone who uses it stupid (because then I'd be
calling myself stupid!), it's just an honest discussion about pros and cons
without getting defensive just because I happen to use this very system
myself.

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

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