Software Archive
Announcements
17060 Discussions

## Why calculation of fibonacci with cilk took longer? Beginner
299 Views

I'm running on Linux (ubuntu) Intel I7 1600Mhz, with 4 cores. I'm using Intel compiler V14 I measured the time it tooks to calculate fibonacci with or without cilk:

``````int fib(int n) {

if (n < 2) {
return n;
}
else {
int x = cilk_spawn fib(n-1);
int y = fib(n-2);
cilk_spawn;
return (x+y);
}
}

inf seqFib(int n) {

if (n < 2) {
return n;
}
else {
int x = fib(n-1);
int y = fib(n-2);
return (x+y);
}

}

long long getNanoTime() {

struct timespec currTod;
long long curT = 0;
long long billion = 1000000000;

clock_gettime(CLOCK_REALTIME, &currTod);
curT  = currTod.tv_sec * billion ;
curT += currTod.tv_nsec;

return curT;

}

int main() {
int x = 40;
long long start = getNanoTime();
int res = fib(x);
long long end = getNanoTime();
cout << "\n cilk: " << res;

start = getNanoTime();
res = seqFib(x);
end = getNanoTime();
cout << "\n seq:" << res;

return 0;

}``````

But the results are weired: With cilk the result is 427 nano and without cilk it tooks 281 nano

I run it for several times, and same results ... Employee
299 Views

There's two errors in the listing that probably came from typing them into the forum editor (which I have trouble with too).

• There's a type "inf" that should be "int" in the declaration of seqFib.
• Function fib has cilk_spawn where it should be cilk_sync.

Another problem is that seqFib is calling fib when it recurses, so it's essentially fully parallel.

The amount of work per cilk_spawn is extremely small, just a few integer operations, so parallel scheduling overheads will dwarf any gains from parallelism.  It's better to use seqFib for small n, something like this:

```int seqFib(int n) {
if (n < 2) {
return n;
}
else {
int x = seqFib(n-1);
int y = seqFib(n-2);
return (x+y);
}
}

int fib(int n) {
if (n < 20) {
return seqFib(n);
}
else {
int x = cilk_spawn fib(n-1);
int y = fib(n-2);
cilk_sync;
return (x+y);
}
}```

The variable x in main should be declared volatile, or input from the command line.  Otherwise the compiler might optimize the entire seqFib(x) call away.  When I declared x as volatile, times got more believable.  (I'm using icc 16.0.0 Beta, because that's what was handy.)

By the way, n=40 is a bit small, and the time for the parallel run includes Cilk library startup.  Consider using n big enough that the run takes a second. 