topic Thanks all. Your comments is in Software Archive

recursive function in Cilk

Amos_W_ — Sun, 21 Feb 2016 16:58:58 GMT

Hello,

I just write a simple Cilk code to test how deep recursive function call Cilk can reach. When I set up recursive level over 100,000, Cilk application has segmentation fault. How do I extend recursive level to go deeper? Or, how big the stacksize there is as default?

Result:
[amos@Machine Pi]$ ./cilk-icc 100
Cilk took 0.000000 sec
Steps = 100.000000;Pi = 3.141601
[amos@Machine Pi]$ ./cilk-icc 1000
Cilk took 0.290000 sec
Steps = 1000.000000;Pi = 3.141593
[amos@Machine Pi]$ ./cilk-icc 10000
Cilk took 0.370000 sec
Steps = 10000.000000;Pi = 3.141593
[amos@Machine Pi]$ ./cilk-icc 100000
Segmentation fault (core dumped)

Code:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <cilk/cilk.h>
#include <time.h>

static double num_steps;
double step, pi;
double pi_calculate( double counter, double sum );

static void _usage(FILE *f, int error) {
fprintf(f, "Usage: ./cilk NUMBER\n");
fflush(f);
}

int main(int argc, char *argv[])
{
int i,j;
double x, sum=0;

argc -= optind;
argv += optind;

switch (argc) {
case 0:
fprintf(stderr, "\nMissing pi number.\n"); // fall through
default:
_usage(stderr, 0);
case 1:
num_steps = atof(argv[0]);
break;
}
step = 1.0/ (double)num_steps;

clock_t start = clock();
sum = pi_calculate( 0, 0 );
clock_t end = clock();

double duration = (double)(end - start) / CLOCKS_PER_SEC;
printf("Cilk took %f sec\n", duration);

pi = step*sum;
printf( "Steps = %f;Pi = %f\n", num_steps, pi );

return 0;
}

double pi_calculate( double counter, double sum )
{
double x, result=0, result_2=0;

//printf("counter =%f/%f\n", counter, num_steps);
if( counter < num_steps ) {
x = (counter + 0.5) * step;
result = sum + 4.0/(1.0+x*x);
result_2 = cilk_spawn pi_calculate( counter+1, result );
cilk_sync;
return result_2;
}
else return sum;
}

Amos

The stack size should be same

Barry_T_Intel — Mon, 22 Feb 2016 16:38:31 GMT

The stack size should be same as for a C/C++ app. And on Windows, at least (I don't recall if we could get the information on Mac and/or LInux) if you change the stack size via linker directives, we'll should obey those too.

However, you're also hitting the spawn depth limit. The worker's deque is hard coded to 1024 entries, so you can't spawn infinitely either. This is a balance between how deep is reasonable and memory usage, since every worker will contain a deque.

Of course, you're welcome to build your own runtime and specify a custom deque size. Look in global_state.cpp for function cilkg_init_global_state(), and then look for the initialization of g->ltqsize with the comment /* FIXME */ :o)

It is counter productive to

jimdempseyatthecove — Mon, 29 Feb 2016 13:44:54 GMT

It is counter productive to recurse-spawn to create a number of tasks that exceed more than a few times the number of available logical processors. When the workload per recursion level is equal, then 1x the number of available logical processors. Unequal loads may experience a benefit with a larger multiplier. When you reach the desired number of tasks, then you can continue recursions without spawn.