Cilk/Cilk++

[Charles E. Leiserson]

== Quote from Robert Jacques (sandford at jhu.edu)'s article
> On Mon, 11 Aug 2008 18:20:25 -0700, bearophile <bearophileHUGS at lycos.com>
> wrote:
> > Robert Jacques:
> >> Cilk is a less flexible (and also probably less efficient) version of
> >> futures/promises.
> >
> > I don't know how much efficient is one compared to the other, from the
> > site and articles efficiency seems "acceptable". And sometimes less
> > flexible things are simpler to use, and this Cilk seems already getting
> > difficult enough for me.
> >
> > Bye,
> > bearophile
> On their own, futures don't require work stealing (inherently greedy), so
> they have less overhead. (I think) They also can be library implemented
> and don't require compilier changes.
> As for simplicity compare
> cilk int fib (int n)
> {
>       if (n < 2) return n;
>       else
>       {
>          int x = spawn fib (n-1);
>          int y = spawn fib (n-2);
>          sync;
>          return (x+y);
>       }
> }
> with
> int fib (int n)
> {
>       if (n < 2) return n;
>       else
>       {
>          auto x = future!(fib)(n-1);
>          auto y = future!(fib)(n-2);
>          return (x+y);
>       }
> }

As the leader of the Cilk project at MIT and founder of Cilk Arts, let me offer
some comments about Cilk technology versus general futures.

Cilk is probably more efficient than a general future mechanism.  The overhead for
spawning in MIT-Cilk is only about 3 times the cost of an ordinary C function
call.  The overhead in Cilk Arts's Cilk++ is about 4 times a function call.

A general future mechanism runs into the problem that it can blow out memory
pretty easily if you want good speedup.  What happens is that you create a future
(and allocate storage for it), and then it stalls.  At that point, if you want
good speedup, you have to switch to something else, which creates a future that
stalls, and so forth.  So, you end up with a lot of stalled futures sitting around
and consuming memory.  In contrast, a Cilk-style work-stealing scheduler
guarantees that on P processors, it uses at most P times the stack space of a
serial execution, and it provably achieves linear speedup as long as the
application has sufficient parallelism.

For more information on Cilk and Cilk++, please check out our website
www.cilk.com.  We also have an e-book at www.cilk.com/multicore-e-book that
outlines some of the key issues in multicore-enabling software.  If you have a
deep interest, I'd be happy to discuss what would be involved in inserting Cilk
technology into D.