Algorithms and Parallel Computing

6.3 CILK++

Cilk++ is a language extension programming tool. Cilk++ is suited for divide-and-conquer problems where the problem can be divided into parallel independent tasks and the results can be combined afterward. As such, the programmer bears the responsibility of structuring the program to expose its inherent parallelism. Cilk’s runtime system bears the responsibility of scheduling the computational tasks on the parallel processor system. The techniques we discuss in this book give the programmer insight on the alternative parallelism options available for a given algorithm. The application developer can use a few key words provided by Cilk++ to convert a standard serial program into a parallel program. A standard C++ program can be converted to a Cilk++ program running Intel’s Cilk++ system developers kit (SDK) by doing these initial steps [64]:

1. Ensure that the serial C++ program is bug free.

2. Rename source file extension from .cpp to .cilk.

3. Add #include <cilk.h>.

4. Rename the main() function to cilk_main().

At this stage, the program is a program that has no parallelism yet. The programmer must add a few key words to the program, such as

• cilk, which alerts the compiler that this is a parallel program;
• cilk_spawn, which creates a locally spawned function that can be executed in parallel with other tasks;
• cilk_sync, which forces the current threads to wait for all locally spawned functions to be completed; thus, all cilk_spawn function must be completed first before ...