Re: [Algorithms] General purpose task parallel threading approach

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

On Fri, Apr 10, 2009 at 12:25 AM, Sebastian Sylvan <
seb...@gm...> wrote:

>
>
> On Thu, Apr 9, 2009 at 11:51 PM, Jarkko Lempiainen <al...@gm...>wrote:
>
>>  > It's actually not vital for throughput, and I couldn't see anything in
>> the presentation you linked saying it is.
>>
>>
>>
>> That’s what “Minimizing the Critical Path” is about. Ignoring the issue
>> doesn’t mean it doesn’t exist.
>>
>>
> That section only seems to talk about optimizing scheduling based on static
> (in the sense that they're known ahead of time - not necessarily at compile
> time) dependencies, not about the necessity to support priorities.
>
> And of course, general code doesn't have a static call graph, so it's even
> impossible to do this analysis unless your code happens to be simple enough
> (see: the halting problem).
>


Also, it's worth noting that work stealing is *provably* efficient. In other
words the way the scheduling works gives asymptotically optimal throughput.
So claiming that either ahead-of-time prioritization, or a runtime priority
system is required for efficient throughput is mathematically incorrect. And
given that the absence of them give a far more flexible programming model,
and real-world speedups in practice, I'd say the jury's in on this one...

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