Re: [Algorithms] General purpose task parallel threading approach

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

Sebastian Sylvan wrote:
>
>     So I'm saying you, as the component writer, don't need to worry about
>     spawning at all. Tasks are created by the system, to resolve the
>     semantics as described by the system.
>
>
> I do need to worry about specifying what's parallel and what isn't 
> (unless I'm in a language where this can be automatically deduced - 
> which C/C++ isn't), and if since I can't do that in a dynamic way your 
> system isn't flexible enough to run generic code. 

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.

>
> 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, and how the 
limitations that do exist actually are much less evil than the problems 
of trying to solve the "generic" problem. Although I gave it a pretty 
good shot, I think.


> 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. 
It's simply a different style of building software, using a different 
kind of paradigm than you are using. Personally, I think the old-school 
paradigm is unfit for heavy multi-core execution, and using explicit, 
data-centric components are the way of the future. You're of course free 
to disagree, because the future isn't actually here yet.

> 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. If you recall, my argument was simply that 
a naive work-stealing scheduler is not capable of making decisions made 
on global knowledge (such as dependency depth), and thus will often 
(statistically) make poor choices.

> Restricting the use of dynamic control flow is the opposite of "high 
> level" as it restricts the use of fairly ubiquitous things like 
> virtual functions (when you call a virtual function you can't know 
> what dependencies that call will have ahead of time as virtual 
> functions are dynamically dispatched - you just have to make the call 
> and see where you end up).
>

Go write a real application using WPF dependency properties, and then 
tell me that that's a "low level" "restricted" programming model. (I 
pick WPF because that's the closest available, well-documented API that 
has many of the same affordances as our framework) I think you simply 
are mired in the old, low-level ways, and don't understand the system 
I'm using. (The arguments you make are very similar to the arguments 
that assembly programmers made when FORTRAN and C showed up, IMO).

Heavy multi-core threading is a new kind of execution environment, and 
it's unlikely that the old style of doing things will be the best match 
for that environment. Just like the introduction of deep caches made 
instruction counting a thing of the past.

Sincerely,

jw