topic tricky cilkification in Software Archive

tricky cilkification

newport_j — Thu, 29 Mar 2012 16:34:04 GMT

#include

#include "cilkview.h"

#include

int isprime ( int n )

{

int m;

int sqrt_n = sqrt(n);

for (m = 2; m <= sqrt_n+1; m++) // +1 in case of obscure rounding error

if ((n % m) == 0) return 0;

return 1;

}

int main ( int argc, char** argv )

{

cilkview_data_t start;

int i;

__cilkview_query(start);

cilk_for (i = 79000; i < 10081000; i++)

if (isprime(i)) { printf ( "%d ", i );

fflush(stdout); }

__cilkview_report(&start, NULL, "my_tag", CV_REPORT_WRITE_TO_RESULTS);

return 0;

}

In the above program, how does one cilkify is prime and main? I am guessing thatthe

the answer is not to take the following line:

if (isprime(i)) { printf ( "%d ", i );

and change it to

if (spawn isprime(i)) { printf ( "%d ", i );

That would generate an error; there must be a different way.

Thanks in advance.

Newport_j

tricky cilkification

Barry_T_Intel — Thu, 29 Mar 2012 17:17:50 GMT

You've already got a cilk_for on your loop searching for primes:

cilk_for (i = 79000; i < 10081000; i++)
{
    if (isprime(i))
    {
        printf ( "%d ", i ); 
        fflush(stdout);
    }
}

Why do you think you need more parallelism?

Also, I'm sure you know that you'll be racing on the calls to printf. Fortunately, individual calls to printf seem to be thread-safe, unlike using cout. You could get a correctly ordered list using a reducer_list and dump it when the loop concludes. Of course, then you'll get no indication of progress until the application completes.

- Barry

tricky cilkification

newport_j — Thu, 29 Mar 2012 18:44:57 GMT

Okay, let us drop the c for loop. I am really interested in the embedded ipsime in:

if (isprime()) {printf(%d',i)};

IfI want to spawn that function; I am sure that putting spawn next to it will not work. I must do somethng more elaborate.

if (cilk_spawn (isprime())) {printf(%d',i)};

will not work.

Any help appreciated.

Newport_j

tricky cilkification

Barry_T_Intel — Thu, 29 Mar 2012 19:21:38 GMT

> if (isprime()) {printf(%d',i)};
>
> If I want to spawn that function; I am  sure that putting spawn next to it will not work. I must do
> somethng more elaborate. 
>
> if (cilk_spawn (isprime())) {printf(%d',i)};
>
> will not work

Correct. Because the continuation of the expression may try to evaluate the spawned function call before the call returns. You could moving the entire if statement into a function. try something like:

void check_for_prime(int i)
{
    if isprime(i)
    {
        printf("%d ", i);
    }
}

and

cilk_spawn check_for_prime(i);

Lambda functions in the new C++ make this much easier.

HOWEVER, this suffers from spawning off small pieces of work. A Cilk application should always try to spawn off big pieces so that steals are infrequent.

- Barry