Cilk,Cilk++,Cilk Plus andOpenCilk aregeneral-purposeprogramming languages designed formultithreadedparallel computing. They are based on theC andC++ programming languages, which they extend with constructs to express parallel loops and thefork–join idiom.

Originally developed in the 1990s at theMassachusetts Institute of Technology (MIT) in the group ofCharles E. Leiserson, Cilk was later commercialized as Cilk++ by a spinoff company, Cilk Arts. That company was subsequently acquired byIntel, which increased compatibility with existing C and C++ code, calling the result Cilk Plus. After Intel stopped supporting Cilk Plus in 2017, MIT is again developing Cilk in the form of OpenCilk.

The Cilk programming language grew out of three separate projects at the MIT Laboratory for Computer Science:^[3]

• Theoretical work on scheduling multi-threaded applications.
• StarTech – a parallelchess program built to run on the Thinking Machines Corporation's Connection Machine model CM-5.
• PCM/Threaded-C – a C-based package for scheduling continuation-passing-style threads on the CM-5

In April 1994 the three projects were combined and christened "Cilk". The name Cilk is not an acronym, but an allusion to "nice threads" (silk) and the C programming language. The Cilk-1 compiler was released in September 1994.

The original Cilk language was based onANSI C, with the addition of Cilk-specific keywords to signal parallelism. When the Cilk keywords are removed from Cilk source code, the result should always be a valid C program, called theserial elision (orC elision) of the full Cilk program, with the same semantics as the Cilk program running on a single processor. Despite several similarities,^[which?] Cilk is not directly related to AT&T Bell Labs'Concurrent C.

Cilk was implemented as a translator to C, targeting theGNU C Compiler (GCC). The last version, Cilk 5.4.6, is available from the MIT Computer Science and Artificial Intelligence Laboratory (CSAIL), but is no longer supported.^[4]

A showcase for Cilk's capabilities was the Cilkchess parallel chess-playing program, which won several computer chess prizes in the 1990s, including the 1996 Open Dutch Computer Chess Championship.^[5]

Prior toc. 2006, the market for Cilk was restricted to high-performance computing. The emergence of multicore processors in mainstream computing meant that hundreds of millions of new parallel computers were being shipped every year. Cilk Arts was formed to capitalize on that opportunity: in 2006, Leiserson launched Cilk Arts to create and bring to market a modern version of Cilk that supports the commercial needs of an upcoming generation of programmers. The company closed a Series A venture financing round in October 2007, and its product, Cilk++ 1.0, shipped in December, 2008.

Cilk++ differs from Cilk in several ways: support for C++, support for loops, andhyperobjects – a new construct designed to solve data race problems created by parallel accesses to global variables. Cilk++ wasproprietary software. Like its predecessor, it was implemented as a Cilk-to-C++ compiler. It supported theMicrosoft and GNU compilers.

On July 31, 2009, Cilk Arts announced on its web site that its products and engineering team were now part ofIntel Corp. In early 2010, the Cilk website atwww.cilk.com began redirecting to the Intel website (as of early 2017, the original Cilk website no longer resolves to a host). Intel and Cilk Arts integrated and advanced the technology further resulting in a September 2010 release of IntelCilk Plus.^[6][7] 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. Cilk Plus differs from Cilk and Cilk++ by adding array extensions, being incorporated in a commercial compiler (from Intel), and compatibility with existing debuggers.^[8]

Cilk Plus was first implemented in theIntel C++ Compiler with the release of the Intel compiler in Intel Composer XE 2010.^{[citation needed]} An open source (BSD-licensed) implementation was contributed by Intel to theGNU Compiler Collection (GCC), which shipped Cilk Plus support in version 4.9,^[9] except for the_Cilk_for keyword, which was added in GCC 5.0. In February 2013, Intel announced aClangfork with Cilk Plus support.^[10] The Intel Compiler, but not the open source implementations, comes with arace detector and a performance analyzer.

Intel later discontinued it, recommending its users switch to instead using eitherOpenMP orIntel's own TBB library for their parallel programming needs.^[11]

In the original MIT Cilk implementation, the first Cilk keyword is in factcilk, which identifies a function which is written in Cilk. Since Cilk procedures can call C procedures directly, but C procedures cannot directly call orspawn Cilk procedures, this keyword is needed to distinguish Cilk code from C code. Cilk Plus removes this restriction, as well as thecilk keyword, so C and C++ functions can call into Cilk Plus code and vice versa.

In May, 2017, GCC 7.1 was released and marked Cilk Plus support as deprecated.^[12] Intel itself announced in September 2017 that they would deprecate Cilk Plus with the 2018 release of the Intel Software Development Tools.^[11] In May 2018, GCC 8.1 was released with Cilk Plus support removed.^[13]

After Cilk Plus support was deprecated by Intel, MIT has taken on the development of Cilk in the OpenCilk implementation, focusing on the LLVM/Clang fork now termed "Tapir".^[11][14] OpenCilk remains largely compatible with Intel Cilk Plus.^[15] Its first stable version was released in March 2021.^[16]

The principle behind the design of the Cilk language is that the programmer should be responsible forexposing the parallelism, identifying elements that can safely be executed in parallel; it should then be left to the run-time environment, particularly thescheduler, to decide during execution how to actually divide the work between processors. It is because these responsibilities are separated that a Cilk program can run without rewriting on any number of processors, including one.

Cilk's main addition to C are two keywords that together allow writing task-parallel programs.

• Thespawn keyword, when preceding a function call (spawn f(x)), indicates that the function call (f(x)) can safely run in parallel with the statements following it in the calling function. Note that the scheduler is notobligated to run this procedure in parallel; the keyword merely alerts the scheduler that it can do so.
• Async statement indicates that execution of the current function cannot proceed until all previously spawned function calls have completed. This is an example of abarrier method.

(In Cilk Plus, the keywords are spelled_Cilk_spawn and_Cilk_sync, orcilk_spawn andcilk_sync if the Cilk Plus headers are included.)

Below is arecursive implementation of theFibonacci function in Cilk, with parallel recursive calls, which demonstrates thespawn, andsync keywords. The original Cilk required any function using these to be annotated with thecilk keyword, which is gone as of Cilk Plus. (Cilk program code is not numbered; the numbers have been added only to make the discussion easier to follow.)

cilkintfib(intn){if(n<2){returnn;}else{intx,y;x=spawnfib(n-1);y=spawnfib(n-2);sync;returnx+y;}}

If this code was executed by asingle processor to determine the value offib(2), that processor would create aframe forfib(2), and execute lines 1 through 5. On line 6, it would create spaces in the frame to hold the values ofx andy. On line 8, the processor would have to suspend the current frame, create a new frame to execute the procedurefib(1), execute the code of that frame until reaching a return statement, and then resume thefib(2) frame with the value of fib(1) placed intofib(2)'sx variable. On the next line, it would need to suspend again to executefib(0) and place the result infib(2)'sy variable.

When the code is executed on amultiprocessor machine, however, execution proceeds differently. One processor starts the execution offib(2); when it reaches line 8, however, thespawn keyword modifying the call tofib(n-1) tells the processor that it can safely give the job to a second processor: this second processor can create a frame forfib(1), execute its code, and store its result infib(2)'s frame when it finishes; the first processor continues executing the code offib(2) at the same time. A processor is not obligated to assign a spawned procedure elsewhere; if the machine only has two processors and the second is still busy onfib(1) when the processor executingfib(2) gets to the procedure call, the first processor will suspendfib(2) and executefib(0) itself, as it would if it were the only processor. Of course, if another processor is available, then it will be called into service, and all three processors would be executing separate frames simultaneously.

(The preceding description is not entirely accurate. Even though the common terminology for discussing Cilk refers to processors making the decision to spawn off work to other processors, it is actually the scheduler which assigns procedures to processors for execution, using a policy calledwork-stealing, described later.)

If the processor executingfib(2) were to execute line 13 before both of the other processors had completed their frames, it would generate an incorrect result or an error;fib(2) would be trying to add the values stored inx andy, but one or both of those values would be missing. This is the purpose of thesync keyword, which we see in line 11: it tells the processor executing a frame that it must suspend its own execution until all the procedure calls it has spawned off have returned. Whenfib(2) is allowed to proceed past thesync statement in line 11, it can only be becausefib(1) andfib(0) have completed and placed their results inx andy, making it safe to perform calculations on those results.

The code example above uses the syntax of Cilk-5. The original Cilk (Cilk-1) used a rather different syntax that required programming in an explicitcontinuation-passing style, and the Fibonacci examples looks as follows:^[17]

threadfib(contintk,intn){if(n<2){send_argument(k,n);}else{contintx,y;spawn_nextsum(k,?x,?y);spawnfib(x,n-1);spawnfib(y,n-2);}}threadsum(contintk,intx,inty){send_argument(k,x+y);}

Insidefib's recursive case, thespawn_next keyword indicates the creation of asuccessor thread (as opposed to thechild threads created byspawn), which executes thesum subroutine after waiting for thecontinuation variablesx andy to be filled in by the recursive calls. The base case andsum use asend_argument(k, n) operation to set their continuation variablek to the value ofn, effectively "returning" the value to the successor thread.

The two remaining Cilk keywords are slightly more advanced, and concern the use ofinlets. Ordinarily, when a Cilk procedure is spawned, it can return its results to the parent procedure only by putting those results in a variable in the parent's frame, as we assigned the results of our spawned procedure calls in the example tox andy.

The alternative is to use an inlet. An inlet is a function internal to a Cilk procedure which handles the results of a spawned procedure call as they return. One major reason to use inlets is that all the inlets of a procedure are guaranteed to operateatomically 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.

• Theinlet keyword identifies a function defined within the procedure as an inlet.
• Theabort keyword can only be used inside an inlet; it tells the scheduler that any other procedures that have been spawned off by the parent procedure can safely be aborted.

Inlets were removed when Cilk became Cilk++, and are not present in Cilk Plus.

Cilk++ added an additional construct, the parallel loop, denotedcilk_for in Cilk Plus. These loops look like

voidloop(int*a,intn){#pragma cilk grainsize = 100// optionalcilk_for(inti=0;i<n;i++){a[i]=f(a[i]);}}

This implements theparallel map idiom: the body of the loop, here a call tof followed by an assignment to the arraya, is executed for each value ofi from zero ton in an indeterminate order. The optional "grain size"pragma determines thecoarsening: any sub-array of one hundred or fewer elements is processed sequentially. Although the Cilk specification does not specify the exact behavior of the construct, the typical implementation is a divide-and-conquer recursion,^[18] as if the programmer had written

staticvoidrecursion(int*a,intstart,intend){if(end-start<=100){// The 100 here is the grainsize.for(inti=start;i<end;i++){a[i]=f(a[i]);}}else{intmidpoint=start+(end-start)/2;cilk_spawnrecursion(a,start,midpoint);recursion(a,midpoint,end);cilk_sync;}}voidloop(int*a,intn){recursion(a,0,n);}

The reasons for generating a divide-and-conquer program rather than the obvious alternative, a loop that spawn-calls the loop body as a function, lie in both the grainsize handling and in efficiency: doing all the spawning in a single task makes load balancing a bottleneck.^[19]

A review of various parallel loop constructs on HPCwire found thecilk_for construct to be quite general, but noted that the Cilk Plus specification did not stipulate that its iterations need to be data-independent, so a compiler cannotautomatically vectorize acilk_for loop. The review also noted the fact that reductions (e.g., sums over arrays) need additional code.^[18]

Cilk++ added a kind of objects calledhyperobjects, that allow multiple strands to share state withoutrace conditions and without using explicit locks. Each strand has a view on the hyperobject that it can use and update; when the strands synchronize, the views are combined in a way specified by the programmer.^[20]

The most common type of hyperobject is a reducer, which corresponds to the reduction clause inOpenMP or to the algebraic notion of amonoid. Each reducer has anidentity element and anassociative operation that combines two values. The archetypal reducer issummation of numbers: the identity element is zero, and the associativereduce operation computes a sum. This reducer is built into Cilk++ and Cilk Plus:

// Compute ∑ foo(i) for i from 0 to N, in parallel.cilk::reducer_opadd<float>result(0);cilk_for(inti=0;i<N;i++)result+=foo(i);

Other reducers can be used to constructlinked lists or strings, and programmers can define custom reducers.

A limitation of hyperobjects is that they provide only limiteddeterminacy. Burckhardtet al. point out that even the sum reducer can result in non-deterministic behavior, showing a program that may produce either1 or2 depending on the scheduling order:^[21]

voidadd1(cilk::reducer_opadd<int>&r){r++;}// ...cilk::reducer_opadd<int>r(0);cilk_spawnadd1(r);if(r==0){r++;}cilk_sync;output(r.get_value());

Intel Cilk Plus adds notation to express high-leveloperations on entire arrays orsections of arrays; e.g., anaxpy-style function that is ordinarily written

// y ← α x + yvoidaxpy(intn,floatalpha,constfloat*x,float*y){for(inti=0;i<n;i++){y[i]+=alpha*x[i];}}

can in Cilk Plus be expressed as

y[0:n] += alpha * x[0:n];

This notation helps the compiler to effectively vectorize the application. Intel Cilk Plus allows C/C++ operations to be applied to multiple array elements in parallel, and also provides a set of built-in functions that can be used to perform vectorized shifts, rotates, and reductions. Similar functionality exists inFortran 90; Cilk Plus differs in that it never allocates temporary arrays, so memory usage is easier to predict.

In Cilk Plus, an elemental function is a regular function which can be invoked either on scalar arguments or on array elements in parallel. They are similar to the kernel functions ofOpenCL.

This pragma gives the compiler permission to vectorize a loop even in cases where auto-vectorization might fail. It is the simplest way to manually apply vectorization.

The Cilk scheduler uses a policy called "work-stealing" to divide procedure execution efficiently among multiple processors. Again, it is easiest to understand if we look first at how Cilk code is executed on a single-processor machine.

The processor maintains astack on which it places each frame that it has to suspend in order to handle a procedure call. If it is executingfib(2), and encounters a recursive call tofib(1), it will savefib(2)'s state, including its variables and where the code suspended execution, and put that state on the stack. It will not take a suspended state off the stack and resume execution until the procedure call that caused the suspension, and any procedures called in turn by that procedure, have all been fully executed.

With multiple processors, things of course change. Each processor still has a stack for storing frames whose execution has been suspended; however, these stacks are more likedeques, in that suspended states can be removed from either end. A processor can still only remove states from itsown stack from the same end that it puts them on; however, any processor which is not currently working (having finished its own work, or not yet having been assigned any) will pick another processor at random, through the scheduler, and try to "steal" work from the opposite end of their stack – suspended states, which the stealing processor can then begin to execute. The states which get stolen are the states that the processor stolen from would get around to executing last.

• Grand Central Dispatch
• Intel Concurrent Collections (CnC)
• Intel Parallel Building Blocks (PBB)
  • Intel Array Building Blocks (ArBB)
• Intel Parallel Studio
• NESL
• OpenMP
• Parallel computing
• Sieve C++ Parallel Programming System
• Threading Building Blocks (TBB)
• Unified Parallel C

• Official website for OpenCilk
• Intel's Cilk Plus website
• Cilk Project website at MIT
• Arch D. Robison,"Cilk Plus: Language Support for Thread and Vector Parallelism" and"Parallel Programming with Cilk Plus", July 16, 2012.

• Concurrent programming languages
• C programming language family
• Massachusetts Institute of Technology software
• Intel software
• Programming languages created in 1994

• Webarchive template wayback links
• Articles with short description
• Short description is different from Wikidata
• All articles with specifically marked weasel-worded phrases
• Articles with specifically marked weasel-worded phrases from September 2015
• All articles with unsourced statements
• Articles with unsourced statements from March 2015
• Official website different in Wikidata and Wikipedia
• Articles with example code