25,161
edits
Changes
Cilk
,Created page with " '''Home * Programming * Languages * Cilk''' '''Cilk''' (pronounced "silk") is a C-based, general-purpose programming language designed for [https:/..."
'''[[Main Page|Home]] * [[Programming]] * [[Languages]] * Cilk'''
'''Cilk''' (pronounced "silk") is a [[C]]-based, general-purpose programming language designed for [https://en.wikipedia.org/wiki/Multithreading_%28computer_architecture%29 multithreaded] parallel computing. Cilk started as in the mid 90s as a project at the Supertech research group in the [[Massachusetts Institute of Technology|MIT Labroratory]] headed by [[Charles Leiserson|Charles E. Leiserson]]. Important milestones in Cilk technology include the original Cilk-1, which provided a provably efficient work-stealing runtime support but little linguistic support, the later Cilk-5, which provided simple linguistic extensions for multithreading to [https://en.wikipedia.org/wiki/ANSI_C ANSI C], the commercial ''Cilk++'' by ''Cilk Arts'', which extended the Cilk model to [[Cpp|C++]], and after [[Intel]] acquired ''Cilk Arts'' in 2009, [https://en.wikipedia.org/wiki/Intel_Cilk_Plus Intel Cilk Plus]. In November 2010, Intel published a language and an [https://en.wikipedia.org/wiki/Application_binary_interface ABI] specification to enable other compilers to implement Cilk Plus <ref>[http://software.intel.com/en-us/articles/intel-cilk-plus-specification/ Intel® Cilk™ Plus Specification - Intel® Software Network]</ref>.
=Parallel Chess=
Cilk's testbeds in the 90s were chess programs using a [[Parallel Search|parallel search]]. [[Star Socrates|*Socrates]] used the [[Jamboree]] algorithm to search game trees in parallel and uses the Cilk 1.0 language and run-time system to express and to schedule the computation. [[CilkChess]] was written using the Cilk-5 linguistic extensions.
==Cilk-5 Linguistic Extensions==
Cilk-5.4.6 is the latest official MIT Cilk released under the [[Free Software Foundation#GPL|GNU General Public License]] <ref>[http://supertech.csail.mit.edu/cilk/cilk-5.4.6.tar.gz cilk-5.4.6.tar.gz]</ref>.
The keyword "'''cilk'''" defines a function which can [https://en.wikipedia.org/wiki/Spawn_%28computing%29 spawned] as a new [https://en.wikipedia.org/wiki/Thread_%28computer_science%29 thread], by using the "'''spawn'''" keyword. A cilk procedure cannot safely return values of the children it has spawned until it executes a "'''sync'''" statement, which acts like a local barrier. '''Inlets''', a kind of local function with access to local variables of its parent frame, are used to return values to its parent with the option to '''abort''' all of the already spawned descendants of the procedure to terminate immediately. Inlets are guaranteed to operate [https://en.wikipedia.org/wiki/Atomic_%28computer_science%29 atomically] with regards to each other and to the parent procedure, thus avoiding the bugs that could occur if the multiple returning procedures tried to update the same variables in the parent frame at the same time.
<span id="ParallelAlphaBeta"></span>
==Parallel Alpha-Beta==
This is how an [[Alpha-Beta|alpha-beta]] search routine was implemented with Cilk-5 <ref>[[Don Dailey]], [[Charles Leiserson|Charles E. Leiserson]] ('''2001'''). ''Using Cilk to Write Multiprocessor Chess Programs'', [[Advances in Computer Games 9]], [http://supertech.csail.mit.edu/papers/icca99.pdf pdf]</ref>, using the five keywords '''cilk''', '''spawn''', '''sync''', '''inlet''' and '''abort''':
<pre>
cilk int search( position *prev, int move, int depth ) {
position cur; int bestscore = -oo, num_moves, mv, sc, cutoff = false;
inlet void catch( int child_sc ) {
child_sc = -child_sc; /* negamax */
if ( child_sc > bestscore ) {
bestscore = child_sc;
if ( child_sc > cur.alpha ) {
cur.alpha = child_sc;
if ( child_sc >= cur.beta ) {
cutoff = true;
abort;
}
}
}
} /* end inlet */
/* create current position and set up for search */
make_move( prev, move, &cur );
if ( depth <= 0 ) return eval( &cur );
cur.alpha = -prev->beta; /* negamax */
cur.beta = -prev->alpha;
num_moves = gen_moves( &cur );
/* search the moves */
for ( mv = 0; !cutoff && mv < num_moves; mv++) {
catch ( spawn search( &cur, mv, depth-1 ) );
if ( mv == 0 ) sync; /* young brothers wait */
}
sync; /* this sync is outside the loop so that
older brothers execute in parallel */
return bestscore;
}
</pre>
==Quote==
by [[Vincent Diepeveen]] after [[WCCC 1999]] <ref>[https://www.stmintz.com/ccc/index.php?id=58505 DIEP parallel in Paderborn - technical and detailed story] by [[Vincent Diepeveen]], [[CCC]], June 28, 1999</ref>:
Actually the big professor who has written so many books that i have in my possession was there too: [[Charles Leiserson|Leiserson]]. Lucky i could exchange a few words during the game with him.
Cilk really is a very promising language. In contradiction to all my big efforts to parallellize [[Diep|DIEP]], writing in Cilk this goes a lot simpler. Regrettably when starting the parallel version of DIEP, there was no port of CILK to windows (the first demand for something is that it must work both in windows and linux before i can use it; interface is of course something different) otherwise i might have done better in paderborn.
Anyone who still must start his parallel project here gets a free tip from me:
Don't go fiddle with difficult parallellization, simply use CILK, let that language handle the parallellism and keep only busy making a good program!
The alternative to Cilk is years of bugfixing the parallel code.
[[FILE:ParallelExperts1999.jpg|none|border|text-bottom]]
Talking Cilk at [[WCCC 1999]]: [[Vincent Diepeveen]], [[Don Dailey]] and [[Charles Leiserson]]
=Cilk++=
MIT licensed Cilk technology to ''Cilk Arts, Inc.'', a venture-funded start-up founded by [[Charles Leiserson]] and [[Matteo Frigo]]. Cilk Arts developed ''Cilk++,'' a quantum improvement over MIT Cilk, which includes full support for [[Cpp|C++]], parallel loops, and superior interoperability with serial code.
=Intel Cilk Plus=
In July 2009 [[Intel|Intel Corporation]] acquired ''Cilk Arts'' <ref>[http://www.ddj.com/cpp/218900367 Intel Acquires Cilk++ Technology], [http://www.ddj.com/ Dr. Dobb's], August 01, 2009</ref> <ref>[https://en.wikipedia.org/wiki/Intel_Cilk_Plus Intel Cilk Plus from Wikipedia]</ref>. Intel Cilk Plus adopts simplifications, proposed by ''Cilk Arts'' in Cilk++, to eliminate the need for several of the original Cilk keywords while adding the ability to spawn functions and to deal with variables involved in reduction operations. Intel Cilk Plus differs from Cilk and Cilk++ by adding array extensions, being incorporated in a commercial compiler, and compatibility with existing debuggers <ref>[https://en.wikipedia.org/wiki/Cilk Cilk from Wikipedia]</ref>.
=See also=
* [[ABDADA]]
* [[CilkChess]]
* [[Jamboree]]
* [[Parallel Search]]
* [[Shared Hash Table]]
* [[Star Socrates|*Socrates]]
=Publications=
<ref>[http://supertech.csail.mit.edu/papers.html SuperTech Paper Listing]</ref>
* [[Robert Blumofe|Robert D. Blumofe]], [[Chris Joerg|Christopher F. Joerg]], [[Bradley Kuszmaul|Bradley C. Kuszmaul]], [[Charles Leiserson|Charles E. Leiserson]], [[Keith H. Randall]], [[Yuli Zhou]] ('''1995'''). ''Cilk: An Efficient Multithreaded Runtime System'' Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) Santa Barbara, California Pg. 207–216, [http://supertech.csail.mit.edu/papers/PPoPP95.pdf pdf]
* [[Phil Lisiecki|Philip Andrew Lisiecki]] ('''1996'''). ''Macro-Level Scheduling in the Cilk Network of Workstations Environment'', Masters Thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology]], [http://supertech.csail.mit.edu/papers/lisiecki-msthesis.pdf pdf]
* [[Chris Joerg|Christopher F. Joerg]] ('''1996'''). ''The Cilk System for Parallel Multithreaded Computing''. Ph. D. Thesis, Department of Electrical Engineering and Computer Science, [[Massachusetts Institute of Technology]], [http://supertech.csail.mit.edu/papers/joerg-phd-thesis.pdf pdf]
* [[Matteo Frigo]], [[Charles Leiserson|Charles E. Leiserson]], [[Keith H. Randall]] ('''1998'''). ''The Implementation of the Cilk-5 Multithreaded Language''. Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, Montreal, Quebec, Canada, Pg 212–223, [http://supertech.csail.mit.edu/papers/cilk5.pdf pdf]
* [[Don Dailey]], [[Charles Leiserson|Charles E. Leiserson]] ('''2001'''). ''Using Cilk to Write Multiprocessor Chess Programs'', [[Advances in Computer Games 9]], [http://supertech.csail.mit.edu/papers/icca99.pdf pdf]
* [http://www.cs.rice.edu/~vs3/home/Vivek_Sarkar.html Vivek Sarkar] ('''2008'''). ''Shared-Memory Parallel Programming with OpenMP''. [https://en.wikipedia.org/wiki/Rice_University Rice University], [http://www.cs.rice.edu/~vs3/comp422/lecture-notes/comp422-lec7-s08-v1.pdf slides as pdf]
* [[Matteo Frigo]], [http://www.plaxo.com/profile/show/227634457468?pk=a7b8fd342887637e7e469951fbfa6ed308f28640 Pablo Halpern], [[Charles Leiserson|Charles E. Leiserson]], [http://venturebeatprofiles.com/person/profile/stephen-lewin-berlin Stephen Lewin-Berlin] ('''2009 '''). ''Reducers and Other Cilk++ Hyperobjects''. Cilk Arts, Inc., [http://www.fftw.org/~athena/papers/hyper.pdf pdf]
* [http://ai.arizona.edu/people/alumni/milind/ Milind Chabbi] ('''2010'''). ''Cilk and Cilk++ Multithreaded Languages''. [http://www.cs.rice.edu/~johnmc/comp522/lecture-notes/COMP522-2010-Lecture8-Cilk.pdf pdf]
* [http://www.cs.rice.edu/~johnmc/ John Mellor-Crummey] ('''2011'''). ''Shared-memory Parallel Programming with Cilk''. [https://en.wikipedia.org/wiki/Rice_University Rice University], [http://www.clear.rice.edu/comp422/lecture-notes/comp422-2011-Lecture4-Cilk.pdf slides as pdf]
=Manuals=
* [http://supertech.csail.mit.edu/cilk/manual-5.4.6.pdf Cilk 5.4.6. Reference Manual] (pdf)
* [http://software.intel.com/sites/products/cilk-plus/cilk_plus_language_specification.pdf Intel® Cilk™ Plus Language Specification] (pdf)
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=29601 Cilk++] by [[Gerd Isenberg]], [[CCC]], August 30, 2009
=External Links=
* [https://en.wikipedia.org/wiki/Cilk Cilk from Wikipedia]
* [http://supertech.csail.mit.edu/cilk/ The Cilk Project] from [[Massachusetts Institute of Technology|MIT]]
* [https://en.wikipedia.org/wiki/Intel_Cilk_Plus Intel Cilk Plus from Wikipedia]
* [http://software.intel.com/en-us/articles/intel-cilk-plus-specification/ Intel® Cilk™ Plus Specification - Intel® Software Network]
* Commercializing MIT's Cilk Project by [[Charles Leiserson]], [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=XCO5-3Md4LI|alignment=left|valignment=top}}
=References=
<references />
'''[[Languages|Up one Level]]'''
