cilk reducer use in lower level

[adnan4791]

Hi every one,

I am new member in this group. My name is Adnan.
I would like to ask about how to use OpenCilk reducer in lower level way.
For example, using reducer in cilk_for structure is a common way to eliminate a race. But in this case to teach student how the reducer is working, i have to demonstrate divide and conquer so that my student understand. So, I made an simple tutorial about using cilk_spawn to implement divide and conquer to compute pi number. So here is the code below. My question is, is it correct way to explain how reducer and divide and conquer is working ?

#include <cilk/cilk.h>
#include <stdio.h>
#include <stdlib.h>

long num_step;
double delta;
long nb;
double compute_pi(long lower, long upper) {
double sum[1] = {0.0};
double x = 0.0;

if((lower+nb) >= upper ) {
    for(long i=lower;i<upper;i++) {
        x = (i+0.5) * delta;
        sum[0] += 4.0/(1+x*x) * delta;
    }
    return sum[0];
} 
else {
    double *left = sum;
    double right = cilk_spawn compute_pi(lower,(lower+upper)/2);
    *left = compute_pi((lower+upper)/2,upper);
    cilk_sync;
    *left = *left+right; 
    return sum[0];
}

}

int main(int argc, char *argv[]) {
if (argc < 2) {
printf("Please add problem size argument\n Program exited...\n");
exit(0);
}
num_step = atol(argv[1]);
delta = 1.0/num_step;
nb = 1000; //set grain size
double pi = compute_pi(0,num_step);
printf("%f\n",pi);
return 0;
}

[ailiop]

@adnan4791 Hi Adnan!

Thank you for this question. The code you posted certainly shows a correct way of implementing a recursive parallel reduction. In OpenCilk, however, reducers work fairly differently. A principal difference, in particular, is that the OpenCilk runtime internally implements various optimizations to handle reducers efficiently.

Let me go over a couple of similar code snippets to show the semantics of Cilk reducers and demonstrate at least one optimization that OpenCilk does internally. You can also find these codes in this attached (and zipped) source file: reducer-implementation-illustration.zip

Reducers and cilk_for in OpenCilk 2.0

Just as a starting/reference point, here is how a programmer would write the parallel reduction in OpenCilk 2.0. First, define the identity and reduce functions:

void sum_identity(void * view) {
    *(double *)view = 0.0;
}
void sum_reduce(void * left, void * right) {
    *(double *)left += *(double *)right;
}

The compute_pi() function can now be written as follows. (This is similar to your code but somewhat simplified.)

double compute_pi(long n) {
    double cilk_reducer(sum_identity, sum_reduce) sum = 0.0;
    cilk_for (long i = 0; i < n; i++) {
        sum += 1.0 / (n*n + i*(i+1) + 0.25);
    }
    return 4*n * sum;
}

Divide-and-conquer recursion -- unoptimized

The function reduction_recursive_unoptimized() below shows a correct but inefficient recursive implementation of the parallel reduction in compute_pi() above. The fact that it does not return a value is intentional: it is closer to how Cilk reducers are implemented, allows me to show where the sum_identity() and sum_reduce() functions are called, and highlights which pieces of memory are allocated and modified.

Note that this function allocates a new view of the sum variable for every right (i.e., upper-half) subcomputation in the reduction tree.

#define GRAINSIZE 2048  /* for example */

void reduction_recursive_unoptimized(double * sum, long n, long lower, long upper) {
    if ((upper - lower) <= GRAINSIZE) {
        for (long i = lower; i < upper; i++) {
            *sum += 1.0 / (n*n + i*(i+1) + 0.25);
        }
    } else {
        long middle = (lower + upper) / 2;

        /* left subcomputation */
        cilk_spawn reduction_recursive_unoptimized(sum, n, lower, middle);

        /* right subcomputation */
        double sum_new_view;  /* allocate new view */
        sum_identity(&sum_new_view);
        reduction_recursive_unoptimized(&sum_new_view, n, middle, upper);

        /* wait for left and right subcomputations, then merge */
        cilk_sync;
        sum_reduce(sum, &sum_new_view);
    }
}

double compute_pi(long n) {
    double sum = 0.0;
    reduction_recursive_unoptimized(&sum, n, 0, n);
    return 4*n * sum;
}

Divide-and-conquer recursion -- optimization: lazy view allocation

The function reduction_recursive_lazyviews() below shows one optimization on top of the previous implementation. Specifically, it allocates new views for the right subcomputation lazily, i.e., only if the left and right subcomputations actually execute in parallel.

NOTE: The code below is pseudocode: it uses a function is_continuation_stolen() to illustrate what the OpenCilk runtime does internally, but in reality there is no such function that can be called from user code. This function should return true if a Cilk worker has just stolen the continuation to work on the right subcomputation, and false if the same Cilk worker who finished the left subcomputation now moves on to the right subcomputation.

bool is_continuation_stolen(); /* hypothetical function that detects steals during runtime */

void reduction_recursive_lazyviews(double * sum, long n, long lower, long upper) {
    if ((upper - lower) <= GRAINSIZE) {
        for (long i = lower; i < upper; i++) {
            *sum += 1.0 / (n*n + i*(i+1) + 0.25);
        }
    } else {
        long middle = (lower + upper) / 2;
        cilk_spawn reduction_recursive_lazyviews(sum, n, lower, middle);

        /* PSEUDOCODE: in reality, this is handled internally by the
         * OpenCilk runtime system */
        if (is_continuation_stolen()) {
            /* this is the same as for the right subcomputation in the
             * unoptimized code above */
            double sum_new_view;
            sum_identity(&sum_new_view);
            reduction_recursive_lazyviews(&sum_new_view, n, middle, upper);
            cilk_sync;
            sum_reduce(sum, &sum_new_view);
        } else /* (!is_continuation_stolen()) */ {
            /* reuse the memory pointed to by `sum`; this is just as it would
             * have been in a serial implementation and does not use the
             * reducer callbacks `sum_identity()` and `sum_reduce()` */
            reduction_recursive_lazyviews(sum, n, middle, upper);
            /* no need to cilk_sync */
        }
    }
}

Other optimizations?

As I mentioned earlier, there are several additional optimizations in the runtime system for managing reducers more efficiently, but these are hard to show with such code snippets without getting into the runtime system in more detail. For example, the function reduction_recursive_lazyviews() implies that a left view may only be combined with its sibling right view (see the call to sum_reduction() in the if-block). In practice, the runtime may merge any pair of adjacent views as soon as they are ready.

Do these examples and explanation help?

[adnan4791]

@ailiop Hi....

Thank you for your answer an explanation, it help me much

I am sorry I don't know how to mention your name, btw.

[mohandotyes]

How do i use cilk_reducer to write data to file??

[neboat]

Thank you for reaching out. I believe I answered your question on StackOverflow: https://stackoverflow.com/questions/75155198/how-to-use-cilk-reducer-variable-to-write-data-into-a-file-without-race-conditio/75203198#75203198.