Intel Cilk Plus Reducers

With Intel Cilk Plus, if the only data races in a site come from updates to an accumulator variable, then you may be able to fix them without locks using a reducer. A reducer works with the Intel Cilk Plus runtime system to create a private accumulator variable for each task, and to combine the task-private accumulator variable results in the correct order as the tasks finish. Reducers can be very efficient, because they do not need locks.

The main requirement for using a reducer is that all the updates to the accumulator use the same associative operation. The Intel Cilk Plus library contains predefined reducers for computing:

• Arithmetic sum, product, minimum, and maximum

• Bitwise and, or, and exclusive or

• List append or prepend

• String append

• ostream output

If none of the library reducers meet your needs, you can easily to create a custom reducer (see the Intel Cilk Plus online documentation).

The following shows annotated serial code example followed by an example of the transformed Intel Cilk Plus code using reducers. Since there are no Intel Advisor annotations that represent reductions, the accumulator variable updates are guarded with lock annotations below:

int sum;
ANNOTATE_SITE_BEGIN(sum_site);
for (int i = 0; i != n; ++i) {
   ANNOTATE_ITERATION_TASK(sum_task);
   ANNOTATE_LOCK_ACQUIRE();
   sum += f(i);
   ANNOTATE_LOCK_RELEASE();
}
ANNOTATE_SITE_END();
printf("The sum is %d\n", sum);

std::string alphabet;
ANNOTATE_SITE_BEGIN(alphabet_site);
for (char letter = 'A'; letter <= 'Z'; ++i) {
    ANNOTATE_ITERATION_TASK(alphabet_task);
    ANNOTATE_LOCK_ACQUIRE();
    alphabet += letter;
    ANNOTATE_LOCK_RELEASE();
}
ANNOTATE_SITE_END();
cout << alphabet << "\n";

To use the Intel Cilk Plus reducers:

• Replace the accumulator variable with an appropriate reducer class.

• De-reference the reducer to update the accumulator variable.

• Retrieve the result with the get_value() function.

Thus, the transformed code when using the Intel® C++ Compiler 14.0 or later is the following:

void IncrementCount() {
   // ANNOTATE_LOCK_ACQUIRE() annotation removed
   (*count)++;     // Increment the reducer
   // ANNOTATE_LOCK_RELEASE() annotation removed
}

#include <cilk/reducer_opadd.h>
// use reducer<op_add<int> > instead of int for the accumulator
cilk::reducer<cilk::op_add<int> > sum;
ANNOTATE_SITE_BEGIN(sum_site);
for (int i = 0; i != n; ++i) {
   ANNOTATE_ITERATION_TASK(sum_task);
   // ANNOTATE_LOCK_ACQUIRE(); lock not needed
   (*sum) += f(i);
   // ANNOTATE_LOCK_RELEASE(); lock not needed
}
ANNOTATE_SITE_END();
printf("The sum is %d\n", sum.get_value());

#include <cilk/reducer_string.h>
// use reducer<op_string> instead of string for the accumulator
cilk::reducer<cilk::op_string> alphabet;
ANNOTATE_SITE_BEGIN(alphabet_site);
for (char letter = 'A'; letter <= 'Z'; ++i) {
    ANNOTATE_ITERATION_TASK(alphabet_task);
    // ANNOTATE_LOCK_ACQUIRE(); lock not needed
    (*alphabet) += letter;
    // ANNOTATE_LOCK_RELEASE(); lock not needed
}
ANNOTATE_SITE_END();
cout << alphabet.get_value() << "\n";

When using a release prior to Intel® C++ Compiler 14.0, the reducer style defined in the library is slightly different. The previous style is supported in 14.0 but is deprecated:

The code example above works only with the C++ language. For types and operations meaningful in C, the same effect can be obtained using special macros:

#include <cilk/reducer_opadd.h>
CILK_C_REDUCER_OPADD(sum, int, 0);    // Declare the reducer
CILK_C_REGISTER_REDUCER(sum);
ANNOTATE_SITE_BEGIN(sum_site);
for (int i = 0; i != n; ++i) {
   ANNOTATE_ITERATION_TASK(sum_task);
   // ANNOTATE_LOCK_ACQUIRE(); lock not needed
   REDUCER_VIEW(sum)++;              // Increment the reducer
   // ANNOTATE_LOCK_RELEASE(); lock not needed
}
ANNOTATE_SITE_END();
CILK_C_UNREGISTER_REDUCER(sum);
printf("The sum is %d\n", REDUCER_VIEW(sum));

The final value of the C reducer is retrieved using REDUCER_VIEW(count).