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

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

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
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 next sibling parent "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
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 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