Re: [Algorithms] General purpose task parallel threading approach

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

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

>
>
> On Thu, Apr 9, 2009 at 11:52 PM, Jon Watte <jw...@gm...> wrote:
>
>> Sebastian Sylvan wrote:
>> >
>> >
>> >
>> >
>> >     Anyway, I was hoping to get some strong arguments either way, but
>> >     I guess it’s not very clear yet what solution is the best for
>> >     multi-threading your engine. I read through the Gamefest slides
>> >     and it was a bit surprising they didn’t deal with prioritization
>> >     at all, which is vital for throughput.
>> >
>> > It's actually not vital for throughput, and I couldn't see anything in
>> > the presentation you linked saying it is.
>> > Tasks are naturally ordered according to their dependencies due to the
>> > way they are spawned (you spawn tasks, then you sync - only then do
>> > you spawn any dependent tasks). With the cilk based model any task
>> > that is enqueued is by definition ready to run. There's in no need for
>> > priorities to optimize throughput.
>> >
>>
>> Actually, it is. Consider a case where you have some independent tasks,
>> and some serially dependent tasks. Suppose you have 4 independent tasks
>> xyzw, 4 linearly dependent tasks abcd, and two cores to schedule across.
>> Here are two possible work orderings:
>>
>> xy
>> zw
>> a
>> b
>> c
>> d
>>
>> ax
>> by
>> cz
>> dw
>>
>> Clearly, the second case is much preferred. However, without
>> prioritization, you won't get that outcome.
>
>
> Actually you could, since you can just spawn the tasks in the order you
> want to run them. Like I believe I said very early on, the only reason you
> would want to reorder tasks is because you may want to start a task that
> spawns many other threads early - but you can still do that without having a
> priority system since the order in which tasks are spawned is deterministic.
>
>
In fact, in your particular case this isn't only possible without
prioritization, but it's what happens if you pay no attention what so ever
and just write things naively, expressing parallelism where it is.

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