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.
>

I think they key notion you may be misunderstanding about work stealing is
that the stealing happens from the opposite end of the queue versus where
the owning thread executes from. If stealing happened from the "execution
end" then yes, you could get this weird interleaving, but that's not the
case.



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