reducer for arithmetic operation

reducer for arithmetic operation

Hi everyone,

does anybody know that how can we write our own reducer for arithmetic operations (+,-,*,/,etc.)? In case of '+' and '-' operators there exists a reducer but for '*' and '/' I need to write my own. So anyone can help me?

--Abdul Jabbar--

12 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

The fine manual (surprise!) includes one of the better descriptions of how to examine the supplied reducers and adapt them to your purposes.

It's not clear why you made this new post with little information included, when you seemed to have made some progress according to your previous thread.

Without understanding what the goal of your project is, there might not be much more that can be done to help.    The guide that was uploaded in your previous post contains the relevant theory that one needs to understand to construct custom reducers.  I would suggest trying to read it a bit more carefully to understand why constructing a reducer for "/" is going to be difficult.



the goal of my project is to do some n-times square-matrix multiplication. I had written the reducer for this before posting this topic but when I run it parallel it gives me segmentation fault. It seems like the multiple copies of reducer are not created so that after one iteration it gives me segmentation fault. Below is the code:

class matrix_monoid;

class matrix
friend class matrix_monoid;
     double **values;
           values = new double*[(n+1)];   // n is a global variable declared
            for(int i = 0; i < (n+1); i++){
                values[i] = new double[(n+1)];}
    matrix operator*=(matrix M){
        matrix temp;
        matmul(temp.values,values, M.values, n+1, n, 0); // this is the function that multiply two matrix and store the result in temp.values
                                                                     // in my case values and M.values will be same because i want to take square of matrices
        for(int i = 0; i < n+1; i++){
            for(int j = 0; j < n+1; j++)

                         values[i][j] = temp.values[i][j];// here i'm setting the result back in values because next time this will be squared


        return *this;
    void set(double **temp1 ){
               for(int r = 0; r < n+1; r++){
                values[r] = new double[n+1];
                for(int c = 0; c < n+1; c++){
                    values[r][c] = temp1[r][c];}}
    double** get_value()
        return values;

struct matrix_monoid: public cilk::monoid_base<matrix>
    typedef matrix value_type;
    static void identity(matrix *p){
        p = new matrix;
     static void reduce (matrix* left,matrix* right) {
              *left *= *right;

In main function:

cilk::reducer<matrix_monoid> M;

M().set(Z);    // initialized with some matrix Z

cilk_for(int count = 0; count < 16; count++){
        M() *= M();             // here it gives me segmentation fault after one iteration and if you replace "cilk_for" with "for" then works fine.


So I don't know exactly why i'm getting segmentation fault.

--Abdul Jabbar--

At least part of your problem is coming from the identity method:

  static void identity(matrix *p){  p = new matrix;  }

The parameter to the identity function is a pointer to a block of raw memory to fill in.  The identity method above changes the local pointer p from the original raw block of memory the runtime was expecting to be filled in to a new matrix object allocated off the heap, and then returns.  The net effect is that a new matrix object has been allocated, is immediately thrown away, and the original memory for the identity matrix is left uninitialized.   That behavior seems to be consistent with the segfault you are seeing.

Instead, I believe the identity method should be initializing the p->values field, as you have done in the default constructor of a matrix().   
Alternatively, if you omit the definition of the identity method altogether, the default constructor of the view (matrix in this case) will be called to create identity views.  That should also eliminate your segfault.



ok ... now segmentation fault is eliminated but here comes the new error after some iterations:

sched.c:237: cilk assertion failed: w->l->do_not_steal == 0

and program aborts. Now what can be reason for this?

--Abdul Jabbar--

Do you have a small test program which reproduces the crash?    

Are you spawning a function from inside the "reduce" method of the reducer?   That possibility would be consistent with the error message that you are seeing.   Parallelism within a reduce function is allowed in newer versions of Cilk Plus (e.g., Intel® Composer XE 2013) but I believe is not implemented in the version that you are currently working with.   



No, i'm not spawning the child inside reducer i'm only doing this *left *= *right; in reduce function as in my previous comment.

I will get back you on this with sample program.

--Abdul Jabbar

here is the sample program which crashes on the same error (cilk assertion failed).

--Abdul Jabbar--


Downloadtext/x-c++src test4.cpp2.4 KB

It looks as though your " *left = *= *right " statement should be calling operator * on a matrix object.   The operator * does call matmul, which has a cilk_spawn inside.   Thus, your code is in fact trying to exploit parallelism inside the reduce function, which explains the bug you are seeing.
When I compiled using a newer version of the compiler and runtime, the program did not crash.

More generally, however, you may wish to review your overall approach to the problem first, as reducers may not be what you want to use here...




I’m afraid that what you are trying to do cannot be done with reducers.

The basic theory of writing a reducer, as described in the user’s guide, is that

  • You have a sequence of values to combine an operation: a1 OP a2 OP … OP an.
  • The operation is associative and has an identity value, I.
  • The algorithm does the computation by successively updating an accumulator variable:  x = I; x = x OP a1; x = x OP a2; … x = x OP an.
  • You create a monoid that describes the operation:
    • The reduce() function represents the operation.
    • The identity() function represents the identity value.
  • You replace the accumulator variable with a reducer that uses your monoid.
  • The only operations that you apply to the reducer are:
    • Initialize it.
    • Update it with “reducer = reducer OP value”.
    • Retrieve the value when the computation is complete.

The sequence of operations “x = x * x; x = x * x; … x = x * x” does not fit this reducer pattern. Rather than combining a sequence of values with an operation, it repeatedly transforms a single value.

The associative operation with an identity element is critical to the correct functioning of a reducer. A reducer works by breaking up a sequence of updates to an accumulator variable. It creates a separate accumulator variable for each strand of the parallel computation, initializes it to the identity value, and applies a subsequence of the updates to it. Then the values of the per-strand accumulator variables can be combined. Grouping the computations into subsequences and combining the partial results works because the operation is associative and the individual updates are independent. This is not true for your computation.



thanks for your help Jim and Neil.


Abdul Jabbar.

Leave a Comment

Please sign in to add a comment. Not a member? Join today