Intel® C++ Compiler 16.0 User and Reference Guide

Using Reducers - More Examples

The following shows how to use a variety of reducers, including the String and List reducers.

String Reducer

reducer<op_string> builds strings of 8-bit characters, and the example uses += (string concatenation) as the update operation. For strings of 16-bit or 32-bit characters, use reducer<op_basic_string> or reducer<op_wstring>.

This example demonstrates how reducers work with the runtime to preserve serial semantics. In a serial for loop, the reducer concatenates each of the characters 'A' to 'Z', and then prints out:

The result string is: ABCDEFGHIJKLMNOPQRSTUVWXYZ

The cilk_for loop uses a divide-and-conquer algorithm to break this into two halves, and then break each half into two halves, until it gets down to a reasonable size chunk of work. Therefore, the first worker might build the string "ABCDEF", the second might build "GHIJKLM", the third might build "NOPQRS", and the fourth might build "TUVWXYZ". The runtime system calls the reducer's reduce method so that the final result is a string containing the letters of the English alphabet in order.

String concatenation is associative (but not commutative); the order of operations is not important. For instance, the following two expressions are equal:

The result is always the same, regardless of how cilk_for creates the work chunks.

The call to get_value() performs the reduce operation and concatenates the substrings into a single output string. Why use get_value() to fetch the string? It makes you think about whether fetching the value at this time makes sense. You could fetch the value whenever you want, but, in general, you should not. The result might be an unexpected intermediate value, and, in any case, the intermediate value is meaningless. In this example, the result might be "GHIJKLMNOPQRS", the concatenation of "GHIJKLM" and "NOPQRS".

Intel® Cilk™ Plus reducers provide serial semantics; these serial semantics are only guaranteed at the end of the parallel calculation, such as at the end of a cilk_for loop, after the runtime system has performed all the reduce operations. You should not call get_value() within the cilk_for loop; the value is unpredictable and meaningless since results from other loop iterations are being combined (reduced) with the results in the calling iteration.

Unlike the previous example, which adds integers, the reduce operation is not commutative. You could use similar code to append (or prepend) elements to a list using the reducer library's reducer_list_append, as is shown in the example in the next section. 

#include <cilk/cilk.h>
#include <cilk/reducer_string.h>
#include <iostream>
int main()
{
   //...
   cilk::reducer<cilk::op_string> result;
   cilk_for (std::size_t i = 'A'; i < 'Z'+1; ++i){
     *result += (char)i;
   }
   std::cout << "The result string is: "
             << result.get_value() <<std::endl;
   return 0;
}

In this and other examples, each loop iteration only updates the reducer once; however, you can have several updates in each iteration. For example: 

cilk_for (std::size_t i = 'A'; i < 'Z'+1; ++i){
   *result += (char)i;
   *result += tolower((char)i);
}

This is valid and produces the following string:

AaBb...Zz

List Reducer (With User-Defined Type)

reducer<op_list_append> creates lists, using the STL list append method as the update operation. The identity is the empty list. The example here is almost identical to the previous string example. The reducer<op_list_append> declaration does, however, require a type, as shown in the following code. 

#include <cilk/cilk.h>
#include <cilk/reducer_list.h>
#include <iostream>
int main()
{
  //...
  cilk::reducer<op_list_append<char> > result;
  cilk_for (std::size_t i = 'A'; i < 'Z'+1; ++i){
     result->push_back ((char)i);
  }

  std::cout << "String = ";
  std::list<char> r;
  r = result.get_value() ;
  for (std::list<char>::iterator i = r.begin();
                                 i != r.end(); ++i){
     std::cout << *i;
  }
  std::cout << std::endl;
}

Reducers in Recursive Functions

Reducers are not limited to update operations within a cilk_for loop. Reducers can work with arbitrary control flow, such as recursively spawned functions. This example illustrates how a reducer can be used to create an in-order list of elements in a tree. The final list will always contain the elements in the same order as in a serial execution, regardless of the number of cores or how the computation is scheduled. 

#include <cilk/reducer_list.h>
Node *target;
cilk::reducer<op_list_append<int> > output_list;
...
// Output the tree with an in-order walk
void walk (Node *x)
{
   if (NULL == x)
     return;
   cilk_spawn walk (x->left);
   output_list->push_back (x->value);
   walk (x->right);
 }
Parent topic: Reducers