Cilk is a parallel programming language developed at MIT by Charles E. Leiserson, Keith H. Randall, and Silviu C. Craciunas. It is based on the C programming language and adds a few keywords to support parallelism.
Cilk programs are executed by a runtime system that manages a pool of worker threads. When a Cilk function is invoked, the runtime system spawns a new thread to execute the function. The spawned thread may in turn spawn other threads, creating a tree of threads.
The Cilk runtime system is designed to work with any parallel programming model, such as shared memory or message passing. However, the most common model is shared memory, where each thread has its own private data, but can also access shared data.
Cilk provides a few keywords to support parallelism. The most important is "cilk_spawn", which spawns a new thread to execute a function. The spawned thread may in turn spawn other threads, creating a tree of threads.
The "cilk_sync" keyword is used to synchronize all threads in a Cilk program. When a thread reaches a "cilk_sync" statement, it waits for all child threads to finish before proceeding. This ensures that all threads have finished their work before the program continues.
The Cilk programming model is based on "divide and conquer". To parallelize a problem, it is divided into smaller subproblems, which are then solved in parallel. This approach is well suited to problems that can be divided into independent subproblems.
A simple example of a Cilk program is the "Hello, World!" program:
#include <stdio.h>
int main() {
cilk_spawn printf("Hello, ");
printf("World!\n");
cilk_sync;
return 0;
}
In this program, the "Hello, World!" string is printed by two threads. The first thread is spawned by the "cilk_spawn" keyword and prints the "Hello, " string. The second thread, which is the main thread, prints the "World!" string. The "cilk_sync" keyword synchronizes the two threads, so that the "World!" string is not printed until the "Hello, " string has been printed.
Cilk is a powerful tool for parallel programming, but it has a few drawbacks. First, Cilk programs can be difficult to understand and debug. Second, the Cilk runtime system can be slow, especially when spawning many threads. Finally, Cilk does not support some important parallel programming models, such as data parallelism.