Cilk (pronounced "silk") is a C-based, general-purpose programming language designed for multithreaded parallel computing. Cilk started as in the mid 90s as a project at the Supertech research group in the MIT Labroratory headed by 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 ANSI C, the commercial Cilk++ by Cilk Arts, which extended the Cilk model to C++, and after Intel acquired Cilk Arts in 2009, Intel Cilk Plus. In November 2010, Intel published a language and an ABI specification to enable other compilers to implement Cilk Plus [1].
Parallel Chess
Cilk's testbeds in the 90s were chess programs using a parallel search. *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.
The keyword "cilk" defines a function which can spawned as a new 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 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.
Parallel Alpha-Beta
This is how an alpha-beta search routine was implemented with Cilk-5 [3], using the five keywords cilk, spawn, sync, inlet and abort:
cilk int search( position *prev, int move, int depth ){
position cur;int bestscore =-oo, num_moves, mv, sc, cutoff =false;
inlet voidcatch(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;}
Actually the big professor who has written so many books that i have in my possession was there too: 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, 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.
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 C++, parallel loops, and superior interoperability with serial code.
Intel Cilk Plus
In July 2009 Intel Corporation acquired Cilk Arts[5][6]. 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 [7].
Matteo Frigo, 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, pdf
Table of Contents
Cilk (pronounced "silk") is a C-based, general-purpose programming language designed for multithreaded parallel computing. Cilk started as in the mid 90s as a project at the Supertech research group in the MIT Labroratory headed by 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 ANSI C, the commercial Cilk++ by Cilk Arts, which extended the Cilk model to C++, and after Intel acquired Cilk Arts in 2009, Intel Cilk Plus. In November 2010, Intel published a language and an ABI specification to enable other compilers to implement Cilk Plus [1].
Parallel Chess
Cilk's testbeds in the 90s were chess programs using a parallel search. *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 GNU General Public License [2].The keyword "cilk" defines a function which can spawned as a new 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 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.
Parallel Alpha-Beta
This is how an alpha-beta search routine was implemented with Cilk-5 [3], using the five keywords cilk, spawn, sync, inlet and abort:Quote
by Vincent Diepeveen after WCCC 1999 [4]:Cilk really is a very promising language. In contradiction to all my big efforts to parallellize 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.
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 C++, parallel loops, and superior interoperability with serial code.Intel Cilk Plus
In July 2009 Intel Corporation acquired Cilk Arts [5] [6]. 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 [7].See also
Publications
[8]Manuals
Forum Posts
External Links
References
What links here?
Up one Level