- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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 ...
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
The classic "fib" program is almost always used as the first example of a Cilk program. It's a really good example because it's really simple and clearly demonstrates the basic concepts behind Cilk programming. It's a really bad example because it's almost entirely overhead. Using the "cilk_spawn" keyword is relatively cheap, but it's not free. Since the program does almost nothing except spawn and sync, the overhead dominates the code. Worse yet, the compiler is *really* good at optimizing the sequential case.
Jim Sukha wrote an excellent pair of articles on this issue:
- Why is Cilk™ Plus not speeding up my program? (Part 1)
- Why is Cilk™ Plus not speeding up my program? (Part 2)
So I'm not surprised that you're not seeing speedup. fib() is *the* poster child for Jim's first pitfall: Parallel regions with insufficient work.
- Barry
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page