Языки Cilk: от MIT до Intel и OpenCilk

Programming language

Cilk, Cilk++, Cilk Plus and OpenCilk are general purpose programming languages designed for multithreaded parallel computing. They are based on the C and C++ programming languages, which they extend with constructs to express parallel loops and the fork–join idiom. Originally developed in the 1990s at the Massachusetts Institute of Technology (MIT) in the group of Charles E. Leiserson, Cilk was later commercialized as Cilk++ by a spinoff company, Cilk Arts. That company was subsequently acquired by Intel, 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.

Prior to c. 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, and hyperobjects a new construct designed to solve data race problems created by parallel accesses to global variables. Cilk++ was proprietary software. Like its predecessor, it was implemented as a Cilk to C++ compiler. It supported the Microsoft and GNU compilers.

On July 31, 2009, Cilk Arts announced on its web site that its products and engineering team were now part of Intel Corp. In early 2010, the Cilk website at www. 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 Intel Cilk Plus. 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. Cilk Plus was first implemented in the Intel C++ Compiler with the release of the Intel compiler in Intel Composer XE 2010. An open source (BSD licensed) implementation was contributed by Intel to the GNU Compiler Collection (GCC), which shipped Cilk Plus support in version 4.9, except for the keyword, which was added in GCC 5.0. In February 2013, Intel announced a Clang fork with Cilk Plus support. The Intel Compiler, but not the open source implementations, comes with a race detector and a performance analyzer. Intel later discontinued it, recommending its users switch to instead using either OpenMP or Intel's own TBB library for their parallel programming needs.

In the original MIT Cilk implementation, the first Cilk keyword is in fact cilk, which identifies a function which is written in Cilk. Since Cilk procedures can call C procedures directly, but C procedures cannot directly call or spawn Cilk procedures, this keyword is needed to distinguish Cilk code from C code. Cilk Plus removes this restriction, as well as the cilk 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. Intel itself announced in September 2017 that they would deprecate Cilk Plus with the 2018 release of the Intel Software Development Tools.

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". OpenCilk remains largely compatible with Intel Cilk Plus. Its first stable version was released in March 2021.

The principle behind the design of the Cilk language is that the programmer should be responsible for exposing the parallelism, identifying elements that can safely be executed in parallel; it should then be left to the run time environment, particularly the scheduler, 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.

The two remaining Cilk keywords are slightly more advanced, and concern the use of inlets. 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 to x and y. 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 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. The inlet keyword identifies a function defined within the procedure as an inlet. The abort 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.

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 of OpenCL.

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 a stack on which it places each frame that it has to suspend in order to handle a procedure call. If it is executing fib(2), and encounters a recursive call to fib(1), it will save fib(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 like deques, in that suspended states can be removed from either end. A processor can still only remove states from its own 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.