Cilk Tutorial

1.1. About this Tutorial

This tutorial is designed as an introductory guide to parallelizing C and C++ code using the Cilk language extension. This tutorial assumes that you have a fair knowledge of C and/or C++. The Intel® Cilk™ documentation was used to build this tutorial.

The authors of this tutorial are Michael Graf and Andrei Papancea. Its creation was partially supported by National Science Foundation's "Transforming Undergraduate Education in Science, Technology, Engineering and Mathematics (TUES)" program under Award No. DUE-1044299, the Andrew W. Mellon Foundation, and the Baker-Velde Award. It is currently being maintained by David Bunde. Please let us know what you think of the tutorial so that we can continue to improve it.

1.2. About Cilk

Intel® Cilk™ Plus is a user-friendly language add-on to the C and C++ programming languages, implemented by the Intel® C++ Compiler. Since almost all modern day devices have a multicore processor, parallelism is becoming increasingly relevant. The problem is that most popular languages were not created with the idea of parallelism in mind, and if they do support this feature it is usually unintuitive and difficult to implement. Intel® Cilk™ Plus provides a simple to use library that makes parallelizing C and C++ code trivial.

Intel® Cilk™ Plus adds only 3 keywords to C and C++: cilk_for, cilk_spawn, and cilk_sync. With only three keywords you can start writing C and C++ parallel code in minutes, that runs significantly faster than its serial counterpart, so you can better take advantage of multicore machines.

2.1. cilk_spawn

The cilk_spawn keyword tells the compiler that the function that cilk_spawn precedes may run in parallel with the caller - but is not required to. A cilk_spawn statement can be called in the following ways:

When a function spawns another function the original function is knows as the parent, while the other function is know as the child. It is illegal to spawn a function as the argument of another function such as: Here's a more concrete use of cilk_spawn. In the example below, we want to print the message "Hello world!" and then "Done!" right before the program ends. Run the code a couple of times. What you probably noticed is that messages will print out of order most of the time. This is because cilk_spawn is making them run asynchroniously. Since the hello() and world() functions each have loops inside them, "Done!" can sometimes print before hello(), world() or both. Note that we used the loops to generate more work for the program - if you remove the loops the statements will print in order, which means that you need a substantial amount of work to take full advantage of cilk_spawn's power.

2.2. cilk_sync

Looking at the previous example you can see some side effects of running things in parallel - tasks will run out of order most of the time. Sometimes you want certain tasks to run in order because they might be dependent on each other, case in which you would use cilk_sync.

When you place cilk_sync somewhere in the code it causes all previously spawed tasks to wait for each other to complete before the program can continue. Getting back to our previous "Hello world! Done!" example, placing a single cilk_sync statement right before "Done!" is printed can ensure that "Done!" is printed only after the two spawed tasks, hello() and world(), respectively, have finished their work.

2.3. cilk_for

The cilk_for construct specifies a loop that permits loop iterations to run in parallel. This is a the parallel version of a normal C/C++ for loop. cilk_for divides a loop into chunks containing one or more loop iterations. Once the loop is broken down, each chunk is executed on a specific thread of execution.

Let's take a look at a quick example, where we use cilk_for to sum up in parallel the first 10,000 integers:

Note that in order to use Cilk keywords and features, you have to include the Cilk library like above. Furthermore, notice how the only difference in this example between the native C version of the code and the Cilk version of it, is the replacement of the for keyword with the cilk_for one. Yet again, it is trivial to parallelize already-written C/C++ code using Cilk. Finally, note that the program above will return a different answer almost every time. That's because a race condition is created, about which we will talk and solve later in the tutorial.

There are certain restrictions on cilk_for that you should take into account. First, you cannot change the loop control variable in the loop body. So, the following is illegal: Moving on, you cannot declare the loop control variable outside the loop in C++, as opposed to C. More exactly, the following code will not work in C++: To fix the above code for C++ you need to declare the loop control variable i, in the header of the cilk_for loop: As we mentioned previously, the cilk_for statement divides the loop into multiple smaller chunks, that run on specific threads of execution. The maximum number of iterations in each chunk is defined as the grain size. The actual number of iterations run as a chunk will often be less than the grain size.

In a loop with many iterations, a large grain size can significantly reduce overhead. Alternately, in a loop with few iterations, a small grain size can improve the parallelization of the program and thus increase performance as the number of processors increases.

In order to define the grain size you need to use the cilk grainsize pragma (used to tell the compiler to use implementation-dependent features). To change the default value of the grain size add the following right before the cilk_for statement for which you would like to change the grain size: The expression above can be a number, an arithmetic operation or a function call. The default value of the grainsize, which works well in most cases is: where N is the number of loop iterations and p is the number of workers (threads) created during the current program execution.

When it executes the loop, the Intel compiler breaks down every loop in half until the number of loop iterations of each loop is smaller than or equal to the grainsize. For example, if the grainsize is 4 and the number of loop iterations is 64, the loop will be broken down into 16 chunks with 4 iterations each. If the number of iterations divided by the grain size has no remainder, then the number of chunks that are created is equal to the number of iterations divided by the grain size (in our example with a grain size of 4 and 64 iterations, the loop is broken down into 16 chunks). On the other hand, if this division returns a remainder, the number of chunks might be different than the integer division between the two parameters, number of iterations and grain size, respectively (think of the case where the number of iterations is 64 and the grain size is 5).

Note that if you change the grain size, test the performance of your program to ensure that you have made the loop faster, not slower.

The example below uses cilk_for to count all the prime numbers up to 10,000,000. We use grainsize to adjust the number of worker threads created, because there is an implicit cilk_sync after every cilk_for loop iteration. Thus, unless we adjust the grainsize there is going to be a lot of overhead - having 10,000,000 cilk_syncs is not probably something that you want. Let's take a look: Once again, just like in the summation example above, there is a race condition that we will solve in the next two sections Locks and Reducers (C++ only).

2.4. Locks

Recall for a second our previous example, in which we sum up the first 10,000 integers. Whenever we run it we get a different result, because of a race condition. One way to solve this problem is to use locks. Locks are synchronization mechanisms that prevent multiple threads from changing a variable concurrently. Thus, locks help to eliminate data races.

Here is how you can use locks in C (using the pthread.h library) and in C++ (using the tbb/mutex.h library):

Even though locks are a solution to data races, there are a few things that can go wrong. First, deadlock might occur, which is when all the threads are waiting on each other. This is best illustrated by this image. Second, since the threads have to wait on each other, the locked part of the code is seriallized, causing performance issues. In Cilk™, the constructs that solve most of the issues associated with locks, are called reducers, about which we are going to talk in the next section.

2.5. Reducers (C++ Only)

You have seen how locks can be used to solve data race, but some of the problems associated with them can make them a poor solution to the problem. The better solution in Cilk™ are reducers. By definition, a reducer is a variable that can be safely used by multiple threads running in parallel.

The runtime ensures that each thread has access to a private copy of the variable, eliminating the possibility of races without requiring locks. When the threads synchronize, the reducer copies are merged (or reduced) into a single variable. The runtime creates copies only when needed, minimizing overhead.

Getting back to our summation example, where we add up the first 10,000 integers, take a look below at the reducer solution for the race condition problem:

First thing that you need to take care of in order to use a reducer is to include one of the Cilk reducer libraries, that fits the needs of your program most - there are multiple types of reducers: for mathematical operations, for strings, for determining minimum and maximum values of a list etc. For the full list of reducers check out the Intel® Cilk™ documentation. In our case, we need a reducer for a summation, so we will include the reducer_opadd.h library. Next, define the variable susceptible to a race condition as a reducer. Once the operation is complete, in order to retrieve the final value of the computation you need to call the get_value() function on the reducer (reducers are C++ hyperobjects, which is why this section is dedicated to C++ only).