An explanation of the mechanisms and semantics of reducers should help the more advanced programmer understand the rules governing the use of reducers as well as provide the background needed to write custom reducers.
In the simplest form, a reducer is an object that has a value, an identity, and a reduction function.
The reducers provided in the reducer library provide additional interfaces to help ensure that the reducers are used in a safe and consistent manner.
In this discussion, the object created when the reducer is declared is known as the "leftmost" instance of the reducer.
The following sections present a simple example and discuss the run-time behavior of the system as this program runs.
First, consider the two possible executions of a cilk_spawn, with and without a steal. The behavior of a reducer is very simple:
If no steal occurs, the reducer behaves like a normal variable.
If a steal occurs, the continuation receives a view with an identity value, and the child receives the reducer as it was prior to the spawn. At the corresponding sync, the value in the continuation is merged into the reducer held by the child using the reduce operation, the new view is destroyed, and the original (updated) object survives.
The following diagrams illustrate this behavior:
No steal
There is no steal after the cilk_spawn indicated by (A):
In this case, a reducer object visible in strand (1) can be directly updated by strand (3) and (4). Because there is no steal, there is no new view is created and no reduce operation is called.
Steal
Strand (2), the continuation of the cilk_spawn at (A), is stolen:
In this case, a reducer object in strand (1) is visible in strand (3), the child. Strand (2), the continuation, receives a new view with an identity value. At the sync (B), the new reducer view is reduced into the original view visible to strand (3).
Example: Using reducer_opadd<>
This example consists of a simplified program that uses reducer_opadd<> to accumulate a sum of integers in parallel. For addition, the identity value is 0, and the reduction function adds the right value into the left value:
1 #include <cilk/cilk.h>
2 #include <cilk/reducer_opadd.h>
3
4 cilk::reducer_opadd<int> sum;
5
6 void addsum()
7 {
8 sum += 1;
9 }
10
11 int main()
12 {
13 sum += 1;
14 cilk_spawn addsum();
15 sum += 1; // the value of sum here depends on whether a steal occurred
16 cilk_sync;
17 return sum.get_value();
18 }
First, consider the serial case when the execution occurs on a single processor, and there is no steal. In this case, there is no private view of sum created, so all operations are performed on the leftmost instance. Because no new views are created, the reduction operation is never called. The value of sum will increase monotonically from 0 to its final value of 3.
In this case, because there was no steal, the cilk_sync statement is treated as a no-op.
Now, consider the case where a steal occurs. When sum is accessed at line 15, a new view with an identity value (0) is created. The value of sum after line 15 executes will be 1. The parent gets the new (identity) view and child gets the view that was active at the time of the spawn. This allows reducers to maintain deterministic results for reduce operations that are associative but not commutative. The child (addsum) operates on the leftmost instance, and so sum increases from 1 to 2 at line 8.
When the cilk_sync statement is encountered, if the strands joining together have different views of sum, those views are merged using the reduction operation. In this case, reduction is an addition, so the new view in the parent (value 1) is added into the view held by the child (value 2) resulting in the leftmost instance receiving the value 3. After the reduction, the new view is destroyed.
Lazy semantics
You can think of each strand as having a private view of the reducer. For performance purposes, these views are created lazily-that is, only when two conditions are met.
First, a new view will only be created after a steal.
Second, the new view is created when the reducer is first accessed in the new strand. At that point, a new instance is created, holding an identify value as defined by the default constructor for the type.
If a new view has been created, it is merged into the prior view at cilk_sync. If no view was created, no reduction is necessary. (Logically, you can consider that an identity was created and then merged, which would be a no-op.)
Safe operations
It is possible to define a reducer by implementing only the identity and reduction functions. However, it is typically both safer and more convenient to provide functions using operator overloads in order to restrict the operations on reducers to those that make sense.
For example, reducer_opadd defines +=, -=, * ++, --, +, and - operators. Operations such as multiply (*) and divide (/) do not provide deterministic and consistent semantics, and, therefore, are not provided in the reducer_opadd definition.