Re: new multicore programming docs for GCC and Visual Studio

On Sep 29, 4:23=A0pm, "Chris M. Thomasson" <n...@[EMAIL PROTECTED]
> wrote:

> >> Are you using something like the algorithm in TBB?
>
> >http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TM-548.pdf
>
> > TBB is based on MIT's Cilk work:
>
>http://www.cilk.com/multicore-blog/bid/5607/Cilk-Wins-Most-Influentia...
>
> How does the internal low-level impl compare to the following:
>
> http://www.cs.bgu.ac.il/~hendlerd/papers/dynamic-size-deque.pdf
>
> I am looking for raw pseudo-code for atomic deque internal impl
details..=
..
> AFAICT, this work from SUN would scale better than Clik. Please correct
m=
e
> if I am way off base here. It seems like spawning a successor thread has
> overheads... Humm. Pleas try to bear with me here; okay? Correct my
> ignorance on Clik's work-stealing internal impl... Well, let me pick an
i=
mpl
> to focus on... Say, DEC Alpha?


AFAIK, in early days Cilk's work-stealing deque used mutex-based
pop(). But I remember there was some mentions of non-blocking
algorithms in the Cilk's papers, something like "some people point us
that it's possible to implement work-stealing deque in completely non-
blocking manner". And I don't know whether non-blocking deque was
finally incor****ated into Cilk.

If mutex is spin-mutex (i.e. there is only 1 atomic RMW per lock/
unlock) and stealing is rare, then mutex-based deque is nearly the
same as non-blocking deque with 1 RMW... provided that push() doesn't
use mutex. And provided that atomic RMW has the same cost as StoreLoad
memory fence (x86).


Dmitriy V'jukov