Re: [Algorithms] General purpose task parallel threading approach

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

On Fri, Apr 10, 2009 at 1:48 AM, Jon Watte <jw...@gm...> wrote:

> Sebastian Sylvan wrote:
> >
> >         Here are two possible work orderings:
> >
> >         xy
> >         zw
> >         a
> >         b
> >         c
> >         d
> >
> >         ax
> >         by
> >         cz
> >         dw
> >
>
> >
> > 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.
> >
>
>
> There is no guarantee of that. The scheduler, expressing "parallelism
> where it is" could easily choose the xyzw first order, rather than
> trying to run a in parallel with x. There is nothing in the knowledge of
> the scheduler you propose to guarantee the second (desirable) outcome,
> except perhaps wishful thinking on part of the implementer.
>

In this case, with the scheduling policy I propose (standard work-stealing)
I don't see how it could possibly do anything different?
You put two tasks (the xyzw one and abcd one) on whichever queue you start
on, the other queue will sit idle just waiting for something to pop up
somewhere and grab the first one to go on the queue. Then the second one
goes on the queue and then there's the final sync which causes the
originating thread to start executing. Regardless of the order you spawn the
task the other thread will take the other one. There is no opportunity for
the xyzw tasks to "skip" past the abcd ones since you only steal when you've
run out (so even if the other thread takes the xyzw ones it will put the
child-tasks on *its* queue, and the original thread will go ahead and do
abcd before trying to steal).

So yeah, looks pretty guaranteed.

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