Cilk

From Chessprogramming wiki
Jump to: navigation, search

Home * Programming * Languages * Cilk

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: 

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;
}

Quote

by Vincent Diepeveen after WCCC 1999 [4]: 

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.
ParallelExperts1999.jpg

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

1995 ...

2000 ...

2010 ...

Manuals

Forum Posts

External Links

References

  1. ↑ Intel® Cilk™ Plus Specification - Intel® Software Network
  2. ↑ cilk-5.4.6.tar.gz
  3. ↑ Don Dailey, Charles E. Leiserson (2001). Using Cilk to Write Multiprocessor Chess Programs, Advances in Computer Games 9, pdf
  4. ↑ DIEP parallel in Paderborn - technical and detailed story by Vincent Diepeveen, CCC, June 28, 1999
  5. ↑ Intel Acquires Cilk++ Technology, Dr. Dobb's, August 01, 2009
  6. ↑ Intel Cilk Plus from Wikipedia
  7. ↑ Cilk from Wikipedia
  8. ↑ SuperTech Paper Listing
  9. ↑ Work stealing from Wikipedia

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Cilk&oldid=22886"