www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Cilk/Cilk++

reply bearophile <bearophileHUGS lycos.com> writes:
As D seems getting more serious regarding its parallel intentions (even pushing
AST macros to the D 3), I have taken few looks at little Cilk programs, they
seem almost comprehensible to me, so this may result interesting:

http://en.wikipedia.org/wiki/Cilk

Bye,
bearophile
Aug 10 2008
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
The three lectures give a quick and fast intro to this extension to C:
http://supertech.csail.mit.edu/cilk/lecture-1.ppt
http://supertech.csail.mit.edu/cilk/lecture-2.ppt
http://supertech.csail.mit.edu/cilk/lecture-3.ppt

The main problem I see is combining this form of parallelism with other ones.

Bye,
bearophile
Aug 11 2008
next sibling parent reply davidl <davidl 126.com> writes:
在 Mon, 11 Aug 2008 20:07:24 +0800，bearophile <bearophileHUGS lycos.com>  
写道:


 The three lectures give a quick and fast intro to this extension to C:
 http://supertech.csail.mit.edu/cilk/lecture-1.ppt
 http://supertech.csail.mit.edu/cilk/lecture-2.ppt
 http://supertech.csail.mit.edu/cilk/lecture-3.ppt

 The main problem I see is combining this form of parallelism with other  
 ones.

 Bye,
 bearophile


Yeah, from a quick view it's quite interesting

-- 
使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/
Aug 11 2008
parent %Joseph Schmoe <elmer fudd.com> writes:
Cilk has been spun out of MIT, and is now a commercial venture, Cilk Arts.

http://www.cilk.com/multicore-e-book

Cilk Arts has published a free e-Book: "How to Survive the Multicore Revolution
(or at Least Survive the Hype)"
the ebook covers:
    - Background on the emergence of mainstream multicore processors
    - The key challenges facing software developers
    - An introduction to multithreading concepts
    - Twenty questions to ask when going multicore
    - Overview of programming approaches, including OpenMP, Intels TBB, MPI,
Cilk++, WinAPI/Pthreads
Aug 16 2008
prev sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 11 Aug 2008 05:07:24 -0700, bearophile <bearophileHUGS lycos.com>  
wrote:

 The main problem I see is combining this form of parallelism with other  
 ones.


Cilk is a less flexible (and also probably less efficient) version of  
futures/promises. As such it's a subset of CSP and can be combined with  
threading, etc. fairly easily.
Aug 11 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Aug 11 2008
next sibling parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Mon, 11 Aug 2008 18:20:25 -0700, bearophile <bearophileHUGS 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);
      }
}
Aug 11 2008
next sibling parent Yigal Chripun <yigal100 gmail.com> writes:
Robert Jacques wrote:

 On Mon, 11 Aug 2008 18:20:25 -0700, bearophile
 <bearophileHUGS 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
 


<snip code>

While futures can be implemented in a library it would be even better to
add language support for them in the language. example of this is Herb
Sutter's Concur research project.
Aug 12 2008
prev sibling parent reply Charles E. Leiserson <cel cilk.com> writes:
== Quote from Robert Jacques (sandford jhu.edu)'s article

 On Mon, 11 Aug 2008 18:20:25 -0700, bearophile <bearophileHUGS 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.
Sep 04 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Charles E. Leiserson:


If you have a deep interest, I'd be happy to discuss what would be involved in
inserting Cilk technology into D.<


D is a free language, so probably that discussion can't give much money
directly to Cilk Arts. But if such keywords and semantics (what you call "cilk
technology") become more widespread among other languages (recently I have seen
newLisp adopt them) then Cilk Arts may gain something indirectly. Walter Bright
may be interested in some of the Cilk keywords, I don't know.

---------------

Related to Cilk I have just read this quite interesting article from the blog
in your site:
http://www.cilk.com/multicore-blog/bid/6381/Multicore-enabling-the-N-Queens-Problem-Using-Cilk

From that article:


After all, it's always good to have the serial version of a parallel
implementation at hand.<


Think about this alternative version of that phrase, told by an hypothetical
vendor of one of the first C compilers:

"After all, it's always good to have the assembly version of a C implementation
at hand."

It tells me that such technologies aren't much ripe yet :-)



Parallelizing a piece of code with Cilk++ is easy.<


Well, it's probably doable (and probably better than some other parallel
programming technologies), but for my limited brain, and limited knowledge of
Cilk, it doesn't seem 'easy' :-)

One fault of that code is that it doesn't show a comparison of that Cilk++ code
with the performance of code written for a normal C compiler, like GCC.

If you compare the performance of that 2/4-core implementation with the
following single core C version you may have a surprise:


#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef unsigned long ulong;
static const ulong ulong_bit = sizeof(ulong) * CHAR_BIT;

static inline ulong search(ulong lb, ulong cb, ulong rb, ulong cnt) {
  if (~0ul == cb)
    cnt += 1;
  else
    for (ulong bs = lb | cb | rb; ~0ul != bs;) {
      ulong b = ~bs & (bs+1);
      bs |= b;
      cnt = search((lb | b) << 1, cb | b, (rb | b) >> 1, cnt);
    }
  return cnt;
}

static inline ulong nQs(ulong m) { return search(0, ~0ul >> m, 0, 0); }

int main(int argc, char* argv[]) {
  ulong a = argc < 2 ? ulong_bit : atol(argv[1]);
  ulong n = a < ulong_bit ? a : ulong_bit;
  for (ulong i=1; i<=n; ++i)
    printf("%li: %li total solutions\n", i, nQs(i));
  return 0;
}

That code comes from:
http://c2.com/cgi/wiki?EightQueensInManyProgrammingLanguages

-----------------

So far, one of the most promising technologies I see for parallel computations
can be seen from this article + supplementary data:
"BSGP: Bulk-Synchronous GPU Programming", by Qiming Hou, Kun Zhou, Baining Guo,
that you can find here:
http://www.kunzhou.net/

Bye and thank you,
bearophile
Sep 04 2008
prev sibling parent "Robert Jacques" <sandford jhu.edu> writes:
 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.


Thank you. It's always great to hear from an expert.


 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.


And the overhead for a future is about 3-4 function calls as well (on  
average, less for delegates or if you can scope it) and ~4-6 CASes.
1 call to the future creation function (with complier support, this can be  
merged with copying the arguments onto the heap)
1 call worth of work to copy the function arguments onto the heap (not  
needed for delegates or if you can scope the future.)
1 call worth of work to copy the function arguments onto the worker thread  
and then begin execution.
The CASes are for a memory free-list and a work stack/queue.


 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.


This isn't a problem of futures. This is a problem of the implementation  
of the future. It's no more difficult for futures to cleanly support  
kernel locks than Cilk. Work-stealing actually is due to Click using per  
thread work queues, instead of a single global queue. While the the  
multiple queues do reduce contention, they require all threads to be  
future/Cilk enabled. A hybrid solution, with a global queue for  
non-future/Cilk threads and per thread queues for the future threads might  
work well and support multi-paradigm threading.


 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.
Sep 04 2008
prev sibling parent "Manfred_Nowak" <svv1999 hotmail.com> writes:
bearophile wrote:


  less flexible things are simpler to use


Argumenting by Occam's razor :-)



 Cilk seems already getting difficult enough


A problem with cilk is, that it is unaware of the fact, that efficient 
algorithms do change with O(p), the order of the number of available 
processors...and their capabilities.

-manfred 
-- 
Maybe some knowledge of some types of disagreeing and their relation 
can turn out to be useful:
http://blog.createdebate.com/2008/04/07/writing-strong-arguments/
Aug 16 2008
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
bearophile wrote:

 As D seems getting more serious regarding its parallel intentions (even
pushing AST macros to the D 3), I have taken few looks at little Cilk programs,
they seem almost comprehensible to me, so this may result interesting:
 
 http://en.wikipedia.org/wiki/Cilk


Yeah, I and I believe others have suggested Cilk as one of the languages 
worth investigating as a model for built-in parallel programming 
features in D.  But for whatever reason no one has seemed terribly 
interested.


Sean
Aug 11 2008
parent bearophile <bearophileHUGS lycos.com> writes:
Sean Kelly:

 Yeah, I and I believe others have suggested Cilk as one of the languages 
 worth investigating as a model for built-in parallel programming 
 features in D.  But for whatever reason no one has seemed terribly 
 interested.


Cilk is probably not perfect (it seems not easy to mix multithreading and such
parallel computations), but parallel programming is a quite complex matter, and
there's little hope in re-inventing too much good things. Cilk behind has years
of theoretical study, a C++ implementation (Cilk++) that I think you can buy
(or you will be able to buy), so it's already solid enough, and even a my
limited brain seems able to understand enough how how to use it (and it has
some other advantages, like if you remove the cilk statements you objtain
working C code. The resulting code looks clean enough, even if you have to add
some recursivity where where's none, etc), so it may be better this than
something invented ex-novo, for D.

Bye,
bearophile
Aug 11 2008